페르마의 소정리

수론에서 페르마의 소정리(Fermat小定理, 영어: Fermat’s little theorem)는 어떤 수가 소수일 간단한 필요 조건에 대한 정리이다. 추상적으로, 소수 크기의 유한체 위의 프로베니우스 사상이 항등 함수임을 의미한다.

정의

$p$ 가 소수이고, $a$ 가 정수라고 하자. 페르마의 소정리에 따르면, 법 $p$ 에서 $a^{p}$ 와 $a$ 는 서로 합동이다.

a^{p}\equiv a{\pmod {p}}

위 식은 $p\mid a$ 일 때 자명하게 성립한다. 만약 $p\nmid a$ 일 경우, 양변을 약분하여 다음과 같이 쓸 수 있다.

a^{p-1}\equiv 1{\pmod {p}}\qquad (a\neq 0)

이는 모든 소수가 만족시키는 필요조건이지만, 충분조건이 아니다. 즉, 페르마의 소정리에 나타난 합동식을 만족하는 수가 반드시 소수가 되지는 않는다.

a^{b-1}\equiv 1{\pmod {b}}

를 만족하면서 소수가 아닌 $b$ 를, $a$ 를 밑수로 하는 카마이클 수라고 부른다.

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

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

$a$ 와 서로소인 소수 $p$ 에 대해 $a,\ 2a,\ 3a,\ \cdots \ ,\ (p-1)a$ 인 $p-1$ 개의 수를 살펴보자. 이 수들을 $p$ 로 나눴을 때 나오는 나머지는 모두 다르다.
- 증명 : 귀류법으로, 두 수 $ia$ 와 $ja$ 가 존재해서 그 나머지가 같다고 하자( $0<i<j<p$ 인 정수). 그렇다면 그 두 수의 차 $(j-i)a$ 는 $p$ 로 나누어질 것이다. 그러나 $0<j-i<p$ 이므로 $j-i$ 는 $p$ 의 배수가 아니며, 문제의 가정에 따라 $a$ 는 $p$ 와 서로소이다.
- 따라서 같은 나머지를 가지는 수가 없으므로, $p-1$ 개의 수는 모두 그 나머지가 다르다.
또 $0<i<p$ 인 $i$ 에 대해 $ia$ 역시 $p$ 의 배수가 아니다. 이에 대한 증명은 위와 같으므로 생략한다.
이제 집합
$A=\left\{x|x=ia,\;i\in B\right\}$
를 정의하자. 이는 첫 번째에 가정한 $p-1$ 개의 수들의 집합이다. 여기서 집합
$B=\{1,\ 2,\ \cdots \ ,\ p-1\}$
인데, $p$ 와 서로소인 수를 $p$ 로 나눌 때 생기는 모든 나머지들의 집합이다. 처음에 했던 증명에 의해, $A$ 와 $B$ 의 크기는 같다.
따라서,
$a\times 2a\times 3a\times \cdots \times (p-1)a\equiv 1\times 2\times \cdots \times (p-1)\not \equiv 0{\pmod {p}}$
이다. 양변을 $(p-1)!$ 로 나누면,
$a^{p-1}\equiv 1{\pmod {p}}$
을 얻는다.

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

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

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

유한체 이론에서 다항식의 나눗셈에 관련된 결과를 통해 페르마의 소정리를 일반화할 수도 있다.^[1] 표수가 $p$ 인 유한체 $\mathbb {F} _{p^{r}}$ 에 대하여, 다음 두 명제가 성립한다.

기약 다항식 $g\in \mathbb {F} _{p^{r}}[x]$ 에 대하여, $g\mid x^{p^{n}}-x$ 라면 $\deg g\mid n$ 이다.
$k\mid n$ 인 두 양의 정수 $k,n\in \mathbb {Z} ^{+}$ 에 대하여, $C(p,k)$ 를 $g\mid x^{p^{n}}-x$ 인 k차 기약 다항식 $g\in \mathbb {F} _{p^{r}}[x]$ 들의 수라고 하자. 그렇다면

\sum _{j\mid k}jC(p,j)=p^{k}

이다.

여기서, 뫼비우스 반전 공식에 따라 C(p, k)를 얻는 일반적인 공식을 구하면 다음과 같다.

C(p,k)={\frac {1}{k}}\sum _{j\mid k}\mu (j)p^{k/j}

여기서 $\mu (j)$ 는 뫼비우스 함수이다.

↑ Joseph A. Gallian (2006), Contemporary Abstract Algebra, Houghton Mifflin Company(Boston, New York), p.388.

Golomb, Solomon W. (1956년 12월). “Combinatorial proof of Fermat’s “little” theorem”. 《The American Mathematical Monthly》 (영어) 63 (10): 718–718. doi:10.2307/2309563. JSTOR 2309563.
Alkauskas, Giedrius (2009년 4월). “A curious proof of Fermat’s little theorem”. 《The American Mathematical Monthly》 (영어) 116 (4): 362–364. arXiv:0801.0805. Bibcode:2008arXiv0801.0805A. JSTOR 40391097.

“Fermat's little theorem”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4.
Weisstein, Eric Wolfgang. “Fermat's little theorem”. 《Wolfram MathWorld》 (영어). Wolfram Research.