Как найти три последние цифры числа

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

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

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

Таким образом, число $%2^{2001}$% при делении на 16 даёт в остатке 0, а при делении на 25 даёт в остатке 2. Из этих данных, в силу китайской теоремы об остатках, однозначно определяется остаток от деления на $%400=16cdot25$%. Нас интересует число вида $%16m$%, где $%m$% целое, такое что $%16mequiv2pmod{25}$%. Сокращаем сравнение на 2, затем домножаем на 3, откуда $%-mequiv24mequiv3pmod{25}$%. Тем самым, $%mequiv22pmod{25}$%, и $%16mequiv16cdot22equiv352pmod{400}$%.

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

Первая из задач решается совсем легко, потому что $%3^{352}equiv9^{176}equiv1pmod8$% с учётом того, что 9 сравнимо с 1. Остаток от деления на 8, таким образом, равен 1. Для нахождения остатка от деления на 125 достаточно заметить, что $%varphi(125)=100$%, и тогда мы можем перейти к числу $%3^{52}$%, “списывая” в показателе число, кратное значению функции Эйлера. Чтобы не возводить число в такую высокую степень, можно заметить, что речь идёт о числе $%(3^4)^{13}$%, то есть $%81^{13}$%. Здесь уже остаток вычисляется сравнительно легко при помощи последовательных возведений в квадрат: $%81^2equiv6561equiv61pmod{125}$%; $%81^4equiv61^2equiv3721equiv96pmod{125}$%; $%81^8equiv96^2equiv9216equiv91pmod{125}$%. Отсюда $%81^{13}equiv81^8cdot81^4equiv81^1equiv91cdot96cdot81equiv111cdot81equiv116pmod{125}$%.

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

Мне тоже интересно, но данный раздел я не изучал.

Ну тогда нужно начать решать с задачек попроще
Начать с определения операций по модулю, обратного элемента по модулю и т.д.
То есть познакомиться с такой алгебраической структурой.

Дальнейшепе на процентов 50% будет, я думаю, совсем незнакомо и непонятно, но просто пропускай, не читая )

phi(100) = 40.

Это функция Эйлера – если совсем строго – то это число классов в мультипликативной группе Z*m. Применительно к теории чисел – числа, взаимнопростые с m и с меньшие m образуют мультипликативную группу по модулю m. А значит – phi(m) – число взаимопростых с m и меньшие m.

Интересное важное свойство: если (p,m)=1 и (t,m)=1, то их произведение тоже будет взаимопросто с m: (pt,m)=1
Можно проверить, что это действительно группа (алгебраическая структура с некоторыми свойствами).

Определение: число p взаимнопросто с m – значит их НОД(p,m)=1, или другая запись (p,m)=1
(НОД – наибольший общий делитель)

Для простого числа phi(p) = p-1, потому что все числа, меньшие с p, будут взаимопросты с простым числом.
Для составного – другая формула, предлагаю ее написать Pavlissimus

В частности, phi(100) = 40 – существует только 40 чисел, взаимопростых с 100. Я их даже перечислю:

1 3 7 9 11 13 17 19 21 23
27 29 31 33 37 39 41 43 47 49
51 53 57 59 61 63 67 69 71 73
77 79 81 83 87 89 91 93 97 99

Их ровно 40 и операция умножения по модулю не выводит из этого множества:
Пример: 43*79 = 3397 = 97 mod 100
97 – уже есть в этом списке.
Так на самом деле будет с любыми двумя числами.

Теорема Эйлера, если (r,m)=1, то r^phi(m) = 1 mod m

Если взять любое число из списка, то r^40 = 1 mod 100
Пример: 9^40 = 147808829414345923316083210206383297601 = 1 mod 100

�������

�����   a) 3 ��������� �����;   �) 6 ��������� ���� �����  1⁹⁹⁹ + 2⁹⁹⁹ + … + (10⁶ – 1)⁹⁹⁹.

�������

�)  k⁹⁹⁹ + (10⁶ – k)⁹⁹⁹ ≡ k⁹⁹⁹ + (– k)⁹⁹⁹ = 0 (mod 10⁶);  500⁹⁹⁹ ≡ 0 (mod 10⁶).

�����

�) ��� ����;  �) ����� �����.

��������� � ���������� �������������