Maths Olympiad Prep

Library / /116 of 520

Number theory Difficulty 6.5 National olympiad Find the answer

When Meena turned 16 years old, her parents gave her a cake with nn candles, where nn has exactly 16 different positive integer divisors. What is the smallest possible value of nn?

A number or a short expression. Spacing and $ signs are ignored.

Solution

To find the smallest possible value of n n that has exactly 16 different positive integer divisors, we need to consider the number of divisors function. For a number n n with prime factorization n=p1e1p2e2pkek n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} , the number of divisors d(n) d(n) is given by:

d(n)=(e1+1)(e2+1)(ek+1) d(n) = (e_1 + 1)(e_2 + 1) \cdots (e_k + 1)

We need d(n)=16 d(n) = 16 . The possible factorizations of 16 are:

1. 16=16×1 16 = 16 \times 1
2. 16=8×2 16 = 8 \times 2
3. 16=4×4 16 = 4 \times 4
4. 16=4×2×2 16 = 4 \times 2 \times 2
5. 16=2×2×2×2 16 = 2 \times 2 \times 2 \times 2

We will consider each case to find the smallest n n .

Case 1: n=p115 n = p_1^{15}
- The smallest prime is 2.
- n=215=32768 n = 2^{15} = 32768

Case 2: n=p17p2 n = p_1^7 \cdot p_2
- The smallest primes are 2 and 3.
- n=273=1283=384 n = 2^7 \cdot 3 = 128 \cdot 3 = 384

Case 3: n=p13p23 n = p_1^3 \cdot p_2^3
- The smallest primes are 2 and 3.
- n=2333=827=216 n = 2^3 \cdot 3^3 = 8 \cdot 27 = 216

Case 4: n=p13p2p3 n = p_1^3 \cdot p_2 \cdot p_3
- The smallest primes are 2, 3, and 5.
- n=2335=835=120 n = 2^3 \cdot 3 \cdot 5 = 8 \cdot 3 \cdot 5 = 120

Case 5: n=p1p2p3p4 n = p_1 \cdot p_2 \cdot p_3 \cdot p_4
- The smallest primes are 2, 3, 5, and 7.
- n=2357=210 n = 2 \cdot 3 \cdot 5 \cdot 7 = 210

Among these cases, the smallest value of n n is found in Case 4:

n=2335=120 n = 2^3 \cdot 3 \cdot 5 = 120

Thus, the smallest possible value of n n that has exactly 16 different positive integer divisors is 120 \boxed{120} .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.