Задача
NT-B2-M11-P015 Бесконечно много автоморфных чисел
Назовём число автоморфным, если его квадрат заканчивается десятичной записью самого числа. Докажите, что существует бесконечно много автоморфных чисел, отличных от \(0\) и \(1\).
Для каждого \(k\) решите сравнение \(x^2\equiv x\pmod{10^k}\) с помощью модулей \(2^k\) и \(5^k\).
Условие, что квадрат заканчивается теми же \(k\) цифрами, есть \(x^2\equiv x\pmod{10^k}\), то есть \(x(x-1)\equiv0\pmod{10^k}\). Так как \(10^k=2^k5^k\), а \(x\) и \(x-1\) взаимно просты, все множители \(2^k\) и \(5^k\) должны целиком попасть в один из двух соседних множителей.
Например, система \(x\equiv0\pmod{2^k}\), \(x\equiv1\pmod{5^k}\) имеет единственное решение по модулю \(10^k\) по CRT. Оно не равно одновременно \(0\) и \(1\). Для разных больших \(k\) получаются всё новые ненулевые неединичные остатки; иначе одно фиксированное число удовлетворяло бы \(x^2\equiv x\pmod{10^k}\) для бесконечно многих \(k\), что возможно только при \(x=0\) или \(x=1\). Значит, автоморфных чисел бесконечно много.
Решение можно упростить для класса, построив первые окончания: \(76,376,9376,\ldots\).