Давненько у нас не было фактов про простые числа!
Исправим это недоразумение и поговорим о малой теореме Ферма.

Её формулировка звучит так:
Если p — простое число и a — целое число, которое не делится на p, то aᵖ⁻¹ ≡ 1 (mod p).
Если такая запись вам незнакома, советуем прочитать наш пост про арифметику остатков.

Чуть более простая формулировка теоремы: если p — простое число и a — целое число, которое не делится на p, то aᵖ⁻¹-1 нацело делится на p.

У данного факта существует довольно много доказательств: попроще и сильно посложнее. При желании можно посмотреть их тут и пообсуждать в комментариях к посту.

Чем может быть полезна эта теорема? Она помогает находить простые делители чисел или проверять, является ли число простым. Конечно, при маленьких значениях это можно выяснить и вручную, но для достаточно больших чисел проще воспользоваться теоремой. Также малая теорема Ферма используется для доказательства корректности алгоритма шифрования RSA. Ну и, конечно же, с её помощью можно находить остатки от деления!

Предлагаем вам почувствовать себя исследователями теории чисел и решить пару задач, используя малую теорему Ферма.

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

Ваши решения и ответы ждём под скрытым текстом.