산술의 기본 정리 (Fundamental Theorem of Arithmetic) 2

산술의 기본 정리의 유일성에 대해서 증명을 하겠습니다. 일단 유클리드 소정리를 이용해서 증명을 하고 그 다음에 다른 방법으로 증명하겠습니다.

 

유클리드 소정리는 다음과 같이 일반화 시킬 수 있습니다.

 

소정리 1 소수 $p$ 가 있으면 $p| a_1 \cdots a_r \Rightarrow p | a_i$ 을 만족하는 적당한 $1 \leq i \leq r$ 이 존재한다.

 

귀납법(Induction) 을 사용하면 쉬운 증명이니 도전해보시기 바랍니다.

 

정리 2 (소인수분해의 유일성) 두 소인수분해가 있다고 가정해보자.

\[ p_1 \cdots p_r = q_1 \cdots q_s  \]

또 $ p_1 \leq \cdots \leq p_r $ 과 $ q_1 \leq \cdots \leq q_s$ 라고 가정해보자. 그러면 $r = s$ 이고 모든 $1 \leq i \leq r$ 에 대해서 $p_i = q_i$ 가 성립한다.

 

증명 (1)

 

귀류법 (Induction) 으로 증명해봅시다. $r=1$ 라고 해봅시다. 그러면 $p = q_1 \cdots q_s$ 가 성립합니다. 그러면 $p |q_1 \cdots q_s$ 이기 때문에 소정리 1에 의해서 $p | q_i$ 가 성립합니다. 둘 다 소수이기에 $p = q_i$ 가 성립합니다. 만얄 $s > 1$이면, 양변에 $p$를 나누게 되면

\[  1 = q_1 \cdots q_{i-1} \cdot q_{i+1} \cdots q_s \]

이기 때문에 모순입니다. 소수는 $1$ 보다 크기 때문에 우변이 1 보다 크게 되기 때문입니다. 즉 $s=1$이여야 합니다. 

 

이제 $r >1$라고 가정하고 $r-1$ 경우에 성립한다고 가정합시다. 위랑 비슷하게

\[ p_r | p_1 \cdots p_r = q_1 \cdots q_s \]

를 통해서 적당한 $i$ 에 대해서 $p_r = q_i$ 가 성립합니다. $q_1, \ldots, q_s$의 지표를 다시 써서 $q_i$ 를 $q_s$ 으로 생각할 수 있습니다. 양변을 $p_r = q_s$으로 나누게 되면

\[ p_1 \cdots p_{r-1} = q_1 \cdots q_{s-1} \]

이 성립하게 됩니다. 귀류법에 의해서 $r-1 = s-1 \Rightarrow r=s$ 그리고 모든 $1 \leq i \leq r-1$ 에 대해서 $p_i = q_i$ 가 성립합니다. 이미 $p_r = q_r$은 증명을 했기 때문에 증명이 마무리 됩니다.

 

증명 (2)

다음 증명은 Hardy & Wright - An introduction to the Theory of Numbers 2.11을 참조하였습니다.

 

만약 산술의 기본 정리가 사실이 아니라면 소인수분해가 유일하지 않은 수가 존재합니다.엄밀하게는 소인수분해가 유일하지 않은 수들의 집합 $S$가 공집합이 아니라고 가정합시다. 그럼 자연수의 부분집합이기 때문에 가장 작은 수 $n$ 이 존재합니다. $n$의 두 소인수분해를 다음과 같이 씁시다.

 

\[ p_1 \cdots p_r = q_1 \cdots q_s \]

 

(i) 소수를 소인수분해는 유일합니다.

 

만약 $p = q_1 \cdots q_s$ 면, $q_i$ 들은 $p$ 의 약수가 됩니다. 즉 $q_i$ 들은 $1$ 아니면 $p$  가 됩니다. 여기서 $p$ 가 될 수 있는 $q_i$ 는 하나 밖에 없으므로 $p = q_i$ 가 성립합니다.

 

(ii) 즉, (i)으로 인해서 $n$은 합성수입니다. 

 

(iii) $p_i$ 와 $q_j$ 들은 같은 소수가 없습니다. 

 

어떤 적당한 지표 $i$ 와 $j$에 대해서 $p_i = q_j$ 가 성립한다고 가정해 봅시다. 지표를 재배열해서 $p_1 = q_1$ 라고 가정해도 무방합니다. 양변을 나누게 되면

\[ n/p_1 = p_2 \cdots p_r = q_2 \cdots q_s \]

이 성립합니다. 만약 위의 두 소인수분해가 같다면 $p_1 \cdots p_r = q_1 \cdots q_s$ 또한 같은 소인수분해이기 때문에  $n/p_1$ 또한 유일한 소인수분해를 가지고 있지 않습니다. 즉 $n/p_1 \in S$ 가 성립합니다. 하지만 $1 <  n/p_1 < n$ 이기 때문에  $n$이 $S$ 의 원소 중 가장 작다는 가정을 부정하게 됩니다. 다시 말해 (iii) 이 사실이 됩니다.

 

지표를 또 다시 재배열해서 $p_1 \leq p_i$ 가 성립한다고 가정해봅시다. 마찬가지고 $q_1 \leq q_i$ 가 성립한다고 가정해봅시다. (ii) 에 의해서 $n$이 합성수이기 때문에 $p_1^2 \leq n$ 과 $q_1^2 \leq n$ 이 성립합니다. 즉, $p_1 q_1 \leq n$이 성립하게 됩니다. 새로운 수 $N = n -p_1 q_1$ 을 정의해 봅시다. $0 < N < n$ 을 성립하기 때문에 $N$의 소인수분해는 유일합니다.

 

$p_1 | n \Rightarrow p_1 | N$ 고 $q_1 | n \Rightarrow q_1 | N$ 가 성립합니다. 소인수분해의 유일성에 의해서 $p_1q_1 | N$이 성립합니다. (왜 그럴까요? 더 보기를 눌러주세요)

 

$N$의 소인수분해를 $p_1' \cdots p_t'$ 이라고 합시다. $p_1 | p_1' \cdots p_t'$ 이기 떄문에 $p_1 = p_i'$ 가 성립하고 비슷하게 $q_1 = p_j'$ 가 성립합니다. $p_1$ 이랑 $q_1$은 다른 소수이기 때문에 $i \neq j$가 성립하기 때문에 $p_1 q_1$ 이 $N$의 소인수분해에 약수로 존재해야 됩니다.

 

그러면 $p_1 q_1 | n$ 을 성립합니다. 다시 말해 $p_1 | n/q_1$ 이 성립합니다. $n/q_1 < n$ 이기 때문에 소인수분해의 유일성에 의해서 $n/q_1 = q_2 \cdots q_s$가 성립합니다. 하지만 $p_1 \neq q_i$ 이기 때문에 모순이 생깁니다.