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

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

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

Пусть $\exists m:\text{ }(a_k, a_l)<m\text{, }\forall k \neq l$. Теперь рассмотрим множество $S$ простых чисел, которые делят хотя бы один $a_i$. Для каждого $p \in S$ рассмотрим последовательность $v_p(a_i)$. Пусть она неограниченна, тогда найдутся $i<j$, что $v_p(a_i), v_p(a_j)>X$ для $X$ такого, что $p^X\geq m$, но тогда $(a_i, a_j)>p^X\geq m$, противоречие. Пусть $|S|$ конечно, тогда степени вхождения каждого $p\in S$ ограничены, а значит ${a_n}$ сама по себе ограниченна, что, очевидно, не так. Теперь, раз $|S|$ бесконечно, выделим два подмножества $S$: ${p\in S_1: p\leq m}$ и ${p\in S_2: p>m}$. Заметим, что каждый член второго множества делит ровно один $a_i$, иначе НОД будет больше $m$. Рассмотрим достаточно большое $n$ (определим насколько оно большое чуть позже), тогда пусть $p| 2^{2^n}+d$ для какого то $p\in S_2$, тогда $p \nmid 2^{2^k}-2^{2^n}, \forall k>n$, пусть $2^{n+1} \nmid p-1$, тогда $p-1 = 2^ab$, где $2 \nmid b$ и $a\leq n$. Тогда выберем $k=\varphi(b)+n$, тогда $p-1| 2^k-2^n$, тогда $p| 2^{2^k}-2^{2^n}$, противоречие, откуда $p \equiv 1 (mod\text{ }2^{n+1}), \forall p|2^{2^n}+d, p\in S_2$. Теперь, $\displaystyle d \equiv 2^{2^n}+d \equiv \prod_{p\in S_1} p^{v_p(a_n)} (mod\text{ }2^{n+1})$, но это произведение ограничено, а $d$ фиксировано, значит выберем $n$ такой, что $2^{n+1}$ больше их обоих, тогда $\displaystyle d= \prod_{p\in S_1} p^{v_p(a_n)}$, тогда $d|2^{2^n}$, а значит $d=2^x$. Пусть $x=2^cd$, где $2\nmid d$, докажем тогда, что в последовательности ${2^{n-c}-d}, n>c$ найдутся два члена с НОДом, который больше любого наперед заданного числа. Аналогично прошлому рассуждению, предположив, что это неверно, можно показать, что множество простых, которые делят хотя бы один член этой последовательности, бесконечно, тогда рассмотрим достаточно большое $p|2^{n-c}-d$, тогда $p|2^{n+p-1-c}-d$, тогда их НОД хотя бы $p$, а мы могли выбрать его достаточно большим. Теперь мы рассматриваем НОДы чисел вида $2^x(2^{2^c(2^{n-c}-d)}+1)$, но если рассмотреть такие $t,s$, что $(2^{t-c}-d, 2^{s-c}-d)=r$ - достаточно большое нечетное число, то $(a_t, a_s)\geq 2^x(2^{2^cr}+1)$, что можно сделать большим $m$, откуда итоговое противоречие.