페르마의 소정리

Fermat's little Theorem.

이 정리는 여백이 충분해서 오래 전에 증명되었습니다

1 개요

[math]p[/math]가 소수이고 [math]a[/math]가 [math]p[/math]의 약수가 아니면,

[math] a^{ p - 1 } \equiv 1 \left( \text{mod}\ p \right) [/math]

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

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

2 증명

• 수학적 귀납법과 이항정리를 사용한 증명

먼저, 페르마의 소정리가 다음과 동치임을 확인하자:

[math]p[/math]가 소수라면, [math] n^{p} \equiv n \left(\text{mod}\ p \right) [/math]

먼저 [math]n=0[/math]일 경우는 자명하다.
이항전개에 의하면

[math]\left(n+1\right)^p=n^p+ \Sigma^p _{n=1} {p \choose n} + 1[/math]

여기서, [math] 0 \lt n \lt p[/math]이면

[math] {p \choose n} = {p\left(p-1\right)\cdots \left(p-n+1\right) \over n\left(n-1\right)\cdots 1}[/math]

은 [math]p[/math]의 배수이다. 따라서,

[math]\left(n+1\right)^p \equiv n^p + 1\left( \text{mod}\ p \right)[/math]

는 항상 성립하는 명제. 이제, [math]n[/math]일 때 성립한다는 귀납 가정을 하면, [math]n+1[/math], 혹은 [math]n-1[/math]일 때도 성립한다.
따라서, 모든 정수 [math]n[/math]에 대해 성립한다.

• 완전잉여계를 사용한 증명

이 경우 소수일 때 뿐만이 아닌, 일반적인 정수에 대한 오일러의 정리를 증명하는 것이다.

• 조합론을 사용한 증명

구슬 숫자 p개로 이루어진 목걸이를 생각해 보자. 이제 이 목걸이의 구슬을 색칠할 것인데 칠할 수 있는 색 종류는 a 개이다. 원순열 등 복잡한 생각없이 그냥 구슬 위치마다 좌표가 있다고 생각하면 색칠 가능한 경우의 수는 a의 p 승이다. 색 a개에 구슬 p개니까. 그런데 실제 목걸이는 원형이기 때문에 같은 목걸이를 회전시켜서 얻을 수 있는 경우가 p가지 있고 위에서 단순 셈한것은 이 목걸이를 다 다른 것으로 계산한 것이 된다.(예로 3개 구슬로 이루어진 목걸이를 흰검빨로 칠하는 경우를 생각해보면 흰검빨, 검빨흰, 빨흰검 은 회전시켜보면 모두 같은 목걸이이다.) 단, 모든 구슬이 완전히 같은 색깔로 칠해진 경우는 위에서 단순히 셈한 것이나 실제 목걸이나 한 가지로 계산되는데 이 방법은 색깔의 종류 a 개와 같다.
따라서 a의 p승 (단순 셈한 목걸이 숫자) 에서 a개(깡그리 같은 색깔로 칠해서 얻을 수 있는 목걸이 숫자)를 빼면 이는 p의 배수가 되어야 한다.
모두 같은 색으로 칠해진 목걸이 a개를 제외한 실제 목걸이 1개에 대해 회전시켜서 얻을 수 있는 p가지를 단순셈에서는 모두 다른 목걸이로 계산했기에 있기 때문에 전체 단순셈 목걸이 에서 깡그리 같은 색인 목걸이 숫자를 빼면 p의 배수가 되어야 한다. 즉, a의 p승과 a는 modulo p에 대해 합동이다. 증명완료.

잉여계에 의한 증명은 먼저 a와 p가 서로소인 것에 주의한다. 이 때 1a, 2a, 3a, ....(p-1)a 가 modulo p 에대해 서로 합동이 아니라는 점을 생각하고, 각 ka에 대해(k = 1, 2, .... , p-1) mod p 합동식을 생각한뒤 양변 곱해보면 거의 자명한 결과가 얻어진다. 왜냐하면 우항도 나머지가 1, 2, 3,..... p-1이 한번씩 정확하게 나타나기 때문에 곱하면 (p-1)! 은 양변에서 지울 수 있다.