Существуют ли большие числа, которые не боятся умножения?
Если рассматривать лишь последние 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
и
57423423230896109004
Вычисления можно и сократить, воспользовавшись особыми свойствами числа 5 в десятичной системе счисления:
pow(5,4*10^49,10^50) = pow(5,2^25,10^50), то есть, просто двадцать пять раз возвести 5 в квадрат, на каждом k-ом шаге беря в ответе лишь последние 2k знаков. (Намек на это решение заключен в самом вопросе, ведь 25 = 5*5, а 0625 = 25*25 - каждый квадрат даёт два новых знака.) Такой расчет при желании можно произвести даже вручную.
Таким образом мы получаем первый ответ:
57423423230896109004
Как же найти после этого второй?
А очень просто: дело в том, что если x^2=x, то (1-x)^2=1-x, и потому два искомых решения связаны простым соотношением: x+y=1+10^n.
А значит второе число находится из первого как простое дополнение до 9!
В самом деле, поглядите на эти два числа. Если их расположить друг над другом, то видно, что сумма верхней и нижней цифры всегда равна 9. Только последняя цифра на единицу больше:
42576576769103890995
57423423230896109004
Ну, и осталось произвести проверку:
42576576769103890995
18127648893753971252
а
57423423230896109004
32974495355546189261
Добавлю, что такие числа называются автоморфными.
