Автоморфные числа

Определение 1. Число a называют автоморфным, если его квадрат оканчивается цифрами самого числа a.

Записать это на языке математики можно так: 10ⁿ|(a²−a), то есть число 10ⁿ является делителем (a²−a). Или так:

$$a^2=a\pmod{10^n},$$(1)

то есть остаток от деления a² на 10ⁿ равен a, где n — количество цифр в числе а. Для удобства мы несколько изменим обозначение и будем считать, что запись $$a\,{\rm mod}\,b$$ означает остаток от деления a на b. Тогда определение 1 будет выглядеть так:

$$a^2\,{\rm mod}\,10^n=a.$$(1a)

Первые автоморфные числа можно отыскать по таблице квадратов, например: 5, 6, 25, 76. Проверим, выполняется ли определение 1 для числа 76. 76²=5776, остаток от деления 5776 на 100 равен 76. Строго говоря, числа 0 и 1 тоже удовлетворяют определению 1. Но, как мы увидим далее, их свойства сильно отличаются от свойств остальных автоморфных чисел. Поэтому для 0 и 1 все формулируемые свойства можно оговорить особо и показать, что формально они остаются справедливы. Однако это будет выглядеть слишком искусственно. При доказательстве теорем числа 0 и 1 учитывать не будем.

Теорема 1. Пусть a — автоморфное число, состоящее из n цифр. Тогда если n>1, то число a mod 10ⁿ⁻¹ тоже автоморфное.

Доказательство. Число a можно представить в виде

где p — цифра, b<10ⁿ⁻¹. Нам нужно доказать, что b — автоморфно.
Поскольку a — автоморфное число, то по определению 1 верно выражение (1а). Если b<10ⁿ⁻¹, то a mod 10ⁿ⁻¹=b, и, исходя из (1), a² mod 10ⁿ⁻¹=b. Возведем (2) в квадрат:

a²=(b+10ⁿ⁻¹·p)²=b²+2·b·p·10ⁿ⁻¹+10²ⁿ⁻²·p.

Теперь возьмем остатки от деления на 10^n-1 от обеих частей. Для n>1 2n−2≥n−1, и поэтому остаток от деления правой части на 10^n-1 совпадает с остатком от деления b². Таким образом, мы получили, что

b² mod 10ⁿ⁻¹=a² mod 10ⁿ⁻¹=b,

то есть число b — автоморфное. Теорема доказана.

Эта теорема почти очевидна. Она означает, что, отбросив у  автоморфного числа старшие разряды, мы получим автоморфное число. Например, 76 — автоморфное число. Отбросив 7, мы получим 6. 6²=36, то есть 6 — тоже автоморфное число. Из этой теоремы можно сделать

Следствие 1. Пусть нам известны все автоморфные числа с количеством цифр, не превышающем n. Тогда новые автоморфные числа можно получить только дописыванием новых цифр к уже известным цифрам слева.

Кто-то может спросить: «Как некоторое, когда в теореме речь шла об отбрасывании одной цифры?» Перед ответом давайте посмотрим еще на несколько автоморфных чисел (их легко подобрать, используя калькулятор и вооружившись следствием 1): 5, 6, 25, 76, 376, 625, 9376, 90625... Среди однозначных, двузначных, трехзначных чисел есть два автоморфных числа (0 и 1 мы договорились не рассматривать). А вот четырехзначное и пятизначное число только одно. Шестизначных чисел снова два: 109376 и 890625. Здесь следует разъяснить одну условность. В обычных ситуациях нули перед числом ничего не означают, то есть, например, число 001=01=1. Посмотрим на число 625. 625²=390625, и  это число автоморфное. Но в квадрате 625 перед цифрой 6 стоит 0. То есть можно считать, что 0625 — это четырехзначное автоморфное число. Конечно, дописать 0 и сохранить автоморфность можно не у всякого числа. Так, 076²=5776, и 076 не будет автоморфным. Мы нашли неточность в теореме 1 и в ее доказательстве. Мы доказали, что b² mod 10ⁿ⁻¹=b, но не доказали, что (n−1) — количество цифр в числе b. Конечно, теорему 1 можно переформулировать более строго. Но  тогда она усложнится, усложнится и ее доказательство. Мы же этого делать не будем, тем более, что при таком подходе усложняются и другие свойства автоморфных чисел. Таким образом, примем

Замечание 1. Нули, стоящие слева в записи автоморфного числа, откидывать нельзя.

Учитывая это замечание, для нескольких первых автоморфных чисел можно заметить, что количество таких чисел с данным количеством знаков есть 2. Докажем это строго.

Теорема 2. С данным количеством знаков существует ровно 2 автоморфных числа.

