Олимпиада имени Леонарда Эйлера 2024-2025 учебный год, I тур дистанционного этапа

Дано натуральное число $n$. $n$-операция состоит в прибавлении к натуральному числу его остатка от деления на $n$. При каких натуральных $n$, больших 1, из каждого натурального числа за несколько $n$-операций получается число, кратное $n$? ( А. Голованов )

Комментарий/решение

При n = 2^k где к натуральное число.

Решение. Заметим, что если m = an + r, то разность чисел m + r = an + 2r и 2m = 2an + 2r делится на n, и потому остатки от деления этих чисел на n одинаковы. По-этому с точки зрения делимости на п, означающей равенство 0 остатка от деления на n, вместо n-операции можно рассматривать операцию умножения числа на 2. После к таких операций мы из числа m получим число 2^km. Если n = 2^k то это число будет делиться на n. Значит, все степени двойки нам подходят. С другой стороны, из m = 1 будут получаться только степени двойки, и делимости ни на какие другие числа не будет.