Утверждение с числами

[Dave]

Keter в сообщении #748485 писал(а):

А эту маленькую деталь можно как-то обойти в рамках моих тривиальных рассуждений?

Пробуйте, может что-нибудь и выйдет. Но я по этому пути точно не пойду.

Keter в сообщении #748485 писал(а):

Но я не могу въехать как мы к этому пришли.

Вопрос, конечно, интересный. Наверно, долго смотрели на число $10$ и, наконец, поняли, что оно не простое, а раскладывается в произведение $10=2 \cdot 5$ , а у нас как раз $2$ возводится в степень, поэтому её нужно как-то отделить от $5$.

Keter в сообщении #748485 писал(а):

...чем нам это поможет. Почему на $5^n$? Что нам это даёт для задачи?

Прочитайте ещё раз внимательно п.3 выше, а также

Dave в сообщении #746940 писал(а):

Гипотеза. При любом натуральном $n$ целое число $t$ от $0$ до $10^n-1$ включительно является окончанием степени двойки некоторого целого числа $b \geqslant n$ тогда и только тогда, когда $\frac t {2^n}$ - целое число, не делящееся на $5$.
...т.к. при $n>1$ шаг между соседними "хорошими" $t$ не превосходит $2^{n+1}<10^{n-1}$...

[Keter]

Dave, помогите доказать, что остатки от деления $2^k$ на ${10}^a, k>a>1,$ представляют собой числа из множества $J \setminus W,$ где $J$ -- не более чем $a$-значные числа, кратные $2^a$, a $W$ -- не более чем $a$-значные числа, кратные $5$.

[Dave]

С которым из 3 шагов проблема?

[Keter]

В первом почему именно при $x=0,1,\dots,4\cdot 5^{n-1}-1$ ?
Я посмотрел, что вроде при любых $x>n>1$ делим $2^x$ на $10^n$ и получаем в остатке числа кратные $2^n,$ но не кратные пяти.

Еще не понятно, как $2^n<10^{n-1}/2$ показывает, что там может быть любая цифра?

[Dave]

Keter в сообщении #753117 писал(а):

В первом почему именно при $x=0,1,\dots,4\cdot 5^{n-1}-1$ ?

Потому что, по теореме Эйлера, $2^{\varphi(5^n)} \equiv 1 \pmod {5^n}$. Значит остатки начнут повторяться.

Keter в сообщении #753117 писал(а):

Еще не понятно, как $2^n<10^{n-1}/2$ показывает, что там может быть любая цифра?

Шагаем по числам, делящимся на $2^n$ и переступаем через те из них, которые делятся на $5$. Так как два таких числа подряд не могут делиться на $5$, то шаг максимум удвоится, т.е. составит максимум $2^{n+1}$. А $10^{n-1}$ - это длина того интервала, в который мы должны попасть (все числа, $n$-я цифра с конца которых есть $r$).

[Keter]

Dave, то есть потеореме Эйлера $2^{\varphi({10}^n)} \equiv 1 \pmod {{10}^n}$ ?
Тогда, доказав индукцией по $n$, что все числа $2^x,$ при $x=0, 1, 2, ..., 4 \cdot 5^{n-1},$ при делении на $10^n$ дают разные остатки, можно сказать, что все эти остатки представляют собой множество не более чем $n$-значных чисел кратных $2^n,$ но не кратных $5.$ А далее $2^{n+1}<{10}^{n-1},$ значит хотя бы два числа из множества кратных $2^n$ будут начинаться с какой либо цифры $c.$ Так как соседние, не делящееся на $5$, отстоят друг от друга на $2^n,$ то хотя бы одно из них не делится на $5.$ Это правильно?
Чего-то я с этой индукцией запутался окончательно...

[Dave]

Keter в сообщении #753366 писал(а):

Dave, то есть потеореме Эйлера $2^{\varphi({10}^n)} \equiv 1 \pmod {{10}^n}$ ?

Теорема Эйлера в теории чисел гласит: Если $a$ и $m$ взаимно просты...
Хотя бы вникли в формулировку, что ли. Именно поэтому мы не можем сразу изучать остатки от деления на $10^n$.

[Keter]

