2019-01-20
Последовательность натуральных чисел ${a_i}$ такова, что $\:НОД(а_i,а_j) = НОД(i,j)$ для всех $i \neq j$. Докажите, что $a_i = i$ для всех $i \in N$. (Через $(m, n)$ обозначен наибольший общий делитель натуральных чисел $m$ и $n$).
Решение:
Так как каждое $a_i$ делится на $НОД (a_i, a_{2i}) =\:НОД (i, 2i) = i$, то $a_i \vdots i$ для всех $i \in \mathbb{N}$. Предположим, что при некотором $i$ выполняется неравенство $a_i > i$. Тогда, с одной стороны, $\:НОД (a_{a_i}, a_i) =\:НОД (a_i, i) = i$, а с другой стороны, поскольку $a_{a_i}$ делится на $a_i$, то $\:НОД(a_i, a_{a_i}) = a_i > i$. Получили противоречие.