[include(틀:정수론)]

[목차]

== 개요 ==
Fundamental theorem of arithmetic

>1보다 큰 모든 정수 [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\})]가 유일하게 존재한다.
우리가 [[소인수분해]]를 당연하게 여길 수 있게 만들어 주는 정리. 초등 및 중등교과에서는 소인수분해가 거의 주어진 것처럼 사용되지만, 산술의 기본정리는 정수의 성질을 이용해 증명하고 넘어가야 하는 하는 엄연한 정리이다. 교과에서 암묵적으로 사용하는 [[최대공약수]]나 [[최소공배수]]의 존재성/유일성, [[서로소]]의 개념들도 다 이 정리의 성립과 연관되어 있는 만큼, 이 소인수분해의 유일성은 얼마든지 '기본정리'라는 이름을 얻을 자격이 있다.

역사적으로는 [[유클리드]]의 원론의 여러 부분에 나누어져 등장했고, 위에 보는 현대적인 형태의 서술은 [[카를 프리드리히 가우스|가우스]]의 산술원리(Disquisitiones Arithmeticae)에서부터 등장한다.

== 증명 ==
산술의 기본정리의 증명은 보통 대학 수학 [[정수론]]으로 미뤄지는데, 자연수 및 정수의 공리[* 즉 [[자연수#s-2.1|페아노 공리계]]와 이에서 파생되어 나온 정렬성(well-ordering principle), [[수학적 귀납법]], [[아르키메데스 성질]] 정도. 엄밀히 말하면 후자의 세 정리는 '공리'는 아니다.]만으로 위 정리를 증명하기는 생각보단 어렵기 때문이다. 초등수학으로 불가능한 건 아니지만 귀찮은 편이다. 만약 증명에 이상의 공리에 해당하지 않는 것들(즉 [[최대공약수]]나 [[최소공배수]]의 존재성, [[베주 항등식]] 등등)을 사용한다면 반드시 먼저 증명하고 시작해야 한다. 정수론을 공부하다 보면 저 하나하나가 기본정리만큼 강력한 대상이라는 것을 체감할 수 있다.

=== 존재성 ===
1보다 큰 임의의 양의 정수 [math(n)]의 두번째로 작은 약수는 [[소수(수론)|소수]]여야 한다.[* 제일 작은 약수는 당연히 1이다.] 이를 [[귀류법]]으로 증명하면 다음과 같다. 만약 [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)]이 소수라면 증명은 끝. 소수가 아니라면 위 과정을 계속 반복하여[* 수가 갈수록 작아지기 때문에([math(n_1<n)]) 이 과정이 무한히 반복될 수는 없다. 이것을 엄밀하게 하려면 정렬성 혹은 수학적 귀납법을 도입하여 진행하여야 한다.] [math(n)]을 소수의 곱으로만 표현할 수 있다. 즉, 1보다 큰 임의의 양의 정수 [math(n)]의 소인수분해가 존재한다.

=== 유일성 ===
대부분의 경우 유일성을 증명하는 데에 다음의 유클리드의 보조정리(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(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)]을 얻을 수 있다.[* 정확히 하려면 [math(k=1)]이 될 수 없는지 먼저 따져봐야 하는데, 만약 이렇다면 [math(n=p_1)]이 소수가 되어 버려서 [math(n=q_1 q_2 \cdots q_l)]을 보면 소수의 정의에 어긋난다.] 따라서 [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보다 큰 임의의 양의 정수의 소인수분해는 유일하게 존재해야 한다.||

== 여담 ==
산술이란 명칭이 [[정수론]] 일반을 지칭하는 용례가 희미해진 현대에 와서는 '정수론의 기본정리'라고 하는 게 나을 것 같기도 하다.

대학 정수론 교재에서는 [[베주 항등식]]->유클리드 보조정리->산술의 기본정리 순으로 증명을 많이 하는 편이다. 상술한 초등적 방식으로 기본정리를 먼저 증명해도 역으로 서로소, 최대공약수와 최소공배수의 성질 등을 모두 얻을 수 있고[* 대신 이러면 베주 항등식은 별도로 증명해야 한다.] 외려 이 편이 더 간단한 면도 있지만, 저 순서를 따르는 이유는 이후에 배울 추상[[대수학]]과의 연결성을 위해서이다. 대수학에서 환(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])] [* 여기서 [math(\omega = (-1+\sqrt{-3})/2)]은 [[1의 거듭제곱근/세제곱근|[math(\omega^2 + \omega + 1= 0)]의 복소근]]이다.] 같은 집합에 대해서는 소인수분해를 유일하게 찾을 수 있다. 하지만 일반적으로 [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}) )]
서로 다른 소인수분해가 존재하기 때문이다.[* 엄밀하게 한다면 위에 나오는 [math(2,3, 1\pm \sqrt{-5})] 모두 서로 다른 곱으로 나타낼 수 없다는 것을 보여야 한다.] [[대수적 정수론]] 문서에서도 볼 수 있겠지만, 실제로 이런 사례를 정립하기 전까지 많은 수학자들은 소인수분해는 당연히 유일하다고 잘못 생각하고 있었다. [[디오판토스 방정식]]에서 필수적으로 써먹었던 소인수분해가 성립하지 않는 것을 보면서 수학자들은 유클리드 이후로 이 산술의 기본정리에 다시 주목하게 된다. 여기에서 더 나아가서 대수적 정수 위에서 소인수분해가 되지 않는 현상을 설명하기 위해 배수의 일반화인 아이디얼(ideal)의 개념을 고안하였고 소아이디얼 인수분해의 유일성을 증명하는 등등, 역사를 따라가다 보면 소인수분해의 유일성 개념은 정수론과 대수학의 발전에 많은 영향을 끼쳤음을 이후의 사례에서도 볼 수 있을 것이다.

[[분류:산술]][[분류:정수론]][[분류:기본정리]]