С Теоремой Эйлера я кажется разобрался.
Количество чисел от $1$ до $5^n,$ которые не взаимно просты с $5^n$ будет $5^{n-1}-1,$ тогда взаимно простых $5^n-1-(5^{n-1}-1)=5^n-5^{n-1}=4 \cdot 5^{n-1},$ то есть $\varphi(5^n)=4 \cdot 5^{n-1}.$
То есть остатки будут повторяться с периодом $4 \cdot 5^{n-1}.$

Наверное лучше так: $x=1, 2, ..., 4 \cdot 5^{n-1}, n>1.$

Остатки от деления $2^x$ на $5^2$ имеют период $T=20:$

$2, 4, 8, 16, 7, 14, 3, 6, 12, 24, 23, 21, 17, 9, 18, 11, 22, 19, 13, 1.$

Не понимаю, как тут индукцией воспользоваться? И самое главное: как же выглядит множество этих остатков???
$\{1, 2, 3, ..., 25\} \setminus \{5, 10, 15, 20, 25\}$

А что будет при бОльших $n$ ? Остатки будут множеством последовательных натуральных чисел $\Big($сколько именно, есть ли зависимость от $n,$ типа $1, 2, 3, ..., 4 \cdot 5^{n-1}+5(n-1)$ ?$\Big)$, исключая кратные пяти?

[Keter]

Вроде так: при $n=2$ у нас 24 последовательных натуральных числа без кратных пяти. При $n=3$ период будет $T=100.$ Пока мы последовательно дойдем до 100, встретим 20 чисел, кратных пяти, которые исключим, тогда последовательных, без кратных пяти будет 120, но пока дойдём до 120, встретим 105, 110, 115, 120, то есть еще четыре числа, кратных пяти. Результат: при $n=3$ остатки - это множество натуральных чисел от 1 до 125, без кратных 5.
А вот для $n=4, T=500$ остатки - от 1 до 625, без кратных пяти, то есть 500+ 125(предыдущее).
Откуда предположение, что остатки - это множество натуральных чисел от 1 до $5^n$ без кратных $5.$

Итого: остатки при делении $2^x, x=1, 2, ..., 4 \cdot 5^{n-1},$ на $5^n, n>1,$ различны и образуют множество $\mathbb{N} \setminus \{5m\}, 0<m<5^n$

[Dave]

Keter в сообщении #753807 писал(а):

Наверное лучше так: $x=1, 2, ..., 4 \cdot 5^{n-1}, n>1.$

Нет, случай $n=1$ нам пригодится в качестве базы индукции. Здесь придётся перебрать все остатки, чтобы увидеть, что они различны.

Keter в сообщении #753807 писал(а):

Остатки от деления $2^x$ на $5^2$ имеют период $T=20:$

$2, 4, 8, 16, 7, 14, 3, 6, 12, 24, 23, 21, 17, 9, 18, 11, 22, 19, 13, 1.$

Начинайте с $2^0$, так будет проще.

Keter в сообщении #753807 писал(а):

И самое главное: как же выглядит множество этих остатков???
$\{1, 2, 3, ..., 25\} \setminus \{5, 10, 15, 20, 25\}$

Здесь Вы на правильном пути, но $25$ лучше сразу выбросить из обоих множеств. А $0$ добавить. Ибо $25$ - не остаток от деления на $25$.

Keter в сообщении #753807 писал(а):

$...+5(n-1)$

А это что за хрень?

Keter в сообщении #753807 писал(а):

Не понимаю, как тут индукцией воспользоваться?

Вот это самый правильный вопрос.
С базой индукции (см. выше), я думаю, разберётесь. В шаге индукции предположите, что два остатка от деления $2^x$ и $2^y$ на $5^n$ совпадают при $x,y \in \{0,1,\dots,4 \cdot 5^{n-1}-1 \}$, $x \ne y$. Вначале докажите, используя результат для $n-1$, что отсюда следует $x \equiv y \pmod {4 \cdot 5^{n-2}}$, потом $2^{4 \cdot 5^{n-2} k} \equiv 1 \pmod {5^n}$, где $k$ - одно из чисел $1,2,3,4$. Далее воспользуйтесь биномом Ньютона для $2^{4 \cdot 5^{n-2} k}={16}^{5^{n-2} k}=(3 \cdot 5 +1)^{5^{n-2} k}$.

[Keter]

$n=1: \quad \quad x=0,1,2,3;$ числа $2^0, 2^1, 2^2, 2^3$ при делении на $5$ дают остатки соответственно $1,2,4,3.$ Длина периода делится на 4.

