[include(틀:정수론)]
[목차]
== 개요 ==
{{{+1 Fermat's little Theorem, FlT[* l은 L의 소문자이다. 대문자로 쓴 FLT는 [[페르마의 마지막 정리]]를 뜻한다.] · Fermat의 [[小]][[定]][[理]]}}}
>'''페르마의 소정리'''(Fermat's little Theorem)
>----
>[math(p)]가 소수이면, 모든 정수 [math(a)]에 대해 [math(a^p\equiv a\left({\rm mod}\ p\right))] 이다.
>혹은
>[math(p)]가 소수이고 [math(a)]가 [math(p)]의 배수가 아니면, [math(a^{p-1}\equiv 1\left({\rm mod}\ p\right))] 이다.

위 두 정리는 동치인 정리이다.

페르마의 소정리, 혹은 페르마의 작은 정리라고도 불리는 이 정리는 [[피에르 드 페르마]]가 알아낸 정리로서, [[정수론]]의 가장 기본이 되는 동시에 [[KMO]]를 응시하는 학생들 모두가 아는 4대 정리 중 하나다. [* 나머지는 [[오일러의 정리]], [[중국인의 나머지 정리]], [[윌슨의 정리]].] 역시 페르마답게 증명은 하지 않고 편지를 통해 이 정리에 대해 발표했지만, 그 사실 발견 자체가 놀라운 일이므로 페르마의 소정리라고 부른다.

한 마디로 임의의 소수 [math(p)]와 서로소인 한 수의 [math((p-1))]승을 [math(p)]로 나눈 나머지는 '''무조건''' [math(1)]이라는 정리. 눈으로 보이는 간결성만큼 효과도 매우 강력한 정리이다. 정수론에서 별 되도 않는 자명한 명제를 증명한답시고 붙잡고 있다고 '착각하던' 사람들도 [[합동식]] 개념을 접하는 동시에 4대 기본 정수론 정리들을 접하는 즉시 정수론에 대한 호기심이 급증한다고들 한다. [math(64^{70})]을 [math(71)]로 나눈 나머지는 [math(1)]이라는 것을 순식간에 알 수 있다. 더 나아가서 [math(64)]의 [math(70)]의 배수 거듭제곱을 [math(71)]로 나눈 나머지를 쉽게 구할 수 있다. 예를 들어 [math(64^{70000000})]을 [math(71)]로 나누면 나머지가 [math(1)]이라는 엄청난 결론을 낼 수 있다.

'''이 정리의 역은 성립하지 않는다.''' 자세한 내용은 후술.
== 증명 ==
=== [[수학적 귀납법]]과 [[이항정리]]를 사용한 증명 ===
먼저, 페르마의 소정리는 다음과 동치이다.
{{{#!wiki style="text-align: center"
[br][math(p\text{가 소수라면, }n^p\equiv n\pmod{p})]}}}
[math(n=0)]일 경우는 자명하다.

[[이항정리]]에 의하면
{{{#!wiki style="text-align: center"
[br][math(\displaystyle\left(n+1\right)^p=n^p+1+\sum^{p-1}_{n=1}{p\choose n})]}}}
여기서, [math(0<n<p)]이면
{{{#!wiki style="text-align: center"
[br][math(\displaystyle {p\choose n}={p\left(p-1\right)\cdots\left(p-n+1\right)\over n\left(n-1\right)\cdots 1})]}}}
은 [math(p)]의 배수이다. 따라서,
{{{#!wiki style="text-align: center"
[br][math(\left(n+1\right)^p\equiv n^p+1\pmod{p})]}}}
는 항상 성립하는 명제.
같은 방법으로
{{{#!wiki style="text-align: center"
[br][math(\left(n-1\right)^p\equiv n^p-1\pmod{p})]}}}
도 항상 성립한다. 이제, [math(n)]일 때 성립한다는 가정을 하면, [math(n+1, n-1)]일 때도 성립한다. 따라서, 모든 정수 [math(n)]에 대해 이 공식이 성립한다는 것을 알 수 있다.
=== 다항정리를 이용한 증명 ===
{{{#!wiki style="text-align: center"
[br][math(\displaystyle n^p=\left(\underbrace{1+\cdots +1}_{n}\right)^p=\sum_{x_1+\cdots+x_n=p}\frac{p!}{x_1!\cdots x_n!} \equiv\underbrace{\frac{p!}{p!0!\cdots 0!}+\cdots+\frac{p!}{0!0!\cdots p!}}_{n}\equiv n\pmod{p})]}}}

=== [[기약잉여계]]를 사용한 증명[* 이 방법은 [[오일러의 정리]]를 증명하는 방법과 같다.]  ===
먼저 [math(a)]와 [math(p)]가 서로소라고 하자. 이때 [math(1a,2a,\dots,(p-1)a)]는 [math({\rm mod}\ p)]에 대해 서로 합동이 아니다. 또한 이중에서 [math(p)]의 배수인 것은 없으므로, 이 [math(ka)]들을 [math(p)]로 나눈 나머지들의 집합은 [math(\{1,2,\dots,p-1\})]와 같다. 이때 전부 곱한 것을 생각하면 다음이 성립한다.
{{{#!wiki style="text-align: center"
[br][math(1a\cdot 2a\cdots(p-1)a\equiv 1\cdot 2\cdots(p-1)\pmod{p})]}}}
여기서 [math((p-1)!)]은 [math(p)]와 서로소이므로 양변에서 나누어 줄 수 있다. 따라서 [math(a^{p-1}\equiv 1\pmod{p})].

[[KMO]] 입문때 제일 많이 사용되는 방법이기도 하다.

=== 조합론을 사용한 증명 ===
구슬 숫자 [math(p)]개로 이루어진 목걸이를 생각해 보자. 이제 이 목걸이의 구슬을 색칠할 것인데 칠할 수 있는 색 종류는 [math(a)]개이다. 원순열 같은 것은 생각하지 않고 구슬을 위치마다 구분한다고 하면, 색칠 가능한 경우의 수는 [math(a^p)]이다(색 [math(a)]개에 구슬 [math(p)]개).

그런데 실제 목걸이는 원형이기 때문에 같은 목걸이를 회전시켜서 얻을 수 있는 경우가 [math(p)]가지 있고 위에서 단순 셈한 것은 이 목걸이를 다 다른 것으로 계산한 것이 된다. 예를 들어 [math(3)]개 구슬로 이루어진 목걸이를 흰검빨로 칠하는 경우를 생각해보면 '흰검빨, 검빨흰, 빨흰검'은 회전시켜보면 모두 같은 목걸이이다. 단, 모든 구슬이 완전히 같은 색깔로 칠해진 경우는 위에서 단순히 셈한 것이나 실제 목걸이나 한 가지로 계산되는데 이 방법은 색깔의 종류인 [math(a)]가지이다.

따라서 [math(a^p)] (단순 셈한 목걸이 숫자)에서 [math(a)]개(깡그리 같은 색깔로 칠해서 얻을 수 있는 목걸이 숫자)를 빼면 이는 [math(p)]의 배수가 되어야 한다.

모두 같은 색으로 칠해진 목걸이 [math(a)]개를 제외한 실제 목걸이 [math(1)]개에 대해 회전시켜서 얻을 수 있는 [math(p)]가지를 단순셈에서는 모두 다른 목걸이로 계산했기 때문에 전체 단순셈 목걸이 수에서 깡그리 같은 색인 목걸이 수를 빼면 [math(p)]의 배수가 되어야 한다. 즉, [math(a^p)]과 [math(a)]는 [math({\rm modulo}\ p)]에 대해 합동이다.

=== 집합의 분할을 이용한 증명 ===
다음과 같은 함수 집합 [math(F)]를 생각하자.
{{{#!wiki style="text-align: center"
[br][math(F=\left\{f|f:\mathbb{Z}_p\to\mathbb{Z}_a\right\})]}}}
그리고 이 집합 위의 동치관계를 다음과 같이 정의한다.
{{{#!wiki style="text-align: center"
[br][math(f\sim g\overset{\rm def}{\iff}\exists k\in\mathbb{Z}_p:\forall x:g\left(x\right)=f(x+k))]}}}
그러면 이 동치관계에 의한 [math(f)]의 동치류들을 모은 집합 [math(P:=\left\{[f]|f\in F\right\})]은 [math(F)]의 분할이 된다. 이때 [math(P)]에 속하는 집합들은 원소의 개수가 [math(1)]이거나 [math(p)]이다.

만약 [math(f\in F)]가 상수함수라면, [math(f\sim g)]일 때, [math(f=g)]일 수밖에 없다. 따라서 상수함수를 포함하는 집합은 원소의 개수가 [math(1)]이다.

한편 [math(f\in F)]가 상수함수가 아니라고 하자. 그러면 주어진 [math(f)]에 대해 [math(f(x),f(x+1),\dots,f(x+p-1))]는 모두 서로 다르게 된다. 왜냐하면 서로 다른 [math(a,b\in\mathbb{Z}_p)]에 대해 [math(f(x+a)=f(x+b))]일 경우, 모든 [math(n\in \mathbb{Z}_p)]에 대해 [math(f(0)=f\left((b-a)n\right))]이 성립한다. 그런데 [math(p)]가 소수이므로 여기서 [math((b-a)n)]은 [math(\mathbb{Z}_p)]의 모든 원소를 생성할 수 있다. 이는 [math(\forall x\in\mathbb{Z}_p:f(0)=f\left(x\right))]라는 뜻이 되어, [math(f)]가 상수함수가 아니라는 가정에 모순이다. 따라서 [math(f)]의 동치류를 [math(f(x),f(x+1),\dots,f(x+p-1))]로 쓸 수 있으므로 원소의 개수는 [math(p)]가 된다.

[math(F)]의 원소의 개수는 [math(a^p)]인데, 이 중 상수함수의 개수는 [math(a)]이다. 그리고 [math(F)]에서 상수함수를 제외한 집합은 '원소의 개수가 [math(p)]인 집합'들로 분할되므로 원소의 개수가 [math(p)]의 배수이다. 따라서
{{{#!wiki style="text-align: center"
[br][math(a^p-a\equiv 0\pmod{p})]}}}

== 합성수 판정에 사용 ==
이 명제의 대우는 다음과 같다.
>어떤 수 [math(n)]이 적당한 [math(a)]에 대해서 [math(a^n\not\equiv a\left({\rm mod}\ n\right))] 이면, [math(n)]은 합성수이다.
페르마의 소정리를 이용하면, 어떤 수가 소수인지를 확실하게 판정해 줄 수는 없지만, 저 조건을 만족하면 합성수임은 판정할 수 있다.
아래 설명하는 카마이클 수 때문에 소수 판정용으로 사용할 수 없다. 하지만, 소수 후보를 추려 내고, 이 후보들을 다른 소수 판정법을 이용하여 소수 판정을 하는데 사용하는 식으로 사용하는 것은 가능하다.

=== 페르마 유사소수 ===
>어떤 합성수 [math(n)]이 어떤 [math(a)]에 대해서 [math(a^{n-1}\equiv 1\pmod{n})]이면, [math(n)]을 페르마 유사소수(Fermat pseudoprime)이라고 부른다.
참고로 유사소수는 이것 말고도 [[https://ko.wikipedia.org/wiki/%EC%9C%A0%EC%82%AC%EC%86%8C%EC%88%98|여러 종류가 있다.]]

예를 들어 [math(341)] 같은 수가 있는데, [math(341=11\times 31)]로 합성수 이지만, [math(2^{341-1}\equiv 1\pmod{341})]을 만족한다. 하지만, [math(a=3)]인 경우를 확인해 보면 [math(3^{341-1}\equiv 56\pmod{341})]로 만족하지 않기 때문에, [math(341)]은 합성수임을 알 수 있다.

이러한 페르마 유사소수는 무한히 많다.

=== 카마이클 수 ===
페르마 유사 소수 중에서도 특이한 케이스로, 모든 정수 [math(a)]에 대해 [math(a^p\equiv a\left({\rm mod}\ p\right))]임에도 불구하고 [math(p)]가 합성수인 수이다. 이를 절대 유사 소수(absolute pseudoprime) 또는 이를 연구한 수학자 로버트 카마이클의 이름을 따서 '''카마이클 수'''(Carmichael number)라고 부른다.

카마이클 수 [math(n)]은, [math(n)]과 서로소이며[* [math(n)]과 서로소가 아닐 경우 나머지가 [math(1)]이 나오지 않을 것임은 자명하므로 제외하는 것이다.] [math(n)]보다 작은 모든 [math(a)]에 대해서 [math(a^{n-1}\equiv 1\pmod{n})]를 만족한다.

[[561|[math(561)]]][math((=3\times 11\times 17))], [math(1105)][math((=5\times 13\times 17))], [[1729|[math(1729)]]][math((=7\times 13\times 19))] 같은 수가 있다. [[http://oeis.org/A002997|목록 보기]]

카마이클 수는 페르마의 소정리를 이용한 소수 판정 방법의 절대적인 반례가 되기 때문에, 페르마의 소정리만으로는 소수 판정이 불가능하다.

처음에는 카마이클 수가 유한할 것으로 예상하여, 모든 카마이클 수의 목록을 정리하려고 시도하였다. 하지만, [[에르되시 팔]]은 카마이클 수가 무한히 많이 존재할 것이라고 예상하였고, 1994년 레드 알퍼드, 앤드루 그랜빌, 칼 포머런스가 이를 증명하였다.

중국의 택배기사인 위젠춘(33)이 카마이클 수를 증명하는 새로운 방법을 찾아 냈다고 한다. 이 사람은 제대로된 고등 수학 교육을 받은 적이 없다고 한다. 중국판 [[굿 윌 헌팅]]이라고... [[http://news.kmib.co.kr/article/view.asp?arcid=0010791170|관련기사]]
[[분류:정수론]][[분류:피에르 드 페르마]]