페르마의 소정리
페르마의 소정리 (Fermat’s little Theorem) 는 정수론의 주요 정리중 하나로, 내용은 다음과 같습니다.
1. 소수 $p$와 모든 자연수 $a$에 대하여 $a^{p} \equiv a \pmod{p}$이다.
2. 소수 $p$에 대하여 $p$와 $a$가 서로소 이면 $a^{p - 1} \equiv 1 \pmod{p}$이다.
페르마의 소정리 증명
보조정리 (모듈러 연산 성질)
$ab \equiv ac \pmod{p}$이고, $a$와 소수 $p$가 서로소이면 $b \equiv c \pmod{p}$이다.
$1$부터 $p - 1$까지의 수가 있는 집합 $S_{1} = \{ 1, 2, \cdots , p - 2, p - 1 \}$의 원소 각각에다가 $a$를 곱하면 $S_{2} = \{ 1a, 2a, \cdots , (p - 2)a, (p - 1)a \}$ 꼴이 된다.
만약 $ax \equiv ay \pmod{p}$이면 위의 보조정리에서 $x \equiv y \pmod{p}$여야만 하는데, 집합 $S_{1}$에서 $p$로 나누었을 때의 나머지가 서로 같은 원소가 없었으므로 $S_{2}$의 원소를 $p$로 나눈 나머지들도 나머지가 같을 수가 없다.
따라서 $S_{3} = \{ 1a \pmod{p}, 2a \pmod{p}, \cdots , (p - 2)a \pmod{p}, (p - 1)a \pmod{p} \}$라 하고, 이를 정렬하면 $1$부터 $p - 1$까지의 원소가 모두 한 번씩 나오게 된다. 이는 집합 $S_{1}$과 완전히 같다.
$S_{1} = S_{3}$이므로 $S_{1}$에 있는 원소들의 곱과 $S_{3}$에 있는 원소들의 곱이 같다는걸 알 수 있다.
또, $1$부터 $p - 1$까지의 정수가 $p - 1$개 있다.
$S_{1}$ 부분의 곱은 $\prod\limits_{k = 1}^{p - 1} k \pmod{p}$로 쓸 수 있고, $S_{3}$ 부분의 곱은 $\prod\limits_{k = 1}^{p - 1} ka \equiv a^{p - 1} \prod\limits_{k = 1}^{p - 1} k \pmod{p}$로 쓸 수 있다.
(합동식이 아니어도 $\prod\limits_{k = 1}^{p - 1} ka = a^{p - 1} \prod\limits_{k = 1}^{p - 1} k$은 성립한다.)
$S_{1}$의 곱과 $S_{3}$의 곱이 같으므로 $\prod\limits_{k = 1}^{p - 1} k \equiv a^{p - 1} \prod\limits_{k = 1}^{p - 1} k \pmod{p}$이라 할 수 있고, $1$부터 $p - 1$까지 모두 $p$와 서로소이므로 (서로소가 아니라면 그건 $p$가 애초에 소수가 아닌 것이다.) $1$부터 $p - 1$까지의 곱 또한 $p$와 서로소이다.
따라서 $K = \prod\limits_{k = 1}^{p - 1} k$라 하면 $K \equiv a^{p - 1} K \pmod{p}$이고, $K$가 $p$와 서로소이므로 $1 \equiv a^{p - 1} \pmod{p}$이다.
윌슨의 정리 는 A면 B이고 B이면 A다 라는 필요충분조건이 성립하지만, 2번 명제는 아쉽게도 역이 성립하지 않습니다.
즉, 서로소인 두 자연수 $a$, $n$ 에 대해 $a^{n - 1} \equiv 1 \pmod{n}$ 이라고 $n$이 소수인 것은 아닙니다.
$a = 2$인 경우, 즉 $2^{n - 1} \equiv 1 \pmod{n}$ 인데도 합성수인 $n$을 특별히 Poulet Number 라고 부르고, 그 외에는 "$a$를 밑으로 하는 (페르마)유사소수" 라고 부릅니다.
합성수 $n$과 서로소인 모든 $a$에 대해 $a^{n - 1} \equiv 1 \pmod{n}$ 를 만족하면, $n$을 카마이클 수 라고 부릅니다.
페르마의 소정리를 일반화한 오일러의 정리 도 존재합니다. $p$가 소수가 아니어도 성립합니다.
페르마의 소정리에 의해 법 $p$에서의 $a$의 모듈러 곱셈 역원 은 $a^{p - 2}$입니다.