Question

Существуют ли большие числа, которые "не боятся" умножения?

Мы знаем, что 5*5=25, а 6*6=36, то есть последняя цифра у 5 и 6 при умножении сохраняется. Таким же свойством, конечно, обладают 0 и 1. Других однозначных чисел такого свойства не существует. Их всего четыре: 0,1,5 и 6.

Таким же свойством обладают некоторые двузначные числа:

25*25=625

76*76=5776

И даже одно трехзначное: 625*625=390625

А бывают ли четырехзначные числа, последние цифры которых при возведении в степень остаются неизменными? А пятизначные? А десятизначные? А пятидесятизначные? Сколько их, чему они равны и как называются такие числа?

Answer 1

Если рассматривать лишь последние n цифр числа, пренебрегая остальными, то есть, брать остаток от деления на 10^n, то у уравнения x*x=x помимо двух очевидных решений х=0 и х=1 имеются два нетривиальных решения:

2^(4^10(n-1))%10^n

и

5^(4^10(n-1))%10^n

Показатель степени 4^10(n-1) - это функция Эйлера от 10^n, а 2 и 5 - это делители числа 10 (основание нашей системы счисления).

Для человека этот расчет невероятно сложен, но не для компьютера. Посчитать это нетрудно при помощи пары команд для python:

pow(5,4 * 10^49,10^50)

pow(2,4*10^49,10^50)

(здесь знак ^ для python надо заменить двумя звездочками)

Имеем два ответа длиной в 50 знаков:

42576576769103890995­<wbr />893380022607743740081­<wbr />787109376

и

57423423230896109004­<wbr />106619977392256259918­<wbr />212890625

Вычисления можно и сократить, воспользовавшись особыми свойствами числа 5 в десятичной системе счисления:

pow(5,4*10^49,10^50) = pow(5,2^25,10^50), то есть, просто двадцать пять раз возвести 5 в квадрат, на каждом k-ом шаге беря в ответе лишь последние 2k знаков. (Намек на это решение заключен в самом вопросе, ведь 25 = 5*5, а 0625 = 25*25 - каждый квадрат даёт два новых знака.) Такой расчет при желании можно произвести даже вручную.

Таким образом мы получаем первый ответ:

57423423230896109004­<wbr />106619977392256259918­<wbr />212890625

Как же найти после этого второй?

А очень просто: дело в том, что если x^2=x, то (1-x)^2=1-x, и потому два искомых решения связаны простым соотношением: x+y=1+10^n.

А значит второе число находится из первого как простое дополнение до 9!

В самом деле, поглядите на эти два числа. Если их расположить друг над другом, то видно, что сумма верхней и нижней цифры всегда равна 9. Только последняя цифра на единицу больше:

42576576769103890995­<wbr />893380022607743740081­<wbr />787109376

57423423230896109004­<wbr />106619977392256259918­<wbr />212890625

Ну, и осталось произвести проверку:

42576576769103890995­<wbr />893380022607743740081­<wbr />787109376 * 42576576769103890995­<wbr />893380022607743740081­<wbr />787109376 =

18127648893753971252­<wbr />855355098819268321516­<wbr />6459225064257657676­<wbr />910389099589338002260­<wbr />7743740081787109376

а

57423423230896109004­<wbr />106619977392256259918­<wbr />212890625 * 57423423230896109004­<wbr />106619977392256259918­<wbr />212890625 =

32974495355546189261­<wbr />068595053603780841353­<wbr />0717037555742342323­<wbr />089610900410661997739­<wbr />2256259918212890625

Добавлю, что такие числа называются автоморфными.