산술의 기본정리

• 관련 항목 : 수학 관련 정보

Fundamental Theorem of Arithmetic

1 개요

1보다 큰 모든 정수 [math]n[/math]은 [math]n={p_1}^{e_1}{p_2}^{e_2}\cdots{p_n}^{e_n}[/math]로 (순서가 바뀐 것을 제외하고) 유일하게 나타낼 수 있다. 단, 여기서 [math]e_i\geq0[/math]이고, [math]p_i[/math]는 서로 다른 소수이다.

우리가 소인수분해를 당연하게 여길 수 있게 만들어 주는 정리. 이름이 비슷한 대수학의 기본정리는 듣기만 해도 정신이 날아갈 듯한 증명을 사용하지만, 이 산술의 기본정리는 좀 아주 많이 똑똑한초등학생도 증명을 할 수 있다. 증명은 존재성과 유일성, 두 파트로 나뉜다.

2 증명

정수는 UFD이므로 자명하다.

2.1 존재성

1보다 큰 임의의 양의 정수 [math]n[/math]의 두번째로 작은 약수는 소수여야 한다. 만약 [math]m[/math]이 [math]n[/math]의 두번째로 작은 약수인데 합성수라면, 합성수의 정의에 의해 [math]l\mid m,\,1\ltl\ltm[/math]인 자연수 [math]l[/math]이 존재한다. 그런데 [math]m\mid n[/math]이므로 [math]l\mid n[/math]이고, 이는 [math]m[/math]이 두번째로 작은 약수라는 정의에 모순된다. 따라서 [math]m[/math]은 소수이다. 따라서, [math]n=p_1n_1[/math]로 표현할 수 있고 ([math]p_1=m[/math]), [math]n_1[/math]이 소수라면 증명은 끝. 소수가 아니라면 위 과정을 계속 반복하여 [math]n[/math]을 소수의 곱으로만 표현할 수 있다. 즉, 1보다 큰 임의의 양의 정수 [math]n[/math]의 소인수분해가 존재한다.

2.2 유일성

• 증명 1

귀류법을 사용해 증명한다. 집합 [math]A[/math]를 [math]A=\left\{x\in\right.[/math]ℕ[math]|x\gt1, x[/math]의 소인수분해는 유일하지 않음[math]\left.\right\}[/math]로 정의하자. 자연수의 well-ordering 성질에 의해 집합 [math]A[/math]에는 가장 작은 원소가 존재한다. 이를 [math]n[/math]라 하자. 그럼, [math]p_1\leq p_2\leq\cdots\leq p_k,\,q_1\leq q_2\leq\cdots\leq q_l[/math]을 만족하는 소수 [math]p_1,p_2,\cdots,p_k,q_1,q_2,\cdots,q_l[/math]에 대해 [math]n=p_1p_2\cdots p_k=q_1q_2\cdots q_l[/math]이 성립한다. 여기서 만약 어떤 [math]i,j[/math]에 대해 [math]p_i=q_j[/math]이면, [math]n/p_i[/math]도 소인수분해가 유일하지 않고, [math]n\gtn/p_i[/math]이므로 [math]n[/math]이 [math]A[/math]의 가장 작은 원소라는 사실에 모순된다. 즉, [math]p_i\neq q_j[/math]. 한편, [math]{p_1}^2\leq n, {q_1}^2\leq n[/math]이고 [math]{p_1}^2[/math]와 [math]{q_1}^2[/math]은 동시에 [math]n[/math]이 될 수 없으므로 , [math]0\ltp_1q_1\ltn[/math]이다. 이제 [math]N=n-p_1q_1[/math]이라 정의하자. [math]0\ltN\ltn[/math]이고 [math]p_1\mid N,\,q_1\mid N[/math]이므로, [math]1\ltN\ltn[/math]이 성립하고, [math]N[/math]은 유일한 소인수분해를 가진다. 또한 [math]N[/math]의 유일한 소인수분해에는 [math]p_1[/math]과 [math]q_1[/math]이 둘 다 들어간다. 따라서 적당한 양의 정수 [math]M[/math]에 대해 [math]N=p_1q_1M[/math]. 이제 [math]n=N+p_1q_1=p_1q_1\left(M+1\right)[/math]이고, 양변을 [math]p_1[/math]로 나누면 [math]n/p_1=q_1\left(M+1\right)[/math]. 곧, [math]p_2p_3\cdots p_k=q_1\left(M+1\right)[/math]이다. 여기서 [math]q_1\neq p_i[/math]이므로 [math]n/p_1[/math]는 유일하지 않은 소인수분해를 가진다. 또한 [math]1\ltn/p_1[/math]이므로 [math]n/p_1\in A[/math]이고, [math]n/p_1\ltn[/math]이므로 이는 [math]n[/math]이 집합 [math]A[/math]의 가장 작은 원소라는 사실에 모순된다. 따라서 1보다 큰 임의의 양의 정수의 소인수분해는 유일하다.

