페르마의 소정리
페르마의 소정리 (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}입니다.