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

Докажите, что при некотором натуральном $n$ остаток от деления $3^n$ на $2^n$ больше $10^{2021}$. ( А. Голованов )

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

Рассмотрим $n=2^M$ такое, что $2^M>10^{2021}.$ Пусть $r$ является остатком при этом делении, тогда

$$v_2\big((3^n-1)-(r-1)\big)=v_2(3^n-r)\ge n,$$

но с другой стороны из $LTE$ очевидно следует, что $v_2(3^n-1)=M+2<n,$ откуда

$$v_2(r-1)=v_2(3^n-1)=M+2.$$

Понятно, что $r\neq 0,1,$ следовательно

$$r-1\ge 2^{M+2}>10^{2021}\implies r>10^{2021}.\quad\blacksquare$$

Пусть $3^n \equiv r_n \pmod{2^n}$ для всех $n\in\mathbb{N}$

Заметим, что $3\cdot 10^{2021} < 2^{1 000 000 000}$

Утверждение: Найдется такой $m \ge 1 000 000 000,$ что $3r_m \neq r_{m+1}.$

Док-во: От обратного пусть они равны для всех $m\ge 1 000 000 000.$

$$2^m \mid 3^m - r_m$$

$$2^{m+1} \mid 3^{m+1} - r_{m+1} \implies 2^{m+1} \mid 3^{m+1} - 3r_m \implies 2^{m+1} \mid 3^m - r_m $$

Делая аналогичным образом, получим, что $3^m - r_m$ делится на любое число вида $2^{m+k}$, где $k\in\mathbb{N},$ такое невозможно поскольку $3^m-r_m \neq 0.$

Далее легко выходить, что $3r_m \equiv r_{m+1} \pmod{2^m},$ откуда одно из $3r_m$ или $r_{m+1}$ больше $2^m$, что в свою очередь больше $3\cdot 10^{2021}\quad\blacksquare$

Замечание: Утверждение можно было и не доказывать а воспользоваться им против самой условий задачи следующим образом,

Если брать от обратного, то $3r_m = r_{m+1}$ для всех $m\ge 1 000 000 000$, тогда $r_{m+k} = 3^kr_m,$ для большого $k$ число $r_{m+k}$ очевидно больше $10^{2021}.$

Заметим, что остаток $3^k$ при делении на $2^k$ не меньше, чем остаток при делении $3^k$ на $2^n$($k\ge n$). Рассмотрим такие $n$, что $2^n$ больше $10^{2021}$. Предположим, что найдётся такое $k$, что $r$, остаток $3^k\pmod{2^n}$, удовлетворяет неравенству $10^{2021}<r<2^n$. Используя вышеприведённый факт, получаем, что остаток от деления $3^k$ на $2^k$ больше $10^{2021}$.

Если такого $k$ не найдется, это будет означать, что $r\le10^{2021}$, откуда $3^k$ принимает не более $10^{2021}$, следовательно по принципу Дирихле найдутся $k,l$, такие что $3^k\equiv3^l\pmod{2^n}\Leftrightarrow 3^{k-l}\equiv1\pmod{2^n}$, следовательно $d=ord_{2^n}(3^k)\le10^{2021}$ при любом $n$. Поскольку при увеличении $n$, показатель, очевидно, неубывает, то с одного момента он станет постоянным. Обозначим это конечное значение за $l$.

$3^l\equiv1\pmod{2^n}$, что неверно, при $2^n>3^l$.