Можно ещё так попробовать, с опорой на теорему Эйлера.
Некоторые определения и свойства.
Теорема Эйлера. Если для чисел a и m, НОД(a, m) = 1, то a^{phi(m)} % m = 1, где % -- деление с остатком, phi(m) -- функция Эйлера.
Функция Эйлера phi(m) равна количеству натуральных чисел n <= m, таких, что НОД(m, n) = 1.
Некоторые свойства функции Эйлера:
- если НОД(m, n) = 1, то phi(m*n) = phi(m)*phi(n);
- если p -- простое число, то phi(p) = p-1;
- если p -- простое, то phi(p^n) = p^n - p^{n-1}.
Итак, требуется доказать, что существует число x, такое, что
27^x = t*10^5 + 1. (*)
Действительно, умножение на 10^5 равносильно приписыванию пяти нулей после числа, а прибавление единицы к этим нулям меняет последний пятый ноль на единицу и, т.о., даёт требуемый суффикс ...00001.
По определению остатка от деления, уравнение (*) можно переписать как
27^x % 10^5 = 1.
Это очень похоже на теорему Эйлера, но осталось проверить НОД(27, 10^5). Действительно, 27=3^3, 10^5=2^5 * 5^5, т.е. общих факторов у них нет и наибольший общий делитель равен НОД(27, 10^5) = 1, как и требуется. Значит, по теореме Эйлера, x = phi(10^5). Q.e.d.
Несмотря на то, что доказательство уже завершено, т.е. мы доказали, что искомая степень числа 27 существует, можно ещё вычислить её в явном виде. Для этого надо воспользоваться свойствами функции Эйлера (см. выше):
phi(10^5) = phi(2^5 * 5^5) = phi(2^5) * phi(5^5) =
= (2^5 - 2^4) * (5^5 - 5^4) = (32 - 16) * (3125 - 625) =
= 16 * 2500 = 40000.
Т.е., число 27^{40000} представимо в виде t*10^5 + 1 для некоторого t, а значит заканчивается в своей десятичной записи последовательностью цифр 00001. Само число 27^{40000} я не буду здесь приводить, потому что в нём, если я не ошибаюсь, 57255 цифр. :)
