алгебра - Найти три последние цифры числа

Найти последние три десятичные цифры означает нахождение остатка по модулю 1000. Это значит, что 2003 можно заменить на 3 в силу свойств сравнений, которые можно возводить в натуральную степень.

Поскольку $%\varphi(1000)=\varphi(2^3)\varphi(5^3)=(2^3-2^2)(5^3-5^2)=400$%, из теоремы Эйлера следует, что $%3^{400}\equiv1\pmod{10^3}$%. Следует установить, какой остаток от деления на 400 даёт показатель степени, то есть число $%2002^{2001}$%. Если он равен $%r$%, то показатель степени имеет вид $%400q+r$%, и тогда $%3^{400q+r}\equiv(3^{400})^q3^r\equiv3^r\pmod{10^3}$%, и задача сводится к нахождению последних трёх цифр числа $%3^r$%.

Заметим, что $%2002\equiv2\pmod{400}$%, поэтому достаточно найти остаток от деления на 400 для числа $%2^{2001}$%. Здесь теорему Эйлера напрямую уже не применить, так как 400 и 2 не взаимно просты. Однако $%400=2^4\cdot5^2$%, поэтому можно отдельно найти остатки от деления на 16 и на 25. В первом случае ответ очевиден: остаток равен нулю, так как $%2^{2001}$% заведомо делится на $%2^4$%. А остаток от деления на 25 можно найти уже по теореме Эйлера, пользуясь тем, что $%\varphi(25)=20$%. Тогда $%2^{20}\equiv1\pmod{25}$%, откуда $%2^{2001}=(2^{20})^{100}\cdot2\equiv2\pmod{25}$%.

Таким образом, число $%2^{2001}$% при делении на 16 даёт в остатке 0, а при делении на 25 даёт в остатке 2. Из этих данных, в силу китайской теоремы об остатках, однозначно определяется остаток от деления на $%400=16\cdot25$%. Нас интересует число вида $%16m$%, где $%m$% целое, такое что $%16m\equiv2\pmod{25}$%. Сокращаем сравнение на 2, затем домножаем на 3, откуда $%-m\equiv24m\equiv3\pmod{25}$%. Тем самым, $%m\equiv22\pmod{25}$%, и $%16m\equiv16\cdot22\equiv352\pmod{400}$%.

Исходная задача в итоге свелась к нахождению последних трёх цифр числа $%3^{352}$%. Здесь пока что не очень удобно проводить вычисления, поэтому имеет смысл заметить, что $%10^3=2^3\cdot5^3$%, сводя задачу к нахождению остатков от деления на 8 и на 125.

Первая из задач решается совсем легко, потому что $%3^{352}\equiv9^{176}\equiv1\pmod8$% с учётом того, что 9 сравнимо с 1. Остаток от деления на 8, таким образом, равен 1. Для нахождения остатка от деления на 125 достаточно заметить, что $%\varphi(125)=100$%, и тогда мы можем перейти к числу $%3^{52}$%, "списывая" в показателе число, кратное значению функции Эйлера. Чтобы не возводить число в такую высокую степень, можно заметить, что речь идёт о числе $%(3^4)^{13}$%, то есть $%81^{13}$%. Здесь уже остаток вычисляется сравнительно легко при помощи последовательных возведений в квадрат: $%81^2\equiv6561\equiv61\pmod{125}$%; $%81^4\equiv61^2\equiv3721\equiv96\pmod{125}$%; $%81^8\equiv96^2\equiv9216\equiv91\pmod{125}$%. Отсюда $%81^{13}\equiv81^8\cdot81^4\equiv81^1\equiv91\cdot96\cdot81\equiv111\cdot81\equiv116\pmod{125}$%.

Теперь осталось найти число вида $%125n+116$%, дающее остаток 1 от деления на 8. Рассматривая числа указанной арифметической прогрессии, видим, что число 241 обладает нужным свойством. Таким образом, $%3^{352}\equiv241\pmod{10^3}$%, то есть искомыми тремя последними цифрами будут 241.