Maths Olympiad Prep

Library / /20 of 31

Number theory Difficulty 6.5 National olympiad Prove it Belarus

Let a1,a2,,ana_1, a_2, \dots, a_n be the sequence of positive integers. For each number \ell from 11 to n1n-1 the following collection was found:
(gcd(a1,a1+),gcd(a2,a2+),,gcd(an,an+)),(\gcd(a_1, a_{1+\ell}), \gcd(a_2, a_{2+\ell}), \dots, \gcd(a_n, a_{n+\ell})),
where all indices are taken modulo nn, i.e. if s>ns > n then as=asna_s = a_{s-n}. It turned out that all these collections consist of the same nn pairwise distinct numbers maybe in different ordering.
Find out if nn can be equal to a) 2121; b) 20212021.

Solution

Let us prove the following
Statement: n=k2k+1n = k^2 - k + 1 for some positive integer kk.
Proof: Let dd be the largest of the greatest common divisors found. Then the equality gcd(ai,ai+)=d\gcd(a_i, a_{i+\ell}) = d is equivalent to the fact that each of the numbers aia_i and ai+a_{i+\ell} is a multiple of dd. Let (i1,i2,,ik)(i_1, i_2, \dots, i_k) be all indexes of numbers in the given sequence that are multiples of dd, written in ascending order. Note that each pair ij<isi_j < i_s of indices yields dd twice: for =sj\ell = s - j and for =j+ns\ell = j + n - s. Therefore dd will occur as the greatest common divisor exactly 2(k(k1)2)2\left(\frac{k(k-1)}{2}\right) times and by assumption this number is n1n-1. Thus n=1+2(k(k1)2)=k2k+1n = 1 + 2\left(\frac{k(k-1)}{2}\right) = k^2 - k + 1. The assertion is proved.

b) The equation k2k+1=2021k^2 - k + 1 = 2021 is equivalent to k(k1)=2020k(k-1) = 2020. The left side of this equation increases for k>0.5k > 0.5 while 9089=801090 \cdot 89 = 8010 and 9190=819091 \cdot 90 = 8190, therefore this equation doesn't have a positive integer solutions. According to the proven statement, the answer at this item is: "no".

a) Note that 21=525+121 = 5^2 - 5 + 1, i.e. n=21n = 21 satisfies the statement for k=5k = 5. It is easy to construct the sequence (i1,i2,i3,i4,i5)(i_1, i_2, i_3, i_4, i_5) from the proof of this statement, for example (1,11,13,18,19)(1, 11, 13, 18, 19). Let us set a1=a2=a3==a21=1a_1 = a_2 = a_3 = \dots = a_{21} = 1 then choose 2020 different primes p1>p2>>p20p_1 > p_2 > \dots > p_{20} and for each ii from 11 to 2020 multiply by pip_i the numbers ai,ai+10,ai+12,ai+17,ai+18a_i, a_{i+10}, a_{i+12}, a_{i+17}, a_{i+18}. It is easy to see that for each \ell from 11 to 2020 the set of greatest common divisors from the problem statement coincides with the set {p1,p2,,p20}\{p_1, p_2, \dots, p_{20}\}.

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.