Maths Olympiad Prep

Library /

Number theory Difficulty 6.9 National olympiad Prove it Hong Kong

For any positive integer aa, define M(a)M(a) to be the number of positive integers bb for which a+ba+b divides abab. Find all integer(s) aa with 1a20131 \le a \le 2013, so that M(a)M(a) is largest possible in the range of aa.

Solution

The answer is a=1680a = 1680.
Since aba(a)=a2(moda+b)ab \equiv a(-a) = -a^2 \pmod{a+b}, we have a+baba+b \mid ab if and only if a+ba2a+b \mid a^2. This shows a+ba+b can be any divisor of a2a^2 greater than aa. Also, any such divisor corresponds to a unique positive integer bb. Therefore, M(a)M(a) is the number of divisors of a2a^2 greater than aa. Since the positive divisors of a2a^2 less than aa are in one-to-one correspondence to the divisors of a2a^2 greater than aa, it remains to find aa which has the maximum number of positive divisors.
For any a=p1c1p2c2pscsa = p_1^{c_1} p_2^{c_2} \cdots p_s^{c_s} where p1,p2,,psp_1, p_2, \ldots, p_s are distinct prime divisors of aa, recall that d(a2)=(2c1+1)(2c2+1)(2cs+1)d(a^2) = (2c_1+1)(2c_2+1)\cdots(2c_s+1). WLOG we may assume c1c2csc_1 \ge c_2 \ge \cdots \ge c_s. Since 2×3×5×7×11=2310>20132 \times 3 \times 5 \times 7 \times 11 = 2310 > 2013, we have s4s \le 4.
* If s=4s=4, we must have c3=c4=1c_3 = c_4 = 1 since 2232527=6300>20132^2 3^2 5^2 7 = 6300 > 2013.
- If c22c_2 \ge 2, we must have c1=c2=2c_1 = c_2 = 2 since 233257=2520>20132^3 3^2 5 \cdot 7 = 2520 > 2013. When a=p12p22p3p4a = p_1^2 p_2^2 p_3 p_4, we have d(a2)=5232=225d(a^2) = 5^2 \cdot 3^2 = 225.
- If c2=1c_2 = 1, we have c14c_1 \le 4 since 25357=3360>20132^5 3 \cdot 5 \cdot 7 = 3360 > 2013. When a=p14p2p3p4a = p_1^4 p_2 p_3 p_4, we have d(a2)=933=243d(a^2) = 9 \cdot 3^3 = 243.

• If s=3s = 3, we must have c32c_3 \le 2 since 233353=27000>20132^33^35^3 = 27000 > 2013.
– If c3=2c_3 = 2, we must have c2=2c_2 = 2 since 233352=5400>20132^33^35^2 = 5400 > 2013. Then c13c_1 \le 3 since 243252=3600>20132^43^25^2 = 3600 > 2013. When a=p13p22p32a = p_1^3 p_2^2 p_3^2, we have d(a2)=752=175d(a^2) = 7 \cdot 5^2 = 175.
– If c3=1c_3 = 1, we must have c23c_2 \le 3 since 24345=6480>20132^43^45 = 6480 > 2013.
* If c2=3c_2 = 3, we have c1=3c_1 = 3 since 24335=2160>20132^43^35 = 2160 > 2013. When a=p13p23p3a = p_1^3 p_2^3 p_3, we have d(a2)=723=147d(a^2) = 7^2 \cdot 3 = 147.
* If c2=2c_2 = 2, we have c15c_1 \le 5 since 26325=2880>20132^63^25 = 2880 > 2013. When a=p15p22p3a = p_1^5 p_2^2 p_3, we have d(a2)=1153=165d(a^2) = 11 \cdot 5 \cdot 3 = 165.
* If c2=1c_2 = 1, we have c17c_1 \le 7 since 2835=3840>20132^83 \cdot 5 = 3840 > 2013. When a=p17p2p3a = p_1^7 p_2 p_3, we have d(a2)=1532=135d(a^2) = 15 \cdot 3^2 = 135.
• If s=2s = 2, we must have c24c_2 \le 4 since 2535=7776>20132^53^5 = 7776 > 2013.
– If c2=4c_2 = 4, we have c1=4c_1 = 4 since 2534=2592>20132^53^4 = 2592 > 2013. When a=p14p24a = p_1^4 p_2^4, we have d(a2)=92=81d(a^2) = 9^2 = 81.
– If c2=3c_2 = 3, we have c16c_1 \le 6 since 2733=3456>20132^73^3 = 3456 > 2013. When a=p16p23a = p_1^6 p_2^3, we have d(a2)=137=91d(a^2) = 13 \cdot 7 = 91.
– If c2=2c_2 = 2, we have c17c_1 \le 7 since 2832=2304>20132^83^2 = 2304 > 2013. When a=p17p22a = p_1^7 p_2^2, we have d(a2)=155=75d(a^2) = 15 \cdot 5 = 75.
– If c2=1c_2 = 1, we have c19c_1 \le 9 since 2103=3072>20132^{10}3 = 3072 > 2013. When a=p19p2a = p_1^9 p_2, we have d(a2)=193=57d(a^2) = 19 \cdot 3 = 57.
• If s1s \le 1, we have c110c_1 \le 10 since 211=2048>20132^{11} = 2048 > 2013. When a=p110a = p_1^{10}, we have d(a2)=21d(a^2) = 21.
Therefore, a2a^2 has at most 243 positive divisors. This holds when a=p14p2p3p4a = p_1^4 p_2 p_3 p_4 for some distinct primes p1,p2,p3,p4p_1, p_2, p_3, p_4. As 34235=2430>20133^42 \cdot 3 \cdot 5 = 2430 > 2013, we must have p1=2p_1 = 2. Also, since 243511=2640>20132^43 \cdot 5 \cdot 11 = 2640 > 2013, the only possibility is a=24357=1680a = 2^43 \cdot 5 \cdot 7 = 1680.

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 and solution reproduced as published; topic and difficulty added by this site.