Maths Olympiad Prep

Library / /57 of 92

Number theory Difficulty 6.6 National olympiad Prove it Iran

Is it possible to write 14001400 natural numbers (not necessarily distinct) around a circle such that 20212021 is used at least once and each number is the sum of the greatest common divisor of the two previous numbers and the greatest common divisor of the two next numbers? For example, if a,b,c,d,ea, b, c, d, e are five consecutive numbers on the circle then c=gcd(a,b)+gcd(d,e)c = \gcd(a, b) + \gcd(d, e).

Solution

We shall show that this is impossible. Assume that there are such 14001400 numbers. First of all, note that if we divide all the numbers by kk then the new numbers satisfy the second condition and one of them is a divisor of 20212021, so we can assume that the greatest common divisor of the numbers is 11.

Lemma. *the gcd of each three consecutive numbers on the circle is 11.*

Proof. Assume that a,b,c,d,ea, b, c, d, e are five consecutive numbers on the circle, if a,b,ca, b, c have a common divisor dd, then the equality c=gcd(a,b)+gcd(d,e)c = \gcd(a, b) + \gcd(d, e) implies that d,ed, e are also divisible by dd. Similarly all the numbers should be divisible by dd which is in contradiction with our assumption. This completes our proof.

Assume that mm is the maximum number on the circle, and x,y,m,z,tx, y, m, z, t be five consecutive numbers. We know that m>4m > 4 because at least one of the numbers should be a divisor of 20212021 and 20212021 is not divisible by 2,3,42, 3, 4. We have m=gcd(x,y)+gcd(z,t)m = \gcd(x, y) + \gcd(z, t) so at least one of the gcd(x,y)\gcd(x, y), gcd(z,t)\gcd(z, t) should be at least m2\frac{m}{2}. Without the loss of generality we can assume that gcd(x,y)m2\gcd(x, y) \ge \frac{m}{2}.

If xyx \neq y then max(x,y)m\max(x, y) \geq m, yielding max(x,y)=m\max(x, y) = m. If y=my = m then by the assumption x>gcd(m,y)=mx > \gcd(m, y) = m we shall arrive at a contradiction hence we have x=m,y=m2x = m, y = \frac{m}{2}. This implies that gcd(z,t)=m2\gcd(z, t) = \frac{m}{2} therefore z=m2,y=mz = \frac{m}{2}, y = m which contradicts to the fact that y>gcd(z,m)y > \gcd(z, m).

So we have x=ym2x = y \ge \frac{m}{2}, let ww be the number before xx. From the lemma we know that gcd(w,x)=1\gcd(w, x) = 1 and we have
x=gcd(w,x)+gcd(m,z)=1+(m,z)    x1m. x = \gcd(w, x) + \gcd(m, z) = 1 + (m, z) \implies x - 1 \mid m.
If mm is odd this contradicts to the fact that x1m21x - 1 \ge \frac{m}{2} - 1, if mm is even we have x=m2+1x = \frac{m}{2} + 1 and gcd(m,z)=m2\gcd(m, z) = \frac{m}{2}. But we have
m=gcd(x,y)+gcd(z,t)=m2+1+(m2,t)    m21m2. m = \gcd(x, y) + \gcd(z, t) = \frac{m}{2} + 1 + \left(\frac{m}{2}, t\right) \implies \frac{m}{2} - 1 \mid \frac{m}{2}.
Which contradicts to the fact that m2>2\frac{m}{2} > 2. ■

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.