the fundamental theorem of arithmetic
Theorem. 1보다 큰 모든 정수는 곱의 순서를 무시했을 때 오직 한 방법으로 소수의 곱으로 표현된다.
Proof.
먼저 1보다 큰 모든 정수 \(n\)은 소수의 곱으로 표현된다는 것을 증명하자.
\(n\)이 소수이면 자명하게 참이다.
\(n\)이 합성수이면 \(d|n\), \(1<d<n\)인 \(d\)가 존재한다.
이런 \(d\)를 모아놓은 집합 \(S = \{d| d|n , 1<d<n \} \) 을 생각하여 Well Ordering Principle을 적용해서 나온 가장 작은 원소를 \(p_1\)이라고 놓자.
만약 \(p_1\)이 합성수이면 \(d_1 | p_1 \), \(1<d_1 <p_1\)인 \(d_1\)이 존재하고, \(1<d_1<n\), \(d_1|n\)이므로 \(d_1 \in S\)인데 \(d_1<p_1\)이므로 \(p_1\)의 정의에 모순이다.
따라서 \(p_1\)은 소수이다.
\(p_1 | n\)이므로 \(n = p_1 n_1 \quad \text{for some} \; n_1 \in \mathbb{N} \) 이다.
\(n_1\)에 대해서도 같은 과정을 적용해서 어떤 소수 \(p_2\)에 대해 \(n = p_1 p_2 n_2 \)로 나타낼 수 있다.
\(n>n_1>n_2>\cdots\)로 감소하므로 유한번의 시행으로 \(n_k = 1 \quad \text{for some} \; k \in \mathbb{N} \)이 된다. 따라서 다음과 같이 나타내는 것이 가능하다.
\[n = p_1 p_2 \cdots p_m \]
유일성을 증명할 때는 수학적 귀납법을 적용한다.
먼저 정수 n=2일 때 자명하게 성립한다.
어떤 정수 k>2에 대해 \(n=2,3, \cdots, k-1 \)에 대해 명제가 성립한다고 가정하자.
k가 두 가지 방법으로 소인수분해 한 결과를 다음과 같이 놓는다.
\[ k = p_1 p_2 \cdots p_s = q_1 q_2 \cdots q_t \]
s=1일 때, 즉 k = p 꼴일 때 오직 한 방법임이 자명하므로 \(s,t>1\)일 경우만 명제를 만족하는 것을 보이면 충분하다.
\(p_1 | k \)이므로 \(q_1 q_2 \cdots q_t \)를 재배열해서 \(p_1 | q_1 \)이 되도록 만들 수 있다. p,q 모두 소수이므로 \(p_1 = q_1\)이 되고, 다음과 같이 정리된다.
\[ \frac {k}{p_1} = p_2 p_3 \cdots p_s = q_2 q_3 \cdots q_t \]
s>1이므로 \( 1 < k/p_1 < k\)이고, 귀납의 과정 중에 가정한 명제이므로 한 가지 방법으로만 표현되는 소수의 곱이다. 즉, s=t이고 \(k/p_1 \) 은 유일하게 소수의 곱으로 표현된다. 따라서 \(p_1 \frac {k}{p_1} \) 또한 유일한 소수의 곱으로 표현된다.
□