산술의 기본정리
1. 개요
Fundamental theorem of arithmetic
우리가 소인수분해를 당연하게 여길 수 있게 만들어 주는 정리. 초등 및 중등교과에서는 소인수분해가 거의 주어진 것처럼 사용되지만, 산술의 기본정리는 정수의 성질을 이용해 증명하고 넘어가야 하는 하는 엄연한 정리이다. 교과에서 암묵적으로 사용하는 최대공약수나 최소공배수의 존재성/유일성, 서로소의 개념들도 다 이 정리의 성립과 연관되어 있는 만큼, 이 소인수분해의 유일성은 얼마든지 '기본정리'라는 이름을 얻을 자격이 있다.1보다 큰 모든 정수 $$n$$은, 소인수의 순서가 바뀐 것을 제외하면, 서로 다른 소수들의 곱으로 '''유일하게''' 표현할 수 있다. 즉,
* $$\displaystyle n ={p_1}^{e_1}{p_2}^{e_2}\cdots{p_k}^{e_k} $$
(단 $$e_i \geq 1$$, $$p_1<p_2<\cdots<p_k$$: 서로 다른 소수) 를 만족하는 $$k,\{p_i\},\{e_i\}$$가 유일하게 존재한다.
역사적으로는 유클리드의 원론의 여러 부분에 나누어져 등장했고, 위에 보는 현대적인 형태의 서술은 가우스의 산술원리(Disquisitiones Arithmeticae)에서부터 등장한다.
2. 증명
산술의 기본정리의 증명은 보통 대학 수학 정수론으로 미뤄지는데, 자연수 및 정수의 공리[1]만으로 위 정리를 증명하기는 생각보단 어렵기 때문이다. 초등수학으로 불가능한 건 아니지만 귀찮은 편이다. 만약 증명에 이상의 공리에 해당하지 않는 것들(즉 최대공약수나 최소공배수의 존재성, 베주 항등식 등등)을 사용한다면 반드시 먼저 증명하고 시작해야 한다. 정수론을 공부하다 보면 저 하나하나가 기본정리만큼 강력한 대상이라는 것을 체감할 수 있다.
2.1. 존재성
1보다 큰 임의의 양의 정수 $$n$$의 두번째로 작은 약수는 소수여야 한다.[2] 이를 귀류법으로 증명하면 다음과 같다. 만약 $$m$$이 $$n$$의 두 번째로 작은 약수인데 합성수라면, 합성수의 정의에 의해 $$l\mid m,\,1<l<m$$인 자연수 $$l$$이 존재한다. 그런데 $$m\mid n$$이므로 $$l\mid n$$이고, 이는 $$m$$이 두 번째로 작은 약수라는 정의에 모순된다. 따라서 $$m$$은 소수이다. 따라서, $$n=p_1n_1$$로 표현할 수 있고 ($$p_1=m$$), $$n_1$$이 소수라면 증명은 끝. 소수가 아니라면 위 과정을 계속 반복하여[3] $$n$$을 소수의 곱으로만 표현할 수 있다. 즉, 1보다 큰 임의의 양의 정수 $$n$$의 소인수분해가 존재한다.
2.2. 유일성
대부분의 경우 유일성을 증명하는 데에 다음의 유클리드의 보조정리(Euclid's lemma)를 사용한다.
즉 $$p \vert ab$$ 이면 $$p \vert a$$ 혹은 $$p \vert b$$. 쉽게 풀어쓰면, "소수 $$p$$가 $$ab$$를 나누면, $$p$$는 최소한 $$a$$나 $$b$$ 둘 중 하나를 나눈다". 이 유클리드의 보조정리를 사용하면 산술의 기본정리의 유일성을 다음과 같이 증명할 수 있다.'''유클리드의 보조정리'''
소수 $$p$$가 0이 아닌 두 정수 $$a$$와 $$b$$의 곱인 $$ab$$의 약수이면, $$p$$는 최소한 $$a$$나 $$b$$ 둘 중 하나의 약수이다.
비교적 짧은 편인데, 이는 어떻게 보면 이 유클리드 보조정리가 산술의 기본정리만큼 강력하다는 뜻도 된다. 대신에 유클리드 보조정리의 증명이 생각보다 까다롭다. 베주 항등식을 사용한 유클리드 보조정리의 증명은 다음과 같다.
최대공약수나 최소공배수의 존재성을 이용해 진행할 수도 있지만, 이 둘을 증명하려면 또 베주 항등식이 필요하므로 유의해야 한다.
유클리드 보조정리, 베주 항등식, 최대공약수 등을 전혀 사용하지 않는 다음의 초등적 증명도 있다.
3. 여담
산술이란 명칭이 정수론 일반을 지칭하는 용례가 희미하진 현대에 와서는 '정수론의 기본정리'라고 하는 게 나을 것 같기도 하다.
대학 정수론 교재에서는 베주 항등식->유클리드 보조정리->산술의 기본정리 순으로 증명을 많이 하는 편이다. 상술한 초등적 방식으로 기본정리를 먼저 증명해도 역으로 서로소, 최대공약수와 최소공배수의 성질 등을 모두 얻을 수 있고[5] 외려 이 편이 더 간단한 면도 있지만, 저 순서를 따르는 이유는 이후에 배울 추상대수학과의 연결성을 위해서이다. 대수학에서 환(ring)을 배우면 소인수분해의 유일성이 만족되는 유일인수분해정역(unique factorization domain, UFD) 등등을 배우게 되는데, 어찌 보면 산술의 기본정리는 정수환이 UFD라는 증명으로 볼 수 있다. 몫과 나머지를 정할 수 있는 나눗셈이 가능한 유클리드정역(Euclidean domain, ED) 등등의 개념을 도입해서 ED->PID(단항이데알정역)->UFD 등을 생각하는 것은 위 과정의 연장선상이라 볼 수 있고, 실제로 상당히 흡사한 방식으로 증명을 할 수 있다.
대수학 교재에서 잘 소개되지는 않지만 환론에서의 이러한 일반화도 사실은 정수론이 동기가 되었는데, 정수들에 대수적 무리수들을 집어넣어 일반화하면서 과연 이들에 대해서도 소인수분해가 유일하게 성립할까? 하는 물음에서 출발한 것이다. 예를 들어서 가우스 정수(Gaussian integers) $$\mathbb{Z}[i]=\{a + bi : a,b \in \mathbb{Z}\}$$나 아이젠슈타인 정수(Eisenstein integers) $$\mathbb{Z}[\omega]$$ [6] 같은 집합에 대해서는 소인수분해를 유일하게 찾을 수 있다. 하지만 일반적으로 $$\mathbb{Z}[\sqrt{d}]=\{a + b\sqrt{D} : a,b \in \mathbb{Z} \}$$ 꼴에서는 소인수분해가 유일하지 않은데, 예로 $$d=-5$$인 경우에는 다음처럼
$$ \displaystyle 6 = 2 \cdot 3 = (1 + \sqrt{-5}) \cdot (1 - \sqrt{-5}) $$
서로 다른 소인수분해가 존재하기 때문이다.[7] 대수적 정수론 문서에서도 볼 수 있겠지만, 실제로 이런 사례를 정립하기 전까지 많은 수학자들은 소인수분해는 당연히 유일하다고 잘못 생각하고 있었다. 디오판토스 방정식에서 필수적으로 써먹었던 소인수분해가 성립하지 않는 것을 보면서 수학자들은 유클리드 이후로 이 산술의 기본정리에 다시 주목하게 된다. 여기에서 더 나아가서 대수적 정수 위에서 소인수분해가 되지 않는 현상을 설명하기 위해 배수의 일반화인 아이디얼(ideal)의 개념을 고안하였고 소아이디얼 인수분해의 유일성을 증명하는 등등, 역사를 따라가다 보면 소인수분해의 유일성 개념은 정수론과 대수학의 발전에 많은 영향을 끼쳤음을 이후의 사례에서도 볼 수 있을 것이다.[1] 즉 페아노 공리계와 이에서 파생되어 나온 정렬성(well-ordering principle), 수학적 귀납법, 아르키메데스 성질 정도. 엄밀히 말하면 후자의 세 정리는 '공리'는 아니다.[2] 제일 작은 약수는 당연히 1이다.[3] 수가 갈수록 작아지기 때문에($$n_1<n$$) 이 과정이 무한히 반복될 수는 없다. 이것을 엄밀하게 하려면 정렬성 혹은 수학적 귀납법을 도입하여 진행하여야 한다.[4] 정확히 하려면 $$k=1$$이 될 수 없는지 먼저 따져봐야 하는데, 만약 이렇다면 $$n=p_1$$이 소수가 되어 버려서 $$n=q_1 q_2 \cdots q_l$$을 보면 소수의 정의에 어긋난다.[5] 대신 이러면 베주 항등식은 별도로 증명해야 한다.[6] 여기서 $$\omega = (-1+\sqrt{-3})/2$$은 $$\omega^2 + \omega + 1= 0$$의 복소근이다.[7] 엄밀하게 한다면 위에 나오는 $$2,3, 1\pm \sqrt{-5}$$ 모두 서로 다른 곱으로 나타낼 수 없다는 것을 보여야 한다.