16-я Международная Жаутыковская олимпиада по математике, 2020 год

Натуральное число $n$ таково, что ни при каких натуральных $a$ и $b$ число $2^a3^b+1$ не делится на $n$. Докажите, что $2^c+3^d$ также не делится на $n$ ни при каких натуральных $c$ и $d$. ( А. Голованов )

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

Комментарии от администратора Комментарии от администратора №1.     Предположим противное: $2^c+3^d$ кратно $n$. Очевидно, $n$ не кратно 3. Тогда $3^k-1$ делится на $n$ для некоторого $k$. Выбрав $s$ так, что $ks>d$, мы получим, что $3^{ks-d}(2^c+3^d)=2^{c}3^{ks-d}+3^{ks}$ кратно $n$. Следовательно, число $2^{c}3^{ks-d}+1=2^{c}3^{ks-d}+3^{ks}-(3^{ks}-1)$ также кратно $n$ -- противоречие.

От противного пусть нашлись какие то $c;d$.

Очевидно, что $3 \nmid n$. Иначе $3 \mid n \mid 2^c+3^d \Rightarrow 3 \mid 2^c$ что невозможно.

По теоремe Эйлера $3^{\varphi (n)} \equiv 1 \pmod n$. Так же из условия

$-2^c \equiv 3^d \pmod n \Rightarrow -2^c \times 3 \equiv 3^{d+1} \pmod n $

И можно бесконечно домножать на $3$ пока там в степени тройки не возникнет число $d+k$ так, что $\varphi(n) \mid d+k$

Скажем $d+k=\varphi(n) m $

Тогда $-2^c3^k \equiv 3^{d+k}=3^{\varphi(n)m}=(3^{\varphi(n)})^m \equiv 1 \pmod n$

Но тогда $2^c3^k+1 \equiv 0 \pmod n$, что неверно по условию