Малая теорема Ферма
Если p простое и gcd(a, p) = 1, то aᵖ⁻¹ ≡ 1 (mod p). Fermat, 1640. Следствие: aᵖ ≡ a (mod p) для любого a. Применение: быстрое возведение в степень по модулю, тест простоты. Обобщение: теорема Эйлера для φ(n). Основа RSA-криптографии.
Малая теорема Ферма
Применения в арифметике по модулю
Малая теорема Ферма используется для вычисления обратного элемента по модулю простого числа и ускорения возведения в степень. Это базовый кирпич в криптографии и соревновательных алгоритмах.
Связь с функцией Эйлера
Малая теорема Ферма является частным случаем более общей теоремы Эйлера для взаимно простых чисел. Эта связь расширяет применимость результатов к составным модулям и задачам инверсии.