페르마의 소정리

페르마의 소정리(Fermat's little theorem, -小定理)는 페르마의 이름이 붙은 정리 가운데 하나이며, 그 내용은 다음과 같다.

p가 소수이고 a를 p의 배수가 아닌 자연수라 할 때, 즉, gcd(a,p)=1임이 성립할 때,

$a^{p-1} \equiv 1 \pmod{p}$

이 성립한다.

피에르 드 페르마의 이름이 붙어 있지만, 페르마는 이 정리를 언급했을 뿐, 정확한 증명을 제시하지는 않았다. 현재 기록상 남아 있는 증명 가운데 최초는 고트프리트 라이프니츠의 것이다.

증명 방법[편집]

페르마의 소정리를 증명하는 방법은 여러 가지가 있을 수 있지만, 가장 쉬운 방법으로 합동식을 이용하는 방법이 있다. 그 증명 방법을 나타내면 다음과 같다.

a와 서로소인 소수 p에 대해 a, 2a, 3a, ..., (p-1)a인 p-1개의 수를 살펴보자. 이 수들을 p로 나눴을 때 나오는 나머지는 모두 다르다.
증명 : 귀류법으로, 서로 같은 나머지를 가진 두 수, ia와 ja가 있다고 하자(0 < i < j < p인 정수). 그렇다면 이 두 수의 차는 p로 나누어질 것이다. 두 수의 차는 (j-i)a이다. 그러나 0<j-i<p이므로 j-i는 p와 서로소이며, 문제의 가정에 따라 a는 p와 서로소이다.
따라서 같은 나머지를 가지는 수가 없으므로, p-1개의 수는 모두 그 나머지가 다르다. 또 0 < i < p인 i에 대해 ia 역시 p의 배수가 아니다. 이에 대한 증명은 위와 같으므로 생략한다.
이제 집합 A = {x|x = ia, 단 i는 0 < i < p인 정수}를 만들자. 이는 첫 번째에 가정한 p-1개의 수들의 집합이다. 또 집합 B = {x|x는 0 < x < p인 정수}를 보자. 이는 p와 서로소인 수를 p로 나눌 때 생기는 모든 나머지들의 집합이다. 처음에 했던 증명에 의해, 집합 A의 모든 원소는 집합 B의 모든 원소에 일대일 대응될 수 있다.
a × 2a × 3a × ... × (p-1)a와 1 × 2 × 3 × ... × (p-1)은 법 p에 대해 합동이다. 또, 이는 p와 서로소이다. 따라서 합동식의 양변에서 1 × 2 × 3 × ... × (p-1)를 나눠줄 수 있다. 그러면 원하는 식, $a^{p-1} \equiv 1 \pmod{p}$ 이 나온다.

이 부분의 본문은 오일러의 정리입니다.

이 정리는 오일러 파이 함수를 이용하여, 소수가 아닌 정수 n에 대해서까지 다음과 같이 일반화할 수 있다. n이 자연수, a가 n과 서로소인 자연수일 때,

$a^{\varphi(n)} \equiv 1 \pmod{n}$

이 성립한다. 식에서 $\varphi(n)$ 는 오일러 파이 함수를 나타낸다.

유한체론에서 다항식의 나눗셈에 관련된 결과를 통해 페르마의 소정리를 일반화할 수도 있다.^[1] 이는 다음과 같이 쓸 수 있다.

$g(x)$ 가 기약이며 $x^{p^{n}} - x$ 을 나눈다면, $deg(g(x)) | n$ 이다.
어떤 n에 대해, $k | n$ 이고 기약이며 $x^{p^{n}} - x$ 을 나눈다는 조건을 만족하는 k차 다항식 $g(x)$ 의 개수를 $C(p, k)$ 라 정의하자. 그러면, $\sum_{j|k} jC(p, j) = p^{k} \qquad \frac{}{}$ 이다.