Maths Olympiad Prep

Library / /22 of 35

Number theory Difficulty 5.8 AIME, harder Prove it Belarus

Let aba \neq b be coprime positive integers such that for each integer kk from 11 to 1010 the numbers a+ka + k and b+kb + k are not coprime.
Find the minimal possible value of ab|a - b|.

Solution

Answer: 23102310. Suppose aa and bb satisfy the problem conditions. For each integer kk from 11 to 1010 denote by pkp_k the minimal prime divisor of gcd(a+k,b+k)\gcd(a+k, b+k). Since the gcd\gcd of numbers divides their difference, among 1010 successive integers at most 10pk\lfloor \frac{10}{p_k} \rfloor can be a multiple of pkp_k. For pk=2p_k = 2 this number is 55, for pk=3p_k = 3 it is 44, for pk=5p_k = 5 and pk=7p_k = 7 it is 22 and for the others it equals 11.
If all pkp_k are odd then the equality 10=4+2+2+1+110 = 4 + 2 + 2 + 1 + 1 implies that there is at least five distinct primes. Then ba3571113>2310b - a \ge 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 > 2310. Consider the case when some pi=2p_i = 2. Since aa and bb are coprime, ii cannot be even so 2=p1=p3==p92 = p_1 = p_3 = \dots = p_9. Among five primes p2,p4,,p10p_2, p_4, \dots, p_{10} at most 22 can be equal to 33, and for each prime p5p \ge 5 at most one can be equal to pp. Now the equality 10=5+2+1+1+110 = 5 + 2 + 1 + 1 + 1 implies that ba235711=2310b - a \ge 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 = 2310.
On the other hand, if a=2311a = 2311 and b=4621b = 4621 then p1=p3==p9=2p_1 = p_3 = \dots = p_9 = 2, p2=p8=3p_2 = p_8 = 3, p4=5p_4 = 5, p6=7p_6 = 7 and p10=11p_{10} = 11, whence ab=2310|a - b| = 2310 is possible.

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.