Доказательство проведем по индукции. Для n=1 утверждение теоремы верно, так как 5 и 6 — автоморфны. Пусть число a — автоморфное с количеством цифр n>1. Тогда его квадрат можно представить в виде

где p — цифра, c — некое число. Согласно следствию 1, автоморфные числа с количеством цифр n+1 необходимо искать в  виде a+10ⁿ·b, где b — цифра. Возведем его в квадрат:

(a+10ⁿ·b)²=a²+2·a·b·10ⁿ+10²ⁿ·b².

Воспользовавшись (3), получим:

(a+10ⁿ·b)²=a+10ⁿ·p+10ⁿ⁺¹·c+2·a·b·10ⁿ+10²ⁿ·b².

Берем остаток от деления на n+1:

(a+10ⁿ·b)² mod 10ⁿ⁺¹=a+10ⁿ·p+2·a·b·10ⁿ mod 10ⁿ⁺¹.

Если a+10ⁿ·b — автоморфное, то (a+10ⁿ·b)² mod 10ⁿ⁺¹=a+10ⁿ·b, то есть

a+10ⁿ·p+2·a·b·10ⁿ=a+10ⁿ·b+10ⁿ⁺¹·x,

где x — некоторое число.

p+2·a·b=b+10·x,

p+2·a·b−b=10·x.

Рассмотрим два случая.
1) a оканчивается на 5, тогда получается, что p=b.
2) a оканчивается на 6, откуда следует, что p+b кратно 10.

Мы получили вполне определенную и единственную цифру b, которое можно приписать к автоморфному числу с количеством цифр n, чтобы получить автоморфное число с количеством цифр n+1. Вместе с тем, мы получили алгоритм для нахождения автоморфных чисел. Правда, он получился рекуррентным, то есть для нахождения n-ного числа необходимо знать (n−1)-е число. Мне не удалось получить алгоритм, позволяющий найти n-ное автоморфное число без нахождения предыдущих. Проиллюстрируем найденный алгоритм. 5²=25, 2 — очередная цифра в записи квадрата, поэтому 25 — тоже автоморфно. 76²=5776, 7 — очередная цифра, 7+3 кратно 10, поэтому 376 — автоморфное число.

По приведенным ранее примерам автоморфных чисел вы могли заметить интересное свойство:
5+6=11
25+76=101
625+376=1001
и т. д. Приведем строгое доказательство этого факта, для чего нам необходима

Теорема 3. 1) Если а — автоморфное число, оканчивающееся на 5, то
(a−1)² mod 10ⁿ — тоже автоморфное число.
2) Если а — автоморфное число, оканчивающееся на 6, то
(a−1)² mod 10ⁿ⁺¹ — тоже автоморфное число.

Доказательство. Рассмотрим разность между квадратом числа и самим числом.

(a−1)⁴−(a−1)² =((a−1)²−a+1)·((a−1)²+a−1)=(a²−3a+2)(a²−a).

(a²−a) кратно 10ⁿ.
Пусть а оканчивается на 5. Тогда (a²−3a+2) не кратно 10, а (a−1)² — четно, то есть (a−1)² mod 10ⁿ — автоморфное число, оканчивающееся на 6.
Пусть а оканчивается на 6. Тогда (a²−3a+2) кратно 10, поскольку 36-18+2=20 — кратно 10. (a−1)² кратно 5, то есть (a−1)² mod 10ⁿ⁺¹ — автоморфное число, оканчивающееся на 5. Теорема доказана.

Следствие 2. Сумма двух автоморфных чисел с  количеством цифр n есть 10ⁿ+1.

Доказательство. Пусть a и b — автоморфные числа, оканчивающиеся на 5 и на 6 соответственно. Тогда по теореме 3: b=(a−1)² mod 10ⁿ.

(a+b) mod 10ⁿ=a mod 10ⁿ + (a-1)² mod 10ⁿ=
=(a²−a+1) mod 10ⁿ=(a²−a) mod 10ⁿ+1=1,

a+b=x·10ⁿ+1,

где x — некоторое число. Так как a<10ⁿ, b<10ⁿ, то a+b<2·10ⁿ, то есть a+b=10ⁿ+1.

Следует заметить, что теорема 3 так же дает алгоритм для нахождения автоморфных чисел.

У автоморфных чисел есть и другие свойства. Например, из теоремы 2 можно доказать, что автоморфное число кратно 2ⁿ или 5ⁿ, где n — количество цифр.

В завершение я хочу привести 100-значное число, кратное 5. Используя теорему 1, из него можно получить все числа до 100 знаков, кратные 5, а так же, используя и следствие 2, кратные и 6.

a₁₀₀=3953007319
1081698029
3850989006
2166509580
8638110005
5742342323
0896109004
1066199773
9225625991
8212890625