Сайт Романа ПарпалакаЗаметкиНаучный калейдоскопАвтоморфные числа

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

7 ноября 2005 года

Определение 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

Поделиться
Посмотрите в блоге

Читайте также

Как додуматься до решения олимпиадной задачи?
Я иногда решаю «для себя» какие-нибудь сложные задачи по физике или математике. Практической пользы в этом нет, видимо, это мой способ проверить, что я всё еще не растерял форму.
2021
По мотивам нового движка блога
PHP меня радует такими вещами (хотя заслуги PHP в этом особой нет, это типичный синтаксис C):
2007
Опять Вебпланета
Еще одним источником бесконечного количества комбинаций являются иррациональные числа.
2009
Энциклопедия последовательностей целых чисел
Энциклопедия последовательностей целых чисел.
2006
Calc
Оказывается, что калькулятор Windows может считать факториалы от дробных чисел.
2008
Деление окружности на 5 частей
Разделим окружность на пять частей.
2005