이게 어딜 봐서 초등학생도 할 수 있냐

• 증명 2

여기서는 개요만 설명한다.

(1) 임의의 자연수 a, b에 대해 ab가 소수 p로 나누어지면 a, b중 적어도 하나는 p로 나누어진다.

(1-1) 임의의 자연수 x, y에 대해 m이 x와 y의 최소공배수라고 하자. x, y의 모든 공배수는 m의 최소공배수이다.

증명: x, y의 공배수 M 에 대해서 M - m, M - 2m, M - 3m, ... 의 수열을 생각하자. 이 수열에서 0보다 큰 마지막 원소가 m보다 작다면 이는 x와 y의 'm보다 작은' 공배수가 되므로 m이 최소공배수라는 것에 모순이다. 즉 마지막 원소는 항상 m이 되어야 하고, 따라서 M은 항상 m의 배수이다.

(1-2) 임의의 자연수 x, y에 대해 m이 x와 y의 최소공배수라고 하자. [math]d = xy / m[/math]인 d는 자연수이며 x와 y 의 공약수이다.

증명: xy는 x와 y의 공배수이므로 m의 배수이다. 따라서 d는 자연수이다. [math]x = (m/y) d[/math] 인데 m은 y의 배수이므로 [math]m/y[/math]는 자연수이다. 따라서 d는 x의 약수이며, 같은 이유로 y의 약수이다.

단계 (1)의 증명: ab 가 소수 p로 나누어진다고 하자. 이제 a와 p의 최소공배수를 A라고 하자. [math]t = ap / A[/math]는 p의 약수이므로 1 또는 p이다. t = p인 경우에는 a = A이고 A는 p의 배수이므로 a가 p의 배수이다. t = 1인 경우, [math]A = ap [/math] 이다. ab는 a와 p의 공배수이므로 A의 배수이다. [math] ab = Ah[/math] 라고 하자. [math]b = (A/a)h = ph[/math] 이므로 b가 p의 배수이다.

(2) [math]A = p_1^{e_1}p_2^{e_2}p_3^{e_3}... = p_1^{f_1}p_2^{f_2}p_3^{f_3}... [/math] 라 하자. [math]p_i[/math]는 소수이며 [math]e_i[/math]나 [math]f_i[/math]는 0 이상의 정수이다. 그러면 모든 [math]i[/math]에 대하여 [math]e_i = f_i[/math] 이다.

(2-1) 임의의 자연수 [math] a_1, a_2, ..., a_n[/math]에 대하여 [math] a_1 a_2 ... a_n[/math] 가 소수 [math]p[/math]로 나누어지면 [math] a_1, a_2, ..., a_n[/math] 중 적어도 하나는 [math]p[/math]로 나누어진다.

증명: [math] a_1 (a_2 ... a_n)[/math]가 [math]p[/math]로 나누어지므로 [math]a_1[/math]과 [math]a_2 ... a_n[/math] 중 하나는 [math]p[/math]로 나누어자는 것을 이용해서 증명한다.

단계 (2)의 증명: 어떤 [math]i[/math]에 대하여 [math]e_i \neq f_i[/math] 라 하자. 일반성을 잃지 않고 [math]e_i \gt f_i[/math]라 할 수 있다. 그러면 [math]p_1^{e_1}... p_{i-1}^{e_{i-1}} p_i^{e_i - f_i}p_{i+1}^{e_{i+1}}... = p_1^{f_1}...p_{i-1}^{f_{i-1}} p_{i+1}^{f_{i+1}}... [/math] 이므로 [math]p_1^{f_1}...p_{i-1}^{f_{i-1}} p_{i+1}^{f_{i+1}}... [/math]는 [math]p_i[/math]의 배수이다. 그러므로 (2-1)에 따라 [math]p_i[/math]가 [math] p_1^{f_1}, ...p_{i-1}^{f_{i-1}}, p_{i+1}^{f_{i+1}}, ... [/math] 중 하나를 나누어야 한다. [math]p_i[/math]가 [math] p_j^{f_j}[/math]를 나누는 것은 [math]f_j[/math]가 0일 때는 불가능하며 [math]f_j \ge 1[/math]이면 (2-1)에 따라 [math]p_i[/math] 가 [math]p_j[/math]을 나누어야 하므로 역시 모순이다.

3 여담

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