Задача про делимость

[Mikhail_K]

Эту олимпиадную задачу я придумал много лет назад, когда сам был школьником.
Я её нигде больше не встречал, но вполне допускаю, что она может оказаться хорошо известной или даже классической. С задачами на делимость я в целом не очень хорошо знаком.
Как бы вы стали её решать? Возможно, моё решение слишком экзотическое, хотя и простое.

Пусть $k,l\in\mathbb{N}$, $k\geq 2$. Докажите, что найдутся такие целые неотрицательные $m>n$, что число $k^m-k^n$ делится на $l$.

[lel0lel]

$k^n(k^{m-n}-1)$
Если $k,l$ взаимнопростые, то выберем $m-n=\varphi(l)$. Если $(k,l)=d<l$, то, возможно, что $l=td^s$, $s\geq 1$ и $k=ud$, причём $(t,u)=1$. В таком случае положим $n=s$, $m-s=\varphi(t)$.

[Mikhail_K]

lel0lel в сообщении #1570803 писал(а):

В таком случае положим $n=s$, $m-s=\varphi(t)$

Верно ли я понимаю, что Вы используете здесь теорему Эйлера и взаимную простоту $k$ и $t$?
Но, кажется, $k$ и $t$ не обязательно взаимно просты.

[mihaild]

Я чего-то не понимаю, видимо. Среди чисел $k^1, k^2, \ldots, k^{l + 1}$ у хотя бы двух одинаковые остатки по модулю $l$, их разность на $l$ делится.

[lel0lel]

Да. Мы предварительно, выбрав $m$ сократили в $l$ всё то, что мешало взаимной простоте $k, l$. Поэтому $k,t$ взаимнопростые

[Mikhail_K]

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

Среди чисел $k^1, k^2, \ldots, k^{l + 1}$ у хотя бы двух одинаковые остатки по модулю $l$, их разность на $l$ делится.

Да, не получилось из меня автора олимпиадной задачи. Конечно, Вы правы.

lel0lel в сообщении #1570812 писал(а):

Да. Мы предварительно, выбрав $m$ сократили в $l$ всё то, что мешало взаимной простоте $k, l$. Поэтому $k,t$ взаимнопростые

Не думаю. Если $k=12$, $l=18$, то $d=6$, $t=3$ и $k,t$ не взаимно просты.

[lel0lel]

Mikhail_K в сообщении #1570814 писал(а):

Если $k=6$, $l=18$, то $d=6$, $t=3$ и $k,t$ не взаимно просты.

Да, стоило поаккуратнее, но в целом почти очевидно, что выбрав большое $m$, после сокращения от $l$ остаётся либо единичка, либо взаимнопростое число с $k$.

[Mikhail_K]

Моё школьное доказательство основывалось на представлении числа $1/l$ в виде периодической дроби в $k$-ичной системе счисления и использовании формулы суммы бесконечной геометрической прогрессии.
Жаль, что у задачи нашлось гораздо более простое решение.

[ИСН]

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