페르마의 소정리

수론에서 페르마의 소정리(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$를 밑수로 하는 카마이클 수라고 부른다.

역사

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

증명

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

1. $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$개의 수는 모두 그 나머지가 다르다.
2. 또 $0<i<p$인 $i$에 대해 $ia$ 역시 $p$의 배수가 아니다. 이에 대한 증명은 위와 같으므로 생략한다.
3. 이제 집합

   $A=\left\{x|x=ia,\;i\in B\right\}$

   를 정의하자. 이는 첫 번째에 가정한 $p-1$개의 수들의 집합이다. 여기서 집합

   $B=\{1,\ 2,\ \cdots \ ,\ p-1\}$

   인데, $p$와 서로소인 수를 $p$로 나눌 때 생기는 모든 나머지들의 집합이다. 처음에 했던 증명에 의해, $A$와 $B$의 크기는 같다.
4. 따라서,

   $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)$는 오일러 파이 함수를 나타낸다.

유한체론

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

1. 기약 다항식 $g\in \mathbb {F} _{p^{r}}[x]$에 대하여, $g\mid x^{p^{n}}-x$라면 $\deg g\mid n$이다.
2. $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)$는 뫼비우스 함수이다.

참고 문헌

• 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.