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

В этой заметке мы исследуем элементарными школьными методами свойства интересного множества чисел, которые называют автоморфными.

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

Записать это на языке математики для n-значного числа можно так: $$10^n|(a^2-a)$$, то есть число $$10^n$$ является делителем $$a^2-a$$. Или так:

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

то есть остатки от деления a и a² на $$10^n$$ совпадают (и равны a). Для удобства мы несколько изменим обозначение и будем считать, что запись $$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\,{\rm mod}\,10^{n-1}$$ тоже автоморфное.

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

$$a=b+10^{n-1}p,$$(2)

где p — цифра, $$b<10^{n-1}$$. Нам нужно доказать, что b — автоморфно.

Поскольку a — автоморфное число, то по определению 1 верно выражение (1а). Если $$b<10^{n-1}$$, то $$a\,{\rm mod}\,10^{n-1} = b$$, и, исходя из (1), $$a^2\,{\rm mod}\,10^{n-1} = b$$. Возведем (2) в квадрат:

$$a^2=(b+10^{n-1}p)^2=b^2+2bp\cdot 10^{n-1}+10^{2n-2}p.$$

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

$$b^2\,{\rm mod}\,10^{n-1} = a^2\,{\rm mod}\,10^{n-1} = 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^2\,{\rm mod}\,10^{n-1} = b$$, но не доказали, что в числе b количество цифр есть $$n-1$$. Конечно, теорему 1 можно переформулировать более строго. Но тогда она усложнится, усложнится и ее доказательство. Мы же этого делать не будем, тем более, что при таком подходе усложняются и другие свойства автоморфных чисел. Вместо этого примем следующее замечание.

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

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

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

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

$$a^2=a+10^np+10^{n+1}c,$$(3)

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

$$(a+10^nq)^2=a^2+2aq\cdot 10^n+q^2\cdot10^{2n}.$$

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

$$(a+10^nq)^2=a+10^np+10^{n+1}c+2aq\cdot 10^n+q^2\cdot10^{2n}.$$

Берем остаток от деления на $$10^{n+1}$$:

$$(a+10^nq)^2\,{\rm mod}\,10^{n+1}=a+10^np+2aq\cdot 10^n\,{\rm mod}\,10^{n+1}.$$

Если число $$a+10^nq$$ — автоморфное, то левая часть по определению совпадает с им самим, то есть

$$a+10^nq=a+10^np+2aq\cdot 10^n-x\cdot 10^{n+1},$$

где $$x=[2aq/10]$$ — целая часть от деления $$2aq\cdot 10^n$$ на $$10^{n+1}$$. Упрощаем:

$$q=p+2aq-10x\Rightarrow p+q(2a-1)=10x.$$

Рассмотрим два случая. Если a оканчивается на 5, тогда $$q=p$$. Если a оканчивается на 6, то $$2a-1$$ оканчивается на 1, откуда следует, что $$p+q$$ кратно 10, то есть $$q=10-p$$.

Мы получили вполне определенную и единственную цифру q, которую можно приписать слева к автоморфному числу с количеством цифр n, чтобы получить автоморфное число с количеством цифр $$n+1$$. Вместе с тем, мы получили алгоритм для нахождения автоморфных чисел. Правда, он получился рекурсивным, то есть для нахождения n-ного числа необходимо знать предыдущее. Мне не удалось получить алгоритм, позволяющий найти n-ное автоморфное число без нахождения предыдущих. Конечно, так как повторное возведение в квадрат дает следующую цифру автоморфных чисел, можно было бы написать формальное выражение вроде $$a_n=5^{2^{n-1}}\,{\rm mod}\,10^n$$. Но вычисление $$5^{2^{n-1}}$$ по смыслу и есть нахождение всех предыдущих таких чисел.

Проиллюстрируем найденный алгоритм. 5²=25, 2 — очередная цифра в записи квадрата, поэтому 25 — тоже автоморфно. 76²=5776, 7 — очередная цифра, 7+3 кратно 10, поэтому 376 — автоморфное число.

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

Теорема 3. 1) Если а — автоморфное число из n цифр, оканчивающееся на 5, то $$(a-1)^2\,{\rm mod}\,10^n$$ — тоже автоморфное число.
2) Если а — автоморфное число из n цифр, оканчивающееся на 6, то $$(a-1)^2\,{\rm mod}\,10^{n+1}$$ — тоже автоморфное число.

Доказательство. Рассмотрим разность между квадратом числа $$(a-1)^2$$ и самим числом.

$$(a-1)^4-(a-1)^2=\left((a-1)^2-a+1\right)\left((a-1)^2+a-1\right)=(a^2-3a+2)(a^2-a).$$

Второй множитель $$a^2-a$$ кратен $$10^n$$ по определению автоморфного числа. Разберемся теперь с первым множителем.

Пусть а оканчивается на 5. Тогда $$a^2-3a+2$$ не кратно 10. Это значит, что последние n цифр числа $$(a-1)^2$$ совпадают с цифрами в его квадрате, то есть $$(a-1)^2\,{\rm mod}\,10^n$$ — автоморфное число. Оно оканчивается на 6, так как $$(a-1)^2$$ четно.

Пусть а оканчивается на 6. Тогда $$a^2-3a+2$$ кратно 10, поскольку младший разряд дает выражение $$36-18+2=20$$, кратное 10. Это значит, что последние $$n+1$$ цифр числа $$(a-1)^2$$ совпадают с цифрами в его квадрате, то есть $$(a-1)^2\,{\rm mod}\,10^{n+1}$$ — автоморфное число. Оно оканчивается на 5, так как $$(a-1)^2$$ нечетно. Теорема доказана

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

Доказательство. Пусть a и b — автоморфные числа, оканчивающиеся на 5 и на 6 соответственно. Тогда по теореме 3 имеем $$b=(a-1)^2\,{\rm mod}\,10^n$$. Вычислим остаток от деления их суммы на $$10^n$$:

$$\begin{align*} (a+b)\,{\rm mod}\,10^n&=a\,{\rm mod}\,10^n+(a-1)^2\,{\rm mod}\,10^n=\\ &=(a^2-a+1)\,{\rm mod}\,10^n=\\&=(a^2-a)\,{\rm mod}\,10^n+1=1. \end{align*}$$

То есть сумму можно представить в виде $$a+b=10^nx+1$$, где x — некоторое целое число. Так как $$5\leq a<10^n$$, $$6\leq b<10^n$$, то $$11\leq a+b=10^nx+1<2\cdot 10^n$$, откуда x может быть только 1. Теорема доказана.

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

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

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

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