Домашние задания: Алгебра

Найдите остаток а) 53^(999) от деления на 323 б) 2^3^5^2021 от деления на 191

Найдите остаток а) 53^(999) от деления на 323 б) 2^3^5^2021 от деления на 191
А) mod 17:
53^999 = 2^999 = 2^(16*62 + 7) = 2^7 = 128 = 9
mod 19:
53^999 = -4^999 = -4^(18*55 + 9) = -4^9 = -2^18 = -1 = 18
=> 53^999 mod 323 = 17a+9 = 19b + 18, 19b mod 17 = 2b mod 17 = 9 - 18 = 8, b = 4, 19b + 18 = 94
Ludmila Vorontsova
Ludmila Vorontsova
96 935
Лучший ответ
б), буду пошагово использовать теорему Эйлера
НОД (2^3^5^2021, 191) = 1, ф (191) = 190
НОД (3^5^2021, 190) = 1, ф (190) = 1*4*18 = 72
НОД (5^2021, 72) = 1, ф (72) = (8-4)*(9-3) = 24
2021 = 84*24 + 5

Полетели в обратную сторону, ниже mod обозначает не сравнение по модулю, а остаток от деления.

5^2021 mod 72 = 5^5 mod 72 = 29
3^5^2021 mod 190 = 3^29 mod 190 = 143
2^3^5^2021 mod 191 = 2^143 mod 191 = 134

Остаток от деления 2^143 на 191 (и аналогичные выше) могу тебе предложить искать алгоритмом быстрого возведения в степень по модулю. Либо - отдельно искать остатки от деления на простые делители числа 191, как предложено выше.
На всё про всё уйдет несколько десятков минут арифметических упражнений,
Альтернатива вычислениям на бумажке - калькулятор/программа, при должном навыке программа пишется минут за 5.