Автоморфные числа
Определение 1. Число a называют автоморфным, если его квадрат оканчивается цифрами самого числа a.
Записать это на языке математики можно так: 10n|(a2−a), то есть число 10n является делителем (a2−a). Или так:
$$a^2=a\pmod{10^n},$$(1)
то есть остаток от деления a2 на 10n равен a, где n — количество цифр в числе а. Для удобства мы несколько изменим обозначение и будем считать, что запись $$a\,{\rm mod}\,b$$ означает остаток от деления a на b. Тогда определение 1 будет выглядеть так:
$$a^2\,{\rm mod}\,10^n=a.$$(1a)
Первые автоморфные числа можно отыскать по таблице квадратов, например: 5, 6, 25, 76. Проверим, выполняется ли определение 1 для числа 76. 762=5776, остаток от деления 5776 на 100 равен 76. Строго говоря, числа 0 и 1 тоже удовлетворяют определению 1. Но, как мы увидим далее, их свойства сильно отличаются от свойств остальных автоморфных чисел. Поэтому для 0 и 1 все формулируемые свойства можно оговорить особо и показать, что формально они остаются справедливы. Однако это будет выглядеть слишком искусственно. При доказательстве теорем числа 0 и 1 учитывать не будем.
Теорема 1. Пусть a — автоморфное число, состоящее из n цифр. Тогда если n>1, то число a mod 10n−1 тоже автоморфное.
Доказательство. Число a можно представить в виде
a=b+10n−1·p, | (2) |
где p — цифра, b<10n−1. Нам нужно доказать, что b — автоморфно.
Поскольку a — автоморфное число, то по определению 1 верно выражение (1а). Если b<10n−1, то a mod 10n−1=b, и, исходя из (1), a2 mod 10n−1=b. Возведем (2) в квадрат:
a2=(b+10n−1·p)2=b2+2·b·p·10n−1+102n−2·p.
Теперь возьмем остатки от деления на 10n-1 от обеих частей. Для n>1 2n−2≥n−1, и поэтому остаток от деления правой части на 10n-1 совпадает с остатком от деления b2. Таким образом, мы получили, что
b2 mod 10n−1=a2 mod 10n−1=b,
то есть число b — автоморфное. Теорема доказана.
Эта теорема почти очевидна. Она означает, что, отбросив у автоморфного числа старшие разряды, мы получим автоморфное число. Например, 76 — автоморфное число. Отбросив 7, мы получим 6. 62=36, то есть 6 — тоже автоморфное число. Из этой теоремы можно сделать
Следствие 1. Пусть нам известны все автоморфные числа с количеством цифр, не превышающем n. Тогда новые автоморфные числа можно получить только дописыванием новых цифр к уже известным цифрам слева.
Кто-то может спросить: «Как некоторое, когда в теореме речь шла об отбрасывании одной цифры?» Перед ответом давайте посмотрим еще на несколько автоморфных чисел (их легко подобрать, используя калькулятор и вооружившись следствием 1): 5, 6, 25, 76, 376, 625, 9376, 90625... Среди однозначных, двузначных, трехзначных чисел есть два автоморфных числа (0 и 1 мы договорились не рассматривать). А вот четырехзначное и пятизначное число только одно. Шестизначных чисел снова два: 109376 и 890625. Здесь следует разъяснить одну условность. В обычных ситуациях нули перед числом ничего не означают, то есть, например, число 001=01=1. Посмотрим на число 625. 6252=390625, и это число автоморфное. Но в квадрате 625 перед цифрой 6 стоит 0. То есть можно считать, что 0625 — это четырехзначное автоморфное число. Конечно, дописать 0 и сохранить автоморфность можно не у всякого числа. Так, 0762=5776, и 076 не будет автоморфным. Мы нашли неточность в теореме 1 и в ее доказательстве. Мы доказали, что b2 mod 10n−1=b, но не доказали, что (n−1) — количество цифр в числе b. Конечно, теорему 1 можно переформулировать более строго. Но тогда она усложнится, усложнится и ее доказательство. Мы же этого делать не будем, тем более, что при таком подходе усложняются и другие свойства автоморфных чисел. Таким образом, примем
Замечание 1. Нули, стоящие слева в записи автоморфного числа, откидывать нельзя.
Учитывая это замечание, для нескольких первых автоморфных чисел можно заметить, что количество таких чисел с данным количеством знаков есть 2. Докажем это строго.
Теорема 2. С данным количеством знаков существует ровно 2 автоморфных числа.
Доказательство проведем по индукции. Для n=1 утверждение теоремы верно, так как 5 и 6 — автоморфны. Пусть число a — автоморфное с количеством цифр n>1. Тогда его квадрат можно представить в виде
a2=a+10n·p+10n+1·c, | (3) |
где p — цифра, c — некое число. Согласно следствию 1, автоморфные числа с количеством цифр n+1 необходимо искать в виде a+10n·b, где b — цифра. Возведем его в квадрат:
(a+10n·b)2=a2+2·a·b·10n+102n·b2.
Воспользовавшись (3), получим:
(a+10n·b)2=a+10n·p+10n+1·c+2·a·b·10n+102n·b2.
Берем остаток от деления на n+1:
(a+10n·b)2 mod 10n+1=a+10n·p+2·a·b·10n mod 10n+1.
Если a+10n·b — автоморфное, то (a+10n·b)2 mod 10n+1=a+10n·b, то есть
a+10n·p+2·a·b·10n=a+10n·b+10n+1·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-ное автоморфное число без нахождения предыдущих. Проиллюстрируем найденный алгоритм. 52=25, 2 — очередная цифра в записи квадрата, поэтому 25 — тоже автоморфно. 762=5776, 7 — очередная цифра, 7+3 кратно 10, поэтому 376 — автоморфное число.
По приведенным ранее примерам автоморфных чисел вы могли заметить интересное свойство:
5+6=11
25+76=101
625+376=1001
и т. д. Приведем строгое доказательство этого факта, для чего нам необходима
Теорема 3. 1) Если а — автоморфное число, оканчивающееся на 5, то
(a−1)2 mod 10n — тоже автоморфное число.
2) Если а — автоморфное число, оканчивающееся на 6, то
(a−1)2 mod 10n+1 — тоже автоморфное число.
Доказательство. Рассмотрим разность между квадратом числа и самим числом.
(a−1)4−(a−1)2 =((a−1)2−a+1)·((a−1)2+a−1)=(a2−3a+2)(a2−a).
(a2−a) кратно 10n.
Пусть а оканчивается на 5. Тогда (a2−3a+2) не кратно 10, а (a−1)2 — четно, то есть (a−1)2 mod 10n — автоморфное число, оканчивающееся на 6.
Пусть а оканчивается на 6. Тогда (a2−3a+2) кратно 10, поскольку 36-18+2=20 — кратно 10. (a−1)2 кратно 5, то есть (a−1)2 mod 10n+1 — автоморфное число, оканчивающееся на 5. Теорема доказана.
Следствие 2. Сумма двух автоморфных чисел с количеством цифр n есть 10n+1.
Доказательство. Пусть a и b — автоморфные числа, оканчивающиеся на 5 и на 6 соответственно. Тогда по теореме 3: b=(a−1)2 mod 10n.
(a+b) mod 10n=a mod 10n + (a-1)2 mod 10n=
=(a2−a+1) mod 10n=(a2−a) mod 10n+1=1,
a+b=x·10n+1,
где x — некоторое число. Так как a<10n, b<10n, то a+b<2·10n, то есть a+b=10n+1.
Следует заметить, что теорема 3 так же дает алгоритм для нахождения автоморфных чисел.
У автоморфных чисел есть и другие свойства. Например, из теоремы 2 можно доказать, что автоморфное число кратно 2n или 5n, где n — количество цифр.
В завершение я хочу привести 100-значное число, кратное 5. Используя теорему 1, из него можно получить все числа до 100 знаков, кратные 5, а так же, используя и следствие 2, кратные и 6.
a100=3953007319
1081698029
3850989006
2166509580
8638110005
5742342323
0896109004
1066199773
9225625991
8212890625