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$.

Скажем

$3^n=2^nb_n+a_n$ где $a_n<2^n$ $($т.е. $a_n-$ и есть остаток$)$

Предположим, что существует какой то $a_c$ который является максимумом среди всех $a$. (такой обязательно найдется если $a$-шки не бесконечно растут). Тогда возьмем какой то $d-2>c$, и понятно, что $2^c>a_c>a_d; a_{d+1};...; a_{2^c+d-2}$. Заметим, что среди чисел $a_d; a_{d+1};...; a_{2^c+d-2}$ повторяются хотя бы две. Потому что из $2^c>a_c>a_d; a_{d+1};...; a_{2^c+d-2}$ следует, что $2^c-2 \geq a_d; a_{d+1};...; a_{2^c+d-2}$ и еще количество чисел $a_d; a_{d+1};...; a_{2^c+d-2}$ будет $2^c-1$. Тогда пусть повторяются какие то $a_x=a_y \ (2^c+d-2 \geq x>y \geq d)$. Тогда получим $-(2^xb_x-3^x)=a_x=a_y=-(2^yb_y-3^y) \Rightarrow \\ 2^xb_x-3^x=2^yb_y-3^y \Rightarrow$

$2^xb_x-2^yb_y=3^x-3^y$

Тoгда очевидно, что $2^y(2^{x-y}b_x-b_y)=3^y(3^{x-y}-1) \Rightarrow 2^y \mid 3^{x-y}-1$.

Но по LTE $\nu_2(3^{x-y}-1)=\nu_2(2)+\nu_2(4)+\nu_2(x-y)-1$ (сразу взял когда $x-y$ четный, т.к. когда они нечетные там случай легко отпадает, потому что $y \neq 1$).Значит $\nu_2(x-y)+2 \geq y \Leftrightarrow \nu_2(x-y) \geq y-2 \Rightarrow 2^{y-2} \mid x-y$.

Значит $x-y \geq 2^{y-2}$. Вспомним факты $(2^c+d-2 \geq x>y \geq d)$ и $d-2>c$. Объединив получим, что $2^c-2 \geq x-y \geq 2^{y-2} \geq 2^{d-2} > 2^{c} \ \Rightarrow \ 2^c-2 \geq 2^{c}$. Противоречие.

Значит нету такого $a_c$. Тогда $a$-шки растут бесконечно (необязательно монотонно), и когда нибудь точно обойдут $10^{2021}$

Возьмем такие $T,S$ что $2^S>3^T>10^{2021}$

Тогда возьмем $n=2^S+T$

По LTE $V_2(3^n-3^T)=V_2(3^{2^S}-1)=S+2$ =>> $3^n = 3^T (mod 2^{S+2})$ но так как $n>S+2$=>> $3^n = r_n (mod 2^n)$ где $r_n \geq 3^T> 10^{2021}$