산술의 기본 정리

산술의 기본 정리(算術의基本定理, 영어: fundamental theorem of arithmetic)는 모든 양의 정수는 유일한 소인수 분해를 갖는다는 정리이다.

정의

소수의 집합을 $ℙ \subset ℤ^{+}$ 라고 하자. 산술의 기본 정리에 따르면, 임의의 양의 정수 $n \in ℤ^{+}$ 에 대하여, 곱하여 $n$ 이 되는 소수의 유한 중복집합이 유일하게 존재한다. 즉, 다음 성질을 만족시키는 $p_{1}, \dots, p_{k} \subset ℙ$ 및 $r_{1}, \dots, r_{k} \in ℤ^{+}$ 가 존재하며, 이는 $i = 1, \dots, k$ 의 순열을 무시하면 유일하다.

n = p_{1}^{r_{1}} p_{2}^{r_{2}} \dots p_{k}^{r_{k}}

만약 $n = 1$ 인 경우, $k = 0$ 이며, 이 소수 중복집합은 공집합이 된다.

추상대수학의 용어를 사용하면, 이는 정수의 환 $ℤ$ 가 유일 인수 분해 정역이라는 명제와 동치이다.

증명

이 정리의 증명은 다음과 같은 두 단계로 나뉜다.

1 단계

첫 번째로 1보다 큰 양의 정수가 소수의 곱으로 표현할 수 있음을 증명한다. 1보다 큰 양의 정수 $n$ 의 두 번째로 작은 약수는 반드시 소수여야 한다.(첫 번째로 작은 약수는 1이다.) 만약 $m$ 이 두 번째로 작은 약수이고, 소수가 아니라고 한다면 (즉 합성수라면), 합성수의 정의에 의해서 $1 < l < m$ 이면서 $m$ 을 나누는 양의 정수 $l$ 이 존재하게 되고, 따라서 $l$ 은 $n$ 도 나눌 수 있기 때문에, $m$ 이 두 번째로 작은 약수라는 가정에 모순이 생긴다. 따라서 $n$ 은 반드시 소수인 약수를 갖게 되며 이를 다음과 같이 표현할 수 있다.

$n = p_{1} n_{1}$

만약, $n_{1}$ 이 소수라면, 증명은 여기서 종료된다. 하지만, $n_{1}$ 가 소수가 아니라면, $n_{1}$ 역시 1을 제외한 약수 중에 가장 작은 약수를 소수로 갖기 때문에 다음과 같이 표현할 수 있다.

$n = p_{1} p_{2} n_{2}$

이를 소수만 남을 때까지 반복할 수 있기 때문에, 따라서, 1보다 큰 모든 양의 정수는, 소수의 곱으로 표현 가능하다.

2 단계

두 번째로, 그렇게 표현한 소수의 곱이 (각 인수들의 자리바꿈을 제외한다면) 유일함을 귀류법으로 증명한다. 만약, 소수의 곱이 유일하지 않은 1보다 큰 양의 정수가 있다고 가정해 보자. 그 수 중에서 제일 작은 수를 n 이라고 한다면,

$n = p_{1} p_{2} p_{3} ... p_{k} = q_{1} q_{2} q_{3} ... q_{l},$ ( $p_{1} \leq p_{2} \leq p_{3} \leq ... \leq p_{k}, q_{1} \leq q_{2} \leq q_{3} \leq ... \leq q_{l}$ 이고, $p_{i}$ 와 $q_{j}$ 는 소수, 그리고 $p_{i} \neq q_{j}$ )

( $p_{i} = q_{j}$ 이면, $n^{'} = \frac{n}{p_{i}} = \frac{n}{q_{j}} < n$ 인 $n^{'}$ 을 얻을 수 있는데 이는 소수의 곱이 유일하지 않은 1 보다 큰 정수 중 가장 작은 수가 n이라는 가정과 모순된다.)

한편 $p_{1}^{2} \leq n, q_{1}^{2} \leq n$ 이고 $p_{1}^{2}$ 과 $q_{1}^{2}$ 은 동시에 $n$ 이 될 수 없으므로, $0 < p_{1} q_{1} < n$

$N = n - p_{1} q_{1}$ 이라고 한다면, $0 < N < n$ 이고, 또한 $p_{1} | N$ , $q_{1} | N$ 이기 때문에, $N$ 의 유일한 소인수분해의 표현에는 $p_{1}$ 과 $q_{1}$ 가 동시에 존재하여야 한다.

따라서, $p_{1} q_{1} | N$ 이므로 $N = p_{1} q_{1} S$ ( $S$ 는 양의정수)

$n = N + p_{1} q_{1} = p_{1} q_{1} (S + 1)$

양변을 $p_{1}$ 으로 나누면

$\frac{n}{p_{1}} = q_{1} (S + 1)$

$p_{2} p_{3} p_{4} ... p_{k} = q_{1} (S + 1)$ , 즉 $q_{1} | p_{2} p_{3} p_{4} ... p_{k}$

그러나 $\frac{n}{p_{1}}$ 는 $n$ 보다 작기 때문에 소인수분해가 유일하고, $q_{1} \neq p_{i}$ 이면서, 동시에 $q_{1}$ 은 소수이므로, 소수의 곱이 유일하지 않는 양의 정수가 있다는 가정은 모순이다.

같이 보기