Maths Olympiad Prep

Library / /5 of 8

Number theory Difficulty 4.3 AIME Prove it Japan

Determine the smallest possible positive integer nn for which the 4 numbers 14n14n, 16n16n, 18n18n, 20n20n have exactly the same number of positive factors.

Solution

Let us first prove the following Theorem:

Theorem
Suppose that a positive integer nn has the prime factorization n=p1e1p2e2pmemn = p_1^{e_1} p_2^{e_2} \cdots p_m^{e_m}. (Here, p1,p2,,pmp_1, p_2, \cdots, p_m are distinct prime numbers and e1,e2,,eme_1, e_2, \cdots, e_m are positive integers.) Then the total number of factors of nn equals (e1+1)(e2+1)(em+1)(e_1 + 1)(e_2 + 1) \cdots (e_m + 1).

Proof: Any factor of nn can be represented in the form p1f1p2f2pmfmp_1^{f_1} p_2^{f_2} \cdots p_m^{f_m} with fjf_j being an integer satisfying 0fjej0 \le f_j \le e_j for each j=1,2,,mj = 1, 2, \cdots, m. It is clear that the different mm-tuples of integers (f1,f2,,fm)(f_1, f_2, \cdots, f_m) correspond to different factors of nn. Therefore, the total number of factors of nn coincides with the number of mm-tuples (f1,f2,,fm)(f_1, f_2, \cdots, f_m) satisfying the conditions above. Since there are exactly ej+1e_j + 1 choices for fjf_j for each j=1,2,,mj = 1, 2, \cdots, m there are (e1+1)(e2+1)(em+1)(e_1 + 1)(e_2 + 1) \cdots (e_m + 1) such mm-tuples, which proves the claim of the Theorem.

Let us now show that the desired answer for the problem is 30. Suppose nn is an integer satisfying the condition of the problem. If nn has a prime factor besides 2, 3, 5, 7, then since 14=2714 = 2 \cdot 7, 16=2416 = 2^4, 18=23218 = 2 \cdot 3^2, 20=22520 = 2^2 \cdot 5, the integer obtained by dividing nn by that prime factor is smaller than nn and satisfies the condition of the problem as well. So, we may assume that nn has only 2,3,5,72, 3, 5, 7 as its prime factors. Therefore, we can write n=2a3b5c7dn = 2^a \cdot 3^b \cdot 5^c \cdot 7^d, where a,b,c,da, b, c, d are non-negative integers. If we now assume that the number of factors of 14n,16n,18n,20n14n, 16n, 18n, 20n are p,q,r,sp, q, r, s, respectively, then by the Theorem above, we have
p=(a+2)(b+1)(c+1)(d+2),q=(a+5)(b+1)(c+1)(d+1),r=(a+2)(b+3)(c+1)(d+1),s=(a+3)(b+1)(c+2)(d+1). p = (a + 2)(b + 1)(c + 1)(d + 2), \quad q = (a + 5)(b + 1)(c + 1)(d + 1), \\ r = (a + 2)(b + 3)(c + 1)(d + 1), \quad s = (a + 3)(b + 1)(c + 2)(d + 1).
It then follows that we have
q=p    (a+5)(d+1)=(a+2)(d+2)    a1=3d,q=r    (a+5)(b+1)=(a+2)(b+3)    2a+1=3b,q=s    (a+5)(c+1)=(a+3)(c+2)    a+1=2c. \begin{align*} q &= p \iff (a+5)(d+1) = (a+2)(d+2) &\iff a-1 &= 3d, \\ q &= r \iff (a+5)(b+1) = (a+2)(b+3) &\iff 2a+1 &= 3b, \\ q &= s \iff (a+5)(c+1) = (a+3)(c+2) &\iff a+1 &= 2c. \end{align*}
If we make the value of aa bigger, b,c,db, c, d also get bigger, so if nn is the smallest possible integer satisfying the requirement, then aa also has to be the smallest non-negative integer satisfying the conditions above. By substituting a=0,1,a = 0, 1, \dots, and checking to see when all of b,c,db, c, d become non-negative integers, we see that a=1a = 1 is the smallest value for aa for which all of b,c,db, c, d are non-negative integers and their values are b=1,c=1,d=0b = 1, c = 1, d = 0. Thus the answer to the problem is n=21315170=30n = 2^1 \cdot 3^1 \cdot 5^1 \cdot 7^0 = 30.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.