Задача 2. Прибавь свой остаток

Пробуем маленькие n

Сначала посмотрим, что происходит при небольших $n$.

• $n=2$. Чётное число уже кратно $2$. У нечётного числа остаток $1$, и после операции оно становится на $1$ больше — чётным. Подходит.

• $n=4$. Из $1$: $1\to 2\to 4$. Из $3$: $3\to 6\to 8$. Из $5$: $5\to 6\to 8$. Из $7$: $7\to 10\to 12$. Пока всё получается.

• $n=3$. Из $1$: $1\to 2\to 4\to 5\to 7\to 8\to 10\to\ldots$ Остатки от деления на $3$ идут так: $1, 2, 1, 2, 1, 2, \ldots$ Нуля нет, и похоже, что не будет никогда.

Числа растут, но это не помогает: важно не то, какое число, а какой у него остаток. Поэтому дальше будем следить за остатками. Заметим ещё: при $n=3$ остаток $1$ превращается в $2$, а $2$ — снова в $1$. Как именно новый остаток получается из старого?

Главное: остаток удваивается

Пусть число $x$ при делении на $n$ даёт частное $q$ и остаток $r$: $x=n\cdot q+r$, где $0\le r<n$. Операция прибавляет $r$:

Слагаемое $n\cdot q$ делится на $n$, поэтому остаток нового числа — это остаток числа $2r$. Так как $r<n$, то $2r<2n$: если $2r<n$, новый остаток равен $2r$, а если $2r\ge n$, то $2r-n$ (рисунок ниже).

Пример, $n=6$: $10=6\cdot 1+4$, после операции $14=6\cdot 1+8=6\cdot 2+2$. Остаток был $4$, стал $8-6=2$.

Скажем то же самое другими словами. Два числа дают одинаковый остаток при делении на $n$ тогда и только тогда, когда их разность делится на $n$. А

делится на $n$. Итак, после операции получается число с тем же остатком, что и у числа $2x$: с точки зрения остатков операция просто удваивает число.

Как до этого догадаться: в примерах шага 1 остатки менялись так: $1\to 2$, $2\to 4$ (или $2\to 1$ при $n=3$, потому что $4-3=1$) — это удвоение.

После k операций — как у числа 2^k · x

Обозначим числа, которые получаются из $x$, так: $x_0=x$, $x_1$ — после одной операции, $x_2$ — после двух, и так далее. По шагу 2 каждая разность $x_1-2x_0$, $x_2-2x_1$, $x_3-2x_2$, … делится на $n$.

Покажем, что $x_k-2^k\cdot x$ делится на $n$. Для $k=1$ это шаг 2. Для $k=2$:

Обе скобки делятся на $n$, значит, и сумма делится. Точно так же

делится на $n$, и так шаг за шагом: если $x_k-2^k x$ делится на $n$, то и $x_{k+1}-2^{k+1}x=(x_{k+1}-2x_k)+2\cdot(x_k-2^k x)$ делится на $n$.

Вывод: число $x_k$ кратно $n$ тогда и только тогда, когда $2^k\cdot x$ кратно $n$ — ведь они отличаются на число, кратное $n$. Теперь задача стала совсем другой: при каких $n$ для любого $x$ найдётся $k$, при котором $2^k\cdot x$ делится на $n$?

Степени двойки подходят

Пусть $n=2^m$ — степень двойки: $n=2, 4, 8, 16, \ldots$ Возьмём любое натуральное $x$ и сделаем $m$ операций. Число $2^m\cdot x$ делится на $2^m=n$, и по шагу 3 число $x_m$ отличается от него на кратное $n$. Значит, $x_m$ тоже делится на $n$.

Итак, при $n=2^m$ из любого числа не больше чем за $m$ операций получается число, кратное $n$. (Если кратное появилось раньше, дальше оно не меняется: остаток $0$, прибавлять нечего.)

Проверка на примере, $n=8$, $x=3$: $3\to 6\to 12\to 16$ — три операции, и $16=8\cdot 2$. Остатки: $3\to 6\to 4\to 0$, как у чисел $3$, $6$, $12$, $24$ (рисунок ниже).

Остальные n не подходят

Пусть $n$ — не степень двойки. Будем делить $n$ на $2$, пока делится; останется нечётное число $q$, и $q>1$ (иначе $n$ было бы степенью двойки). Число $q$ — делитель $n$. Например, для $n=6$ это $q=3$, для $n=12$ тоже $q=3$, для $n=10$ — $q=5$.

Возьмём начальное число $x=1$. По шагу 3 разность $x_k-2^k$ делится на $n$, а значит, и на $q$. Предположим, что какое-то $x_k$ кратно $n$. Тогда $x_k$ делится на $q$, и

тоже делится на $q$ как разность двух чисел, кратных $q$. Но $2^k=2\cdot 2\cdot\ldots\cdot 2$: в его разложении на простые множители только двойки, поэтому у него нет нечётных делителей, кроме $1$. Противоречие.

Значит, из числа $1$ никогда не получится число, кратное $n$, и такое $n$ не подходит. Пример, $n=6$: $1\to 2\to 4\to 8\to 10\to 14\to 16\to\ldots$, остатки $1, 2, 4, 2, 4, 2, \ldots$ — после третьей операции остаток $2$ повторился, и дальше остатки ходят по кругу $2\to 4\to 2$ (рисунок ниже).

Ответ: подходят ровно степени двойки: $n=2, 4, 8, 16, \ldots$, то есть $n=2^m$, где $m$ — натуральное число.