Examkin

Question

Difficulty: MediumDivisibility, Factors, and Multiples

What is the smallest positive integer nn such that nn is divisible by both 1212 and 1818, and nn has exactly 1212 positive divisors?

Answer: 72

Answer

The smallest positive integer satisfying all given conditions is 72.
To satisfy the divisibility requirements, nn must be a multiple of LCM(12,18)=36=22×32\text{LCM}(12, 18) = 36 = 2^2 \times 3^2. Thus, n=2a×3b×…n = 2^a \times 3^b \times \dots where a≥2a \geq 2 and b≥2b \geq 2. The total number of positive divisors of nn is given by (a+1)(b+1)⋯=12(a+1)(b+1)\dots = 12. Since a+1≥3a+1 \geq 3 and b+1≥3b+1 \geq 3, nn cannot have any additional prime factors, as that would yield at least 3×3×2=183 \times 3 \times 2 = 18 divisors. Factoring 12 into two integers each at least 3 gives 3×43 \times 4 or 4×34 \times 3. Setting (a+1,b+1)=(3,4)(a+1, b+1) = (3, 4) yields a=2,b=3a = 2, b = 3, giving n=22×33=108n = 2^2 \times 3^3 = 108. Setting (a+1,b+1)=(4,3)(a+1, b+1) = (4, 3) yields a=3,b=2a = 3, b = 2, giving n=23×32=72n = 2^3 \times 3^2 = 72. The smallest value is 72.

Step-by-Step Solution

1
Determine the prime factor constraints on nn
nn must be divisible by 222^2 and 323^2, so n=2a×3b×…n = 2^a \times 3^b \times \dots with a≥2a \geq 2 and b≥2b \geq 2.
For nn to be divisible by 12=22×3112 = 2^2 \times 3^1 and 18=21×3218 = 2^1 \times 3^2, its prime factorization must contain at least the maximum power of each prime appearing in either 12 or 18.
2
Set up the divisor count equation
(a+1)(b+1)=12(a+1)(b+1) = 12 with a+1≥3a+1 \geq 3 and b+1≥3b+1 \geq 3, and no additional prime factors.
The number of divisors of n=p1e1p2e2…n = p_1^{e_1} p_2^{e_2} \dots is (e1+1)(e2+1)…(e_1+1)(e_2+1)\dots. Since (a+1)≥3(a+1) \geq 3 and (b+1)≥3(b+1) \geq 3, adding another prime factor would make the product at least 3×3×2=18>123 \times 3 \times 2 = 18 > 12.
3
Find all possible pairs of exponents (a,b)(a, b) and calculate candidate values for nn
Candidate 1: a=2,b=3  ⟹  n=22×33=108a=2, b=3 \implies n = 2^2 \times 3^3 = 108. Candidate 2: a=3,b=2  ⟹  n=23×32=72a=3, b=2 \implies n = 2^3 \times 3^2 = 72.
The only factor pairs of 12 into integers ≥3\geq 3 are 3×43 \times 4 and 4×34 \times 3.
4
Identify the minimum value
n=72n = 72
72<10872 < 108, so 72 is the smallest positive integer fulfilling all criteria.

Key Concept

Divisor Count Formula & Least Common Multiple constraints
Rate this question

Topics

Divisibility, Factors, and Multiples

More questions from this topic