Малая теорема Ферма и теорема Эйлера: Фундамент теории чисел

Малая теорема Ферма и теорема Эйлера – это два важных результата в теории чисел, которые связывают числа с их остатками при делении на другие числа. Теорема Эйлера является обобщением малой теоремы Ферма, и обе они находят широкое применение в криптографии и других областях.

I. Малая теорема Ферма

Формулировка: Если $p$ — простое число, и $a$ — целое число, не делящееся на p, то $a^{p-1} \equiv 1 \left ( \textit{mod p} \right).$

Иными словами

Если взять любое число, которое не делится на простое число $p$ , возвести его в степень $p - 1$ , а затем разделить на $p$ , то остаток всегда будет равен 1.

Примеры

Пусть $a = 2$ , $p = 5$ . Тогда $2^{5-1} = 2^4 = 16$ . $16 \equiv 1 \left ( \textit{mod 5} \right )$ , так как 16 при делении на 5 дает остаток 1.
Пусть $a = 3$ , $p = 7$ . Тогда $3^{7-1} = 3^6 = 729$ . $729 \equiv 1 \left ( \textit{mod 7} \right )$ , так как 729 при делении на 7 дает остаток 1.

Следствия и применение

Если $a$ — целое число, то $a^p \equiv a \left ( \textit{mod p} \right )$ (вне зависимости от того, делится $a$ на $p$ или нет).
Малая теорема Ферма используется для проверки чисел на простоту (хотя это не является надежным методом проверки, так как существуют псевдопростые числа).
Она также используется для нахождения обратного элемента по модулю.

II. Теорема Эйлера

Формулировка: Если $a$ и $n$ — взаимно простые целые числа, то $a^{\phi(n)} \equiv 1\left ( \textit{mod n} \right ),$ где $\phi(n)$ — функция Эйлера, которая определяет количество целых чисел от 1 до $n$ , которые взаимно просты с $n$ .

Связь с малой теоремой Ферма

Теорема Эйлера является обобщением малой теоремы Ферма. Если $n$ — простое число, то $\phi(n) = n - 1,$ и теорема Эйлера превращается в малую теорему Ферма: $a^{p-1} \equiv 1\left ( \textit{mod p} \right ).$