| 정수론 Number Theory | |||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | 공리 | ||
| 페아노 공리계 · 정렬 원리 · 수학적 귀납법 · 아르키메데스 성질 | |||
| 산술 | |||
| 나눗셈 | 약수·배수 | 배수 · 약수(소인수) · 소인수분해(목록 · 알고리즘) · 공배수 · 공약수 · 최소공배수 · 최대공약수 | |
| 약수들의 합에 따른 수의 분류 | 완전수 · 부족수 · 과잉수 · 친화수 · 사교수 · 혼약수 · 반완전수 · 불가촉 수 · 괴짜수 | ||
| 정리 | 베주 항등식 · 산술의 기본정리 · 나눗셈 정리 | ||
| 기타 | 유클리드 호제법 · 서로소 | ||
| 디오판토스 방정식 | 페르마의 마지막 정리 · 피타고라스 세 쌍 · 버치-스위너턴다이어 추측(미해결) | ||
| 모듈러 연산 | |||
| 잉여역수 · 2차 잉여 · 기약잉여계 · 완전잉여계 · 중국인의 나머지 정리 · 합동식 · 페르마의 소정리 · 오일러 정리 · 윌슨의 정리 | |||
| 소수론 | |||
| 수의 분류 | 소수 · 합성수 · 메르센 소수 · 쌍둥이 소수(사촌 소수 · 섹시 소수) · 페르마 소수 · 레퓨닛 수 | ||
| 분야 | 대수적 정수론(국소체) · 해석적 정수론 | ||
| 산술함수 | 뫼비우스 함수 · 소수 계량 함수 · 소인수 계량 함수 · 약수 함수 · 오일러 파이 함수 · 폰 망골트 함수 · 체비쇼프 함수 · 소수생성다항식 | ||
| 정리 | 그린 타오 정리 · 페르마의 두 제곱수 정리 · 디리클레 정리 · 소피 제르맹의 정리 · 리만 가설(미해결) · 골드바흐 추측(미해결)(천의 정리) · 폴리냑 추측(미해결) · 소수 정리 | ||
| 기타 | 에라토스테네스의 체 · 윌런스의 공식 | ||
1. 개요
Fundamental theorem of arithmetic1보다 큰 모든 정수 [math(n)]은, 소인수의 순서가 바뀐 것을 제외하면, 서로 다른 소수들의 곱으로 유일하게 표현할 수 있다. 즉,
* [math(\displaystyle n ={p_1}^{e_1}{p_2}^{e_2}\cdots{p_k}^{e_k} )]
(단 [math(e_i \geq 1)], [math(p_1<p_2<\cdots<p_k)]: 서로 다른 소수) 를 만족하는 [math(k,\{p_i\},\{e_i\})]가 유일하게 존재한다.
우리가 소인수분해를 당연하게 여길 수 있게 만들어 주는 정리. 초등 및 중등교과에서는 소인수분해가 거의 주어진 것처럼 사용되지만, 산술의 기본정리는 정수의 성질을 이용해 증명하고 넘어가야 하는 하는 엄연한 정리이다. 교과에서 암묵적으로 사용하는 최대공약수나 최소공배수의 존재성/유일성, 서로소의 개념들도 다 이 정리의 성립과 연관되어 있는 만큼, 이 소인수분해의 유일성은 얼마든지 '기본정리'라는 이름을 얻을 자격이 있다.* [math(\displaystyle n ={p_1}^{e_1}{p_2}^{e_2}\cdots{p_k}^{e_k} )]
(단 [math(e_i \geq 1)], [math(p_1<p_2<\cdots<p_k)]: 서로 다른 소수) 를 만족하는 [math(k,\{p_i\},\{e_i\})]가 유일하게 존재한다.
역사적으로는 유클리드의 원론의 여러 부분에 나누어져 등장했고, 위에 보는 현대적인 형태의 서술은 가우스의 산술원리(Disquisitiones Arithmeticae)에서부터 등장한다.
2. 증명
산술의 기본정리의 증명은 보통 대학 수학 정수론으로 미뤄지는데, 자연수 및 정수의 공리[1]만으로 위 정리를 증명하기는 생각보단 어렵기 때문이다. 초등수학으로 불가능한 건 아니지만 귀찮은 편이다. 만약 증명에 이상의 공리에 해당하지 않는 것들(즉 최대공약수나 최소공배수의 존재성, 베주 항등식 등등)을 사용한다면 반드시 먼저 증명하고 시작해야 한다. 정수론을 공부하다 보면 저 하나하나가 기본정리만큼 강력한 대상이라는 것을 체감할 수 있다.2.1. 존재성
1보다 큰 임의의 양의 정수 [math(n)]의 두번째로 작은 약수는 소수여야 한다.[2] 이를 귀류법으로 증명하면 다음과 같다. 만약 [math(m)]이 [math(n)]의 두 번째로 작은 약수인데 합성수라면, 합성수의 정의에 의해 [math(l\mid m,\,1<l<m)]인 자연수 [math(l)]이 존재한다. 그런데 [math(m\mid n)]이므로 [math(l\mid n)]이고, 이는 [math(m)]이 두 번째로 작은 약수라는 정의에 모순된다. 따라서 [math(m)]은 소수이다. 따라서, [math(n=p_1n_1)]로 표현할 수 있고 ([math(p_1=m)]), [math(n_1)]이 소수라면 증명은 끝. 소수가 아니라면 위 과정을 계속 반복하여[3] [math(n)]을 소수의 곱으로만 표현할 수 있다. 즉, 1보다 큰 임의의 양의 정수 [math(n)]의 소인수분해가 존재한다.2.2. 유일성
대부분의 경우 유일성을 증명하는 데에 다음의 유클리드의 보조정리(Euclid's lemma)를 사용한다.유클리드의 보조정리
소수 [math(p)]가 두 정수 [math(a)]와 [math(b)]의 곱인 [math(ab)]의 약수이면, [math(p)]는 최소한 [math(a)]나 [math(b)] 둘 중 하나의 약수이다.
즉 [math(p \vert ab)] 이면 [math(p \vert a)] 혹은 [math(p \vert b)]. 쉽게 풀어쓰면, "소수 [math(p)]가 [math(ab)]를 나누면, [math(p)]는 최소한 [math(a)]나 [math(b)] 둘 중 하나를 나눈다". 이 유클리드의 보조정리를 사용하면 산술의 기본정리의 유일성을 다음과 같이 증명할 수 있다.소수 [math(p)]가 두 정수 [math(a)]와 [math(b)]의 곱인 [math(ab)]의 약수이면, [math(p)]는 최소한 [math(a)]나 [math(b)] 둘 중 하나의 약수이다.
| 귀류법을 사용해서, 소인수분해가 두 가지 이상 존재하는 자연수가 있다고 하자. 이 중 가장 작은 것을 [math(n)]이라 하고(자연수의 정렬성에 의해 존재한다) 그 소인수분해 표현을 [math(\displaystyle n = p_1 p_2 \cdots p_k = q_1 q_2 \cdots q_l )] 로 나타내자. 만약 어떤 [math(i,j)]에 대해 [math(p_i=q_j)]라면, [math(n'=n/p_i=n/q_j)]를 얻을 수 있는데 이는 [math(n)]이 소인수분해가 두 가지 이상 존재하는 자연수 중 가장 작은 수라는 가정에 모순된다. 따라서 [math(p_i \neq q_j)].유클리드의 보조정리를 확장하면, [math(p_1 \vert p_1 p_2 \cdots p_l)] 즉 [math(p_1 \vert n)]이기 때문에 어떤 [math(i)]에 대해 [math(p_1 \vert q_i)]가 되어야 한다. [math(p_1 \neq q_i)]인데 [math(p_1 \vert q_i)]이므로 [math(q_i = p_1 \cdot (q_i/p_1))]으로 표현할 수 있는데, 이는 [math(q_i)]가 소수라는 가정과 모순이다. 따라서 가정이 잘못되었고, 1보다 큰 임의의 양의 정수의 소인수분해는 유일하게 존재해야 한다. |
| 만약 소수 [math(p)]가 [math(a,b)] 모두를 나누지 않는다고 하자. [math(\gcd(p,a)=\gcd(p,b)=1)]이므로 [math(ax+py=bz+pw=1)]을 만족시키는 정수 [math(x,y,z,w)]가 존재한다. 그러면 [math( 1 = (ax+py)(bz+pw) = ab\cdot xz + p \cdot(axw+byz+pyw) )] 이 성립하므로 [math(\gcd(p,ab)=1)]이 되어, [math(p)]는 [math(ab)]를 나누지 않는다. |
유클리드 보조정리, 베주 항등식, 최대공약수 등을 전혀 사용하지 않는 다음의 초등적 증명도 있다.
| 앞부분의 진행은 위 증명과 동일하다. 소인수분해가 유일하지 않은 최소의 자연수 [math(n)]의 소인수분해 표현을 [math(\displaystyle n = p_1 p_2 \cdots p_k = q_1 q_2 \cdots q_l )] 라 하고, [math(p_i \neq q_j)]를 얻은 부분부터 시작하자.소인수 [math(p_i)]와 [math(q_j)]들이 각각 크기순으로 정렬되었다고 하면, [math(p_1^2 \le p_1 p_2 \le n)]과 [math(q_1^2 \le n)]을 얻을 수 있다.[4] 따라서 [math(p_1 q_1 \le n)]이다. 만약 여기서 등호가 성립하려면 [math(p_1=q_1 = \sqrt{n})]이어야 하므로 이런 경우는 나오지 않고, [math(p_1 q_1 <n)]이 된다. 이제 [math(N=n-p_1 q_1)]으로 정의하면, [math(n)]의 최소원 성질 때문에 [math(N)]은 유일한 소인수분해를 갖는다. 한편 [math(N)]은 [math(p_1)]으로 나누어떨어지므로, [math(N/p_1)]도 유일한 소인수분해를 갖는다. 이제 [math(N = p_1 \cdot(N/p_1))]에서 [math(N/p_1)]의 소인수분해 표현을 생각하고 [math(N)]의 소인수분해 유일성을 이용하면, [math(N)]의 소인수분해에는 [math(p_1)]이 들어가야 한다는 사실을 알 수 있다. 마찬가지로 [math(q_1)]도 [math(N)]의 유일한 소인수분해에 포함되어야 한다. 따라서 적당한 양의 정수 [math(M)]에 대해 [math(N = p_1 q_1 M)]으로 나타낼 수 있다. 마지막으로 [math( \displaystyle \frac{n}{p_1} = \frac{p_1 q_1 +N}{p_1} = q_1(M+1) )] 을 생각하자. 좌변은 [math(p_2 \cdots p_k)]이고, 우변 역시 [math((M+1))]이 소인수분해가 가능하므로 소인수분해 표현으로 나타낼 수 있다. 하지만 [math(q_1)]은 어떤 [math(p_i)]와도 다르므로, 즉 [math(n/p_1)]의 유일하지 않은 소인수분해 표현을 얻을 수 있다. [math(n/p_1<n)]이므로 이는 [math(n)]의 최소성에 모순된다. 따라서 가정이 잘못되었고, 1보다 큰 임의의 양의 정수의 소인수분해는 유일하게 존재해야 한다. |
3. 여담
산술이란 명칭이 정수론 일반을 지칭하는 용례가 희미해진 현대에 와서는 '정수론의 기본정리'라고 하는 게 나을 것 같기도 하다.대학 정수론 교재에서는 베주 항등식->유클리드 보조정리->산술의 기본정리 순으로 증명을 많이 하는 편이다. 상술한 초등적 방식으로 기본정리를 먼저 증명해도 역으로 서로소, 최대공약수와 최소공배수의 성질 등을 모두 얻을 수 있고[5] 외려 이 편이 더 간단한 면도 있지만, 저 순서를 따르는 이유는 이후에 배울 추상대수학과의 연결성을 위해서이다. 대수학에서 환(ring)을 배우면 소인수분해의 유일성이 만족되는 유일인수분해정역(unique factorization domain, UFD) 등등을 배우게 되는데, 어찌 보면 산술의 기본정리는 정수환이 UFD라는 증명으로 볼 수 있다. 몫과 나머지를 정할 수 있는 나눗셈이 가능한 유클리드정역(Euclidean domain, ED) 등등의 개념을 도입해서 ED->PID(단항이데알정역)->UFD 등을 생각하는 것은 위 과정의 연장선상이라 볼 수 있고, 실제로 상당히 흡사한 방식으로 증명을 할 수 있다.
대수학 교재에서 잘 소개되지는 않지만 환론에서의 이러한 일반화도 사실은 정수론이 동기가 되었는데, 정수들에 대수적 무리수들을 집어넣어 일반화하면서 과연 이들에 대해서도 소인수분해가 유일하게 성립할까? 하는 물음에서 출발한 것이다. 예를 들어서 가우스 정수(Gaussian integers) [math(\mathbb{Z}[i]=\{a + bi : a,b \in \mathbb{Z}\})]나 아이젠슈타인 정수(Eisenstein integers) [math(\mathbb{Z}[\omega])] [6] 같은 집합에 대해서는 소인수분해를 유일하게 찾을 수 있다. 하지만 일반적으로 [math(\mathbb{Z}[\sqrt{d}]=\{a + b\sqrt{D} : a,b \in \mathbb{Z} \})] 꼴에서는 소인수분해가 유일하지 않은데, 예로 [math(d=-5)]인 경우에는 다음처럼
[math( \displaystyle 6 = 2 \cdot 3 = (1 + \sqrt{-5}) \cdot (1 - \sqrt{-5}) )]
서로 다른 소인수분해가 존재하기 때문이다.[7] 대수적 정수론 문서에서도 볼 수 있겠지만, 실제로 이런 사례를 정립하기 전까지 많은 수학자들은 소인수분해는 당연히 유일하다고 잘못 생각하고 있었다. 디오판토스 방정식에서 필수적으로 써먹었던 소인수분해가 성립하지 않는 것을 보면서 수학자들은 유클리드 이후로 이 산술의 기본정리에 다시 주목하게 된다. 여기에서 더 나아가서 대수적 정수 위에서 소인수분해가 되지 않는 현상을 설명하기 위해 배수의 일반화인 아이디얼(ideal)의 개념을 고안하였고 소아이디얼 인수분해의 유일성을 증명하는 등등, 역사를 따라가다 보면 소인수분해의 유일성 개념은 정수론과 대수학의 발전에 많은 영향을 끼쳤음을 이후의 사례에서도 볼 수 있을 것이다.[1] 즉 페아노 공리계와 이에서 파생되어 나온 정렬성(well-ordering principle), 수학적 귀납법, 아르키메데스 성질 정도. 엄밀히 말하면 후자의 세 정리는 '공리'는 아니다.[2] 제일 작은 약수는 당연히 1이다.[3] 수가 갈수록 작아지기 때문에([math(n_1<n)]) 이 과정이 무한히 반복될 수는 없다. 이것을 엄밀하게 하려면 정렬성 혹은 수학적 귀납법을 도입하여 진행하여야 한다.[4] 정확히 하려면 [math(k=1)]이 될 수 없는지 먼저 따져봐야 하는데, 만약 이렇다면 [math(n=p_1)]이 소수가 되어 버려서 [math(n=q_1 q_2 \cdots q_l)]을 보면 소수의 정의에 어긋난다.[5] 대신 이러면 베주 항등식은 별도로 증명해야 한다.[6] 여기서 [math(\omega = (-1+\sqrt{-3})/2)]은 [math(omega^2 + omega + 1= 0)]의 복소근이다.[7] 엄밀하게 한다면 위에 나오는 [math(2,3, 1\pm \sqrt{-5})] 모두 서로 다른 곱으로 나타낼 수 없다는 것을 보여야 한다.