Олимпиада Туймаада по математике. Младшая лига. 2018 год

Докажите, что для любого нечетного натурального $d > 1$ и натурального $m$ в последовательности $a_n = 2^{2^n}+ d$ найдутся два числа $a_k$ и $a_\ell$ ($k\ne \ell$), у которых наибольший общий делитель больше $m$. ( T. Hakobyan )

Комментарий/решение

Пусть $p$ — некоторый нечётный простой делитель числа $d > 1$. Выберем натуральное число $r$ настолько большим, чтобы $p^r > m$.

Поскольку $\gcd(2, p^r) = 1$, по теореме Эйлера справедливо сравнение $2^{\varphi(p^r)} \equiv 1 \pmod{p^r}$. Для нечётного простого $p$ значение функции Эйлера $\varphi(p^r) = p^{r-1}(p - 1)$ является чётным числом, поэтому его можно представить в виде $\varphi(p^r) = 2^s \cdot t$, где $s \ge 1$, а $t$ нечётно.

Выберем достаточно большое натуральное число $k$, удовлетворяющее условиям $k \ge s$ и $2^k \ge \varphi(p^r)$, а также условию $a_k = 2^{2^k} + d \equiv 0 \pmod{p^r}$ (такое $k$ существует в силу периодичности показателей двоек по модулю $p^r$).

Положим $\ell = k + t \cdot \varphi(2^s)$. Так как $k \ge s$, показатель $2^k$ делится на $2^s$. Тогда по теореме Эйлера для модуля $2^s$ получаем:

$$2^\ell = 2^{k + t \cdot \varphi(2^s)} = 2^k \cdot \left(2^{\varphi(2^s)}\right)^t \equiv 2^k \cdot 1^t = 2^k \pmod{\varphi(p^r)}$$

Из равенства остатков по модулю $\varphi(p^r)$ следует, что разность $2^\ell - 2^k$ делится на $\varphi(p^r)$, то есть $2^\ell = 2^k + M \cdot \varphi(p^r)$ для некоторого натурального $M$.

Сравнивая член $a_\ell$ с $a_k$ по модулю $p^r$, получаем:

$$a_\ell = 2^{2^\ell} + d = 2^{2^k + M \cdot \varphi(p^r)} + d = 2^{2^k} \cdot \left(2^{\varphi(p^r)}\right)^M + d \equiv 2^{2^k} \cdot 1^M + d = a_k \pmod{p^r}$$

Таким образом, оба числа $a_k$ и $a_\ell$ кратны $p^r$. Следовательно, их наибольший общий делитель также делится на $p^r$, откуда получаем:

$$\text{НОД}(a_k, a_\ell) \ge p^r > m$$

Что и требовалось доказать.