Привет! Сегодня разберём решение двух задач из поста о малой теореме Ферма.
Напомним формулировку теоремы:

Если p — простое число и a — целое число, которое не делится на p, то
aᵖ⁻¹ ≡ 1 (mod p).

1) Найти остаток от деления числа 3¹⁰ на 11.

Здесь p=11. По нашей теореме любое число, которое не делится на 11 нацело, при возведении в 10 степень даст остаток 1 при делении на 11.
И раз 3 взаимно просто с 11 — теорема применима, поэтому сразу получаем ответ.
Ответ: 1

2) Найти остаток от деления числа 17⁸ на 7.

В данном случае p=7, поэтому давайте представим число 17⁸ как 289*17⁶, чтобы показатель был равен p-1, как в теореме. И раз 17 не делится на 7 нацело, можно применить теорему для множителя 17⁶.
Получим 17⁶ ≡ 1 (mod 7).
Также надо найти, с чем сравнимо 289 по модулю 7. Число 287 делится на 7 нацело, поэтому:
289 ≡ 2 (mod 7).
Значит, 289*17⁶ ≡ 2 (mod 7) * 1 (mod 7) = 2 (mod 7).
Ответ: 2