정리. $p$로 나누어떨어지지 않는 모든 $a$에 대해 $a^p \equiv a \pmod p$입니다.
증명. (이해하는 데 필수적이지 않으므로 건너뛰어도 됩니다)
$$ \begin{aligned} a^p &= (\underbrace{1+1+\ldots+1+1}_\text{$a$ раз})^p \\ &= \sum_{x_1+x_2+\ldots+x_a = p} P(x_1, x_2, \ldots, x_a) & \text{(раскладываем по определению)} \\ &= \sum_{x_1+x_2+\ldots+x_a = p} \frac{p!}{x_1! x_2! \ldots x_a!} & \text{(какие слагаемые не делятся на $p$?)} \\ &\equiv P(p, 0, \ldots, 0) + \ldots + P(0, 0, \ldots, p) & \text{(все остальные не убьют $p$ в знаменателе)} \\ &= a \end{aligned} $$여기서 $P(x_1, x_2, \ldots, x_n) = \frac{k}{\prod (x_i!)}$는 다항 계수로, 괄호 $(a_1 + a_2 + \ldots + a_n)^k$를 전개했을 때 항 $a_1^{x_1} a_2^{x_2} \ldots a_n^{x_n}$이 나타나는 횟수입니다.
이제 결과를 $a$로 두 번 «나눕시다».
$$ a^p \equiv a \implies a^{p-1} \equiv 1 \implies a^{p-2} \equiv a^{-1} $$즉, $a^{p-2}$는 $a^{-1}$처럼 동작하며, 이것이 바로 우리에게 필요한 것입니다. $a^{p-2}$는 이진 거듭제곱을 이용하여 $O(\log p)$에 계산할 수 있습니다.
{{ Утверждение |Название=페르마의 소정리 |Показать название=1 |Утверждение=$p$를 소수, $a$를 $p$로 나누어떨어지지 않는 정수라고 합시다. 그러면 $a^{p - 1} \equiv 1 \mod p$입니다. |Доказательство= 수 $a, 2a, 3a, … ,(p - 1)a$를 생각해 봅시다. 이 집합에는 $1$부터 $p - 1$까지의 모든 나머지가 나타난다는 점에 주목하십시오(증명은 독자에게 연습 문제로 남깁니다).
이 수들을 서로 곱합시다. 좌변에는 수들이 원래 형태 그대로 남아 있고, 우변에서는 이 집합이 $1$부터 $p - 1$까지의 모든 나머지를 포함한다는 사실을 이용합니다.
$a \cdot 2a \cdot 3a \dots \cdot (p-1)a \equiv 1 \cdot 2 \cdot 3 \dots \ \cdot (p - 1) \mod p$
$(p-1)!a^{p-1} \equiv (p-1)! \mod p$
$p$는 소수이므로 $1$부터 $p - 1$까지의 모든 수와 서로소이며, 따라서 $(p - 1)!$과도 서로소입니다. 그러므로 등식의 양변에서 팩토리얼을 약분할 수 있습니다. 그러면 다음을 얻습니다:
$a^{p-1} \equiv 1 \mod p$. }}