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$ -- противоречие.