Возведение в степень Некоторые свойства модульной арифметики

Умножение

$a·b ≡ (a \pmod n · b \pmod n) \pmod n$

Доказательство:

Представим числа $a$, $b$ в виде $a = p_a·n + q_a$,

$b = p_b·n + q_b$,

$q_a = a \pmod n$

$q_b = b \pmod n$

$a·b ≡ (p_a·n + q_a)·(p_b·n + q_b) mod n$

Если раскрыть скобки и выбросить слагаемые кратные n (так как они на модуль не влияют), то выйдет

$a·b ≡ q_a·q_b \pmod n$

$a·b ≡ (a \pmod n·b \pmod n) \pmod n$

Можно применить эту схему для выражения ax mod n

ax ≡ (a mod n)x mod n

Малая теорема Ферма Малая теорема Ферма является частным случаем теоремы Эйлера для случая если n - простое число: aφ(p) ≡ 1 mod p

Как известно φ(p) = p − 1, тогда теорема Эйлера приобретает вид:

ap−1 ≡ 1 mod p

Для примера:

75−1 ≡ 1 mod 5

7·7·7·7 ≡ 1 mod 5

49·49 ≡ 1 mod 5

(49 mod 5)·(49 mod 5) ≡ 1 mod 5

4·4 ≡ 1 mod 5

16 ≡ 1 mod 5

1 ≡ 1 mod 5