Пусть два остатка от деления $2^x$ и $2^y$ на $5^n$ совпадают при $x,y \in \{0,1,...,4\cdot5^{n-1}-1\}, x \ne y.$
Из $2^x \equiv 2^y \pmod {5^n},$ что равносильно $2^{x-y} \equiv 1 \pmod {5^n},$ следует $x \equiv y \pmod {4\cdot5^{n-1}}$

$n>1: \quad \quad 2^{4k\cdot5^{n-2}} \equiv 1 \pmod {5^n}.$

$16^{k \cdot 5^{n-2}} \equiv 1 \pmod {5^n}$ разложим по биному Ньютона:

$${(1+15)}^{k \cdot 5^{n-2}}-1=15k \cdot 5^{n-2}+15^2 k \cdot 5^{n-2} \cdot \dfrac{k \cdot 5^{n-2}-1}{2}+...$$

Все слагаемые, кроме первого заведомо делятся на $5^n,$ а первое - только если $k$ делится на $5.$

$k$ делится на $5.$ А что мы доказываем...? По теореме Эйлера зацикливание остатков возникает не позже, чем через $4\cdot5^{n-1}.$ А мы доказываем, что оно возникает не раньше, чем через $4\cdot5^{n-1} ?$


Dave, здесь в пункте (c) написано ( последнее предложение в (с) ), что если $2^x$ даёт разные остатки от деления на ${13}^2,$ то это справедливо и для ${13}^k.$
И мне вдруг стало интересно: что это за теорема у них?

[Dave]

Keter в сообщении #754827 писал(а):

Из $2^x \equiv 2^y \pmod {5^n},$ что равносильно $2^{x-y} \equiv 1 \pmod {5^n},$ следует $x \equiv y \pmod {4\cdot5^{n-1}}$

Именно это и нужно доказать в шаге индукции для $n$, пользуясь результатом для $n-1$.

Keter в сообщении #754827 писал(а):

А что мы доказываем...? По теореме Эйлера зацикливание остатков возникает не позже, чем через $4\cdot5^{n-1}.$ А мы доказываем, что оно возникает не раньше, чем через $4\cdot5^{n-1} ?$

Именно так, похоже, что здесь Вы уже это поняли, но исправлять вышеуказанный вывод почему-то не захотели.

Keter в сообщении #754827 писал(а):

здесь в пункте (c) написано ( последнее предложение в (с) ), что если $2^x$ даёт разные остатки от деления на ${13}^2,$ то это справедливо и для ${13}^k.$
И мне вдруг стало интересно: что это за теорема у них?

См. лемму 1.4.5 в книге Коэна.

[Keter]

То есть мы доказали, что зацикливание остатков происходит ровно через $4\cdot5^{n-1}-1.$
А откуда мы делаем вывод, что все остатки разные?

Dave в сообщении #754975 писал(а):

См. лемму 1.4.5
в книге Коэна.

Спасибо!

[Dave]

Keter в сообщении #755378 писал(а):

А откуда мы делаем вывод, что все остатки разные?

А разве здесь нет доказательства? Нужно только подправить кое-где $n-1$ на $n-2$ и осмыслить написанное.

[Keter]

Dave,

Dave в сообщении #753365 писал(а):

Шагаем по числам, делящимся на $2^n$ и переступаем через те из них, которые делятся на $5$. Так как два таких числа подряд не могут делиться на $5$, то шаг максимум удвоится, т.е. составит максимум $2^{n+1}$. А $10^{n-1}$ - это длина того интервала, в который мы должны попасть (все числа, $n$-я цифра с конца которых есть $r$).

как можно эту идею оформить красиво? Я думал что-то вроде

$$r \cdot 10^{n-1} \le q \cdot 2^n < (r+1) \cdot 10^{n-1}$$

где $q$ не делится на $5.$ Тогда $q \cdot 2^n = \beta, \gcd (\beta, 5)=1,$ значит, существует $x \ge n,$ что $2^x \equiv \beta \pmod {5^n}.$ На $2^n$ делится $\beta$ и $2^x,$ значит, $2^x \equiv \beta \pmod {2^n}.$ Откуда $2^x \equiv \beta \pmod {10^n},$ то есть $n$ цифр с конца у $\beta$ и у $2^x$ одинаковые. Тогда $n$-ая цифра с конца $2^x$ и есть $r.$