| 정수론 Number Theory | |||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | 공리 | ||
| 페아노 공리계 · 정렬 원리 · 수학적 귀납법 · 아르키메데스 성질 | |||
| 산술 | |||
| 나눗셈 | 약수·배수 | 배수 · 약수(소인수) · 소인수분해(목록 · 알고리즘) · 공배수 · 공약수 · 최소공배수 · 최대공약수 | |
| 약수들의 합에 따른 수의 분류 | 완전수 · 부족수 · 과잉수 · 친화수 · 사교수 · 혼약수 · 반완전수 · 불가촉 수 · 괴짜수 | ||
| 정리 | 베주 항등식 · 산술의 기본정리 · 나눗셈 정리 | ||
| 기타 | 유클리드 호제법 · 서로소 | ||
| 디오판토스 방정식 | 페르마의 마지막 정리 · 피타고라스 세 쌍 · 버치-스위너턴다이어 추측(미해결) | ||
| 모듈러 연산 | |||
| 잉여역수 · 2차 잉여 · 기약잉여계 · 완전잉여계 · 중국인의 나머지 정리 · 합동식 · 페르마의 소정리 · 오일러 정리 · 윌슨의 정리 | |||
| 소수론 | |||
| 수의 분류 | 소수 · 합성수 · 메르센 소수 · 쌍둥이 소수(사촌 소수 · 섹시 소수) · 페르마 소수 · 레퓨닛 수 | ||
| 분야 | 대수적 정수론(국소체) · 해석적 정수론 | ||
| 산술함수 | 뫼비우스 함수 · 소수 계량 함수 · 소인수 계량 함수 · 약수 함수 · 오일러 파이 함수 · 폰 망골트 함수 · 체비쇼프 함수 · 소수생성다항식 | ||
| 정리 | 그린 타오 정리 · 페르마의 두 제곱수 정리 · 디리클레 정리 · 소피 제르맹의 정리 · 리만 가설(미해결) · 골드바흐 추측(미해결)(천의 정리) · 폴리냑 추측(미해결) · 소수 정리 | ||
| 기타 | 에라토스테네스의 체 · 윌런스의 공식 | ||
1. 개요
Fermat's little Theorem, FlT[1] · 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))] 이다.
[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대 정리 중 하나다. [2] 역시 페르마답게 증명은 하지 않고 편지를 통해 이 정리에 대해 발표했지만, 그 사실 발견 자체가 놀라운 일이므로 페르마의 소정리라고 부른다.
한 마디로 임의의 소수 [math(p)]에 대해 서로소인 한 수의 [math((p-1))]승을 [math(p)]로 나눈 나머지는 무조건 [math(1)]이라는 정리. 눈으로 보이는 간결성만큼 효과도 매우 강력한 정리이다. [math(64^{70})]을 [math(71)]로 나눈 나머지는 [math(1)]이라는 것을 순식간에 알 수 있다. 더 나아가서 [math(64)]의 [math(70)]의 배수 거듭제곱을 [math(71)]로 나눈 나머지를 쉽게 구할 수 있다. 예를 들어 [math(64^{70000000})]을 [math(71)]로 나누면 나머지가 [math(1)]이라는 엄청난 결론을 낼 수 있다.
이 정리의 역은 성립하지 않는다. 자세한 내용은 후술.
2. 증명
2.1. 수학적 귀납법과 이항정리를 사용한 증명
먼저, 페르마의 소정리는 다음과 동치이다.[math(p\text{가 소수라면, }n^p\equiv n\pmod{p})]
[math(n=0)]일 경우는 자명하다.
이항정리에 의하면
[math(\displaystyle\left(n+1\right)^p=n^p+1+\sum_{r=1}^{p-1}\binom{p}{r}n^r)]
여기서, [math(0<r<p)]이면
[math(\displaystyle {p\choose r}=\frac{p(p-1)\cdots(p-r+1)}{r(r-1)\cdots1})]
p는 소수이기에 위 식은 [math(p)]의 배수이다. 따라서,
[math(\left(n+1\right)^p\equiv n^p+1\pmod{p})]
는 항상 성립하는 명제.
같은 방법으로
[math(\left(n-1\right)^p\equiv n^p-1\pmod{p})]
도 항상 성립한다. 이제, [math(n)]일 때 성립한다는 가정을 하면, [math(n+1, n-1)]일 때도 성립한다. 따라서, 모든 정수 [math(n)]에 대해 이 공식이 성립한다는 것을 알 수 있다.
2.2. 다항정리를 이용한 증명
[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})]
2.3. 기약잉여계를 사용한 증명[3]
먼저 [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\})]와 같다. 이때 전부 곱한 것을 생각하면 다음이 성립한다.[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 입문때 제일 많이 사용되는 방법이기도 하다.
2.4. 조합론을 사용한 증명
구슬 숫자 [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)]에 대해 합동이다.
2.5. 집합의 분할을 이용한 증명
다음과 같은 함수 집합 [math(F)]를 생각하자.[math(F=\left\{f|f:\mathbb{Z}_p\to\mathbb{Z}_a\right\})]
그리고 이 집합 위의 동치관계를 다음과 같이 정의한다.
[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)]의 배수이다. 따라서
[math(a^p-a\equiv 0\pmod{p})]
3. 합성수 판정에 사용
이 명제의 대우는 다음과 같다.어떤 수 [math(n)]이 적당한 [math(a)]에 대해서 [math(a^n\not\equiv a\left({\rm mod}\ n\right))] 이면, [math(n)]은 합성수이다.
페르마의 소정리를 이용하면, 어떤 수가 소수인지를 확실하게 판정해 줄 수는 없지만, 저 조건을 만족하면 합성수임은 판정할 수 있다.아래 설명하는 카마이클 수 때문에 소수 판정용으로 사용할 수 없다. 하지만, 소수 후보를 추려 내고, 이 후보들을 다른 소수 판정법을 이용하여 소수 판정을 하는데 사용하는 식으로 사용하는 것은 가능하다.
3.1. 페르마 유사소수
어떤 합성수 [math(n)]이 어떤 [math(a)]에 대해서 [math(a^{n-1}\equiv 1\pmod{n})]이면, [math(n)]을 페르마 유사소수(Fermat pseudoprime)이라고 부른다.
참고로 유사소수는 이것 말고도 여러 종류가 있다.예를 들어 [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)]은 합성수임을 알 수 있다.
이러한 페르마 유사소수는 무한히 많다.
3.2. 카마이클 수
페르마 유사 소수 중에서도 특이한 케이스로, 모든 정수 [math(a)]에 대해 [math(a^p\equiv a\left({\rm mod}\ p\right))]임에도 불구하고 [math(p)]가 합성수인 수이다. 이를 절대 유사 소수(absolute pseudoprime) 또는 이를 연구한 수학자 로버트 카마이클의 이름을 따서 카마이클 수(Carmichael number)라고 부른다.카마이클 수 [math(n)]은, [math(n)]과 서로소이며[4] [math(n)]보다 작은 모든 [math(a)]에 대해서 [math(a^{n-1}\equiv 1\pmod{n})]를 만족한다.
[math(561)][math((=3\times 11\times 17))], [math(1105)][math((=5\times 13\times 17))], [math(1729)][math((=7\times 13\times 19))] 같은 수가 있다. 목록 보기
카마이클 수는 페르마의 소정리를 이용한 소수 판정 방법의 절대적인 반례가 되기 때문에, 페르마의 소정리만으로는 소수 판정이 불가능하다.
처음에는 카마이클 수가 유한할 것으로 예상하여, 모든 카마이클 수의 목록을 정리하려고 시도하였다. 하지만, 에르되시 팔은 카마이클 수가 무한히 많이 존재할 것이라고 예상하였고, 1994년 레드 알퍼드, 앤드루 그랜빌, 칼 포머런스가 이를 증명하였다. 단 이중 카마이클이 기존에 예측한 또다른 내용인 [math((6k+1)(12k+1)(18k+1))] 꼴이고 [math(6k+1, 12k+1, 18k+1)]이 모두 소수인 카마이클 수가 무한히 많이 존재하는가는 아직 미증명 상태이다. 이 문제는 딕슨 추측이 참이라면 자동적으로 참이 된다.
중국의 택배기사인 위젠춘(33)이 카마이클 수를 증명하는 새로운 방법을 찾아 냈다고 한다. 이 사람은 제대로된 고등 수학 교육을 받은 적이 없다고 한다. 중국판 굿 윌 헌팅이라고... 관련기사 위젠춘이 발견한 법칙의 인수는 이차식을 포함해 위의 딕슨 추측의 참 여부와는 부분적으로 별개라는 점에 의의가 있다.
[1] l은 L의 소문자이다. 대문자로 쓴 FLT는 페르마의 마지막 정리를 뜻한다.[2] 나머지는 오일러의 정리, 중국인의 나머지 정리, 윌슨의 정리.[3] 이 방법은 오일러의 정리를 증명하는 방법과 같다.[4] [math(n)]과 서로소가 아닐 경우 나머지가 [math(1)]이 나오지 않을 것임은 자명하므로 제외하는 것이다.