Maths Olympiad Prep

Library / /49 of 57

Number theory Difficulty 7.4 National olympiad, round 2 Prove it Russia

Let N>1N > 1 be an integer, and let d1<<dsd_1 < \dots < d_s be all its positive divisors (thus, d1=1d_1 = 1 and ds=Nd_s = N). Find all possible values of NN for which
gcd(d1,d2)+gcd(d2,d3)++gcd(ds1,ds)=N2.(A. Kuznetsov) \gcd(d_1, d_2) + \gcd(d_2, d_3) + \dots + \gcd(d_{s-1}, d_s) = N - 2. \quad (\text{A. Kuznetsov})

Саша выбрал натуральное число N>1N > 1 и выписал в строку в порядке возрастания все его натуральные делители: d1<<dsd_1 < \dots < d_s (так что d1=1d_1 = 1 и ds=Nd_s = N). Затем для каждой пары стоящих рядом чисел он вычислил их наибольший общий делитель; сумма полученных s1s-1 чисел оказалась равной N2N-2. Какие значения могло признать NN? (А. Кузнецов)

Solutions — 2

Solution 1

N=3N = 3.

Notice that gcd(di,di+1)di+1di\gcd(d_i, d_{i+1}) \le d_{i+1} - d_i; thus, denoting ri=(di+1di)gcd(di,di+1)0r_i = (d_{i+1} - d_i) - \gcd(d_i, d_{i+1}) \ge 0 we get r1++rs1=1r_1 + \dots + r_{s-1} = 1, so rk=1r_k = 1 for some kk, and ri=0r_i = 0 for iki \ne k; this yields that dk+1dk=2d_{k+1} - d_k = 2 and that dk,dk+1d_k, d_{k+1} are odd. If ks/2k \ne s/2, then rsk0r_{s-k} \ne 0 as well, which is impossible. Thus N=dkdk+1N = d_k d_{k+1} is odd, so that rs12N3N3r_{s-1} \ge \frac{2N}{3} - \frac{N}{3}; this yields N=3N = 3.

Solution 2

N=3N = 3.

Заметим сразу, что ds+1i=N/did_{s+1-i} = N/d_i при всех i=1,2,...,si = 1, 2, ..., s.

НОД(d1d_1, d2d_2) + НОД(d2d_2, d3d_3) + ... + НОД(ds1d_{s-1}, dsd_s) = N2N - 2. Вычитая из первого равенства второе, получаем r1+...+rs1=1r_1 + ... + r_{s-1} = 1. Это означает, что rk=1r_k = 1 для некоторого k, а все остальные rir_i равны пулю.
Итак, 1=(dk+1dk)НОД(dk,dk+1)1 = (d_{k+1} - d_k) - \text{НОД}(d_k, d_{k+1}). Правая, а потому и левая часть этого равенства делится на \text{НОД}(dkd_k, dk+1d_{k+1}), поэтому \text{НОД}(dkd_k, dk+1d_{k+1}) = 1 и dk+1dk=2d_{k+1} - d_k = 2. Это возможно, только если каждое из чисел dkd_k и dk+1d_{k+1} нечётно.

НОД(dm,dm+1)=NНОК(dk,dk+1)=NНОД(dk,dk+1)dkdk+1<N(dk+1dk)dkdk+1=dm+1dm. \text{НОД}(d_m, d_{m+1}) = \frac{N}{\text{НОК}(d_k, d_{k+1})} = \frac{N \cdot \text{НОД}(d_k, d_{k+1})}{d_k d_{k+1}} < \frac{N(d_{k+1} - d_k)}{d_k d_{k+1}} = d_{m+1} - d_m.

Значит, rm>0r_m > 0, что возможно лишь при k=mk = m (и, следовательно, s=2ks = 2k).
Итак, dk+1=Ndkd_{k+1} = \frac{N}{d_k}, то есть число N=dkdk+1N = d_k d_{k+1} нечётно. Но тогда ds1N3d_{s-1} \le \frac{N}{3}, откуда \text{НОД}(ds1d_{s-1}, dsd_s) ds1N3\le d_{s-1} \le \frac{N}{3}. Следовательно, 1rs12N3N3=N31 \ge r_{s-1} \ge \frac{2N}{3} - \frac{N}{3} = \frac{N}{3}, т. е. N3N \le 3. Поскольку N>1N > 1,

получаем единственно возможное значение N=3N = 3, которое, как легко убедиться, удовлетворяет условию.

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.