Неограниченность некоторого множества натуральных чисел

[Markiyan Hirnyk]

Доказать, что множество сумм цифр десятичной записи чисел вида $2016^n$ , где $n$ - натуральное число, не ограничено сверху.

[worm2]

Нашёл похожую задачку: topic93937.html
Только там не 2016, а 2.
Но зато утверждается, что предел равен бесконечности, а это более сильно.

[Markiyan Hirnyk]

Спасибо. Ознакомился. Разбираю ваше доказательство (оно сложное и изложено тяжеловесно). Первое непонятное мне место

Цитата:

ну это легко доказывается, по Дирихле она хоть один раз, да повторится, а дальше никуда не денется с подводной лодки

Пожалуйста, разъясните.

[worm2]

Остатков от деления $2^n$ на $10^k$ (при фиксированном $k$) — ограниченное количество (в любом случае никак не больше $10^k$). Когда мы неограниченно увеличиваем $n$, рано или поздно cлучится, что $2^n \equiv 2^m \pmod{10^k}$ (принцип Дирихле). А поскольку остаток от деления $2x$ на $y$ полностью определяется остатком от деления $x$ на $y$, то и $2^{n+1} \equiv 2^{m+1} \pmod{10^k}$, и $2^{n+2} \equiv 2^{m+2} \pmod{10^k}$, и т.д., и последовательность замыкается сама на себя.

[Markiyan Hirnyk]

worm2 в сообщении #1170699 писал(а):

А поскольку остаток от деления $2x$ на $y$ полностью определяется остатком от деления $x$ на $y$, то и $2^{n+1} \equiv 2^{m+1} \pmod{10^k}$, и $2^{n+2} \equiv 2^{m+2} \pmod{10^k}$, и т.д., и последовательность замыкается сама на себя.

Не понял. Пожалуйста, изложите подробнее.

[mihaild]

Попробуйте доказать, что если $2^n \equiv 2^m \pmod{n}$, то $\forall k \geqslant 0: 2^{n + k} \equiv 2^{m+k} \pmod{n}$.

[Markiyan Hirnyk]

mihaild в сообщении #1170705 писал(а):

Попробуйте доказать, что если $2^n \equiv 2^m \pmod{n}$, то $\forall k \geqslant 0: 2^{n + k} \equiv 2^{m+k} \pmod{n}$.

Сформулированное вами утверждение ложно: положим $n=3,\,m=5,\,k=2.$ Мне не понятно, чем оно способствует решению задачи.

[mihaild]

Markiyan Hirnyk в сообщении #1170710 писал(а):

Сформулированное вами утверждение ложно: положим $n=3,\,m=5,\,k=2.$

$2^{3 + 2} = 32 \equiv 2 \pmod{3}$, $2^{5 + 2} = 128 \equiv 2 \pmod{3}$ (либо у меня опечатка, которую я в упор не вижу).

Правда я всё равно сформулировал более слабое утверждение, чем нужно - надо заменить модуль $n$ на произвольный.

[Lia]

mihaild
Конечно, нет опечатки. Утверждение устно доказывается для произвольного модуля, как Вы и заметили.

[Markiyan Hirnyk]

Я не прав. Как доказать уточнение сформулированного вами утверждения, не знаю. Можно ли $2$ заменить на $2016$? Например, на $10$ заменить нельзя.

[mihaild]

Заменить можно. Можно взять произвольное основание степени, и произвольный модуль.
Способствует это решению задачи тем, что мы хотим доказать, что последовательность $k^m \pmod{n}$ - периодическая.

Давайте переформулируем без степеней: $a \equiv b \pmod{c} \rightarrow ak \equiv bk \pmod{c}$. Распишите по определению, что значит сравнимость по модулю, и подумайте, как из определения вывести эту импликацию.

(Оффтоп)

Lia, в смысле опечатка в изначальной формуле. Мало ли, где-то $n$ и $m$ перепутал.

[Markiyan Hirnyk]

Спасибо, это место понял (Я - тугодум.). Буду разбирать доказательство дальше.

[worm2]

Прошу прощения, что устранился: очень хотелось спать

[Markiyan Hirnyk]

Оказалось,что этот вопрос является содержанием статей

Цитата:

C L Stewart, On the representation of an integer in two different bases, J Reine Angew Math 319 (1980) 63-72, MR 81j:10012
H G Senge, E G Straus, PV-numbers and sets of multiplicity, Proceedings of the Washington State University Conference on Number Theory (1971) 55-67, MR 47 #8452.

[Padawan]

Markiyan Hirnyk в сообщении #1170685 писал(а):

Доказать, что множество сумм цифр десятичной записи чисел вида $2016^n$ , где $n$ - натуральное число, не ограничено сверху.

Так как число $\lg 2016 $ иррационально, то $n\lg 2016\mod 1$ всюду плотно на отрезке $[0,1]$. Значит, $2016^n=10^{[n\lg 2016]}10^{\{n\lg 2016\}}$ может начинаться с любой последовательности цифр.