46-я Международная Математическая OлимпиадаМексика, Мериде, 2005 год

Последовательность ${{a}_{1}}$, ${{a}_{2}}$, $\ldots $ определена следующим образом: ${{a}_{n}}={{2}^{n}}+{{3}^{n}}+{{6}^{n}}-1$ ($n=1,2,\ldots $). Найдите все натуральные числа, которые взаимно просты с каждым членом этой последовательности.

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

$Ответ:m=1$. Пусть это число $m$,$(m,a_n)=1$.

И пусть $p>3$ это любое простое число. Если $(k,p)=1$ для какого-то целого $k$ то $k^{p-2}\equiv k^{-1}\pmod {p}$ по малой теореме Ферма.

То есть $a_{p-2}=2^{p-2}+3^{p-2}+6^{p-2}-1\equiv \dfrac {1}{2}+\dfrac{1}{3}+\dfrac{1}{6}-1\equiv {0}\pmod{p}$.

Тогда для $m>1$ всегда найдется такой $n$ что $gcd(m,a_n)≥p$ (здесь $p$ какой-то простой делитель $m)$. Значит ответы: $m=1$.

А почему если m > 1 то у него есть простой делитель p > 3?

Докажем, что для каждого простого числа $p$ существует член последовательности, который делится на $p$. Рассмотрим случай, когда $n = p - 2$. Покажем, что в этом случае выполняется сравнение $2^{p-2} + 3^{p-2} + 6^{p-2} - 1 \equiv 0 \pmod p$.

Чтобы избежать работы с дробными степенями в модульной арифметике, умножим выражение на 6:

$$6(2^{p-2} + 3^{p-2} + 6^{p-2} - 1) = 3 \cdot 2^{p-1} + 2 \cdot 3^{p-1} + 6^{p-1} - 6$$

Пусть $p > 3$. Тогда $p$ взаимно просто с числами 2, 3 и 6. По малой теореме Ферма имеем $2^{p-1} \equiv 1 \pmod p$, $3^{p-1} \equiv 1 \pmod p$ и $6^{p-1} \equiv 1 \pmod p$. Подставим эти сравнения в наше выражение:

$$3 \cdot 2^{p-1} + 2 \cdot 3^{p-1} + 6^{p-1} - 6 \equiv 3(1) + 2(1) + 1 - 6 \pmod p$$

$$3 + 2 + 1 - 6 \equiv 0 \pmod p$$

Поскольку 6 и $p$ взаимно просты при $p > 3$, из условия $6(2^{p-2} + 3^{p-2} + 6^{p-2} - 1) \equiv 0 \pmod p$ строго следует, что:

$$2^{p-2} + 3^{p-2} + 6^{p-2} - 1 \equiv 0 \pmod p$$

Теперь отдельно проверим оставшиеся простые числа 2 и 3:

* При $p = 2$: выберем $n = 1$, тогда $2^1 + 3^1 + 6^1 - 1 = 10 \equiv 0 \pmod 2$.

* При $p = 3$: выберем $n = 2$, тогда $2^2 + 3^2 + 6^2 - 1 = 4 + 9 + 36 - 1 = 48 \equiv 0 \pmod 3$.

Вывод: Поскольку абсолютно любое простое число делит по крайней мере один из членов данной последовательности, не существует ни одного простого числа, которое могло бы входить в разложение гипотетического взаимно простого числа. Таким образом, единственным натуральным числом, взаимно простым со всеми членами последовательности, является 1.