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

목차로 돌아가기

 

지난 포스트에서도 이야기 했듯이 모든 자연수는 소수의 곱으로 나타낼 수 있고 순서를 무시하면 유일합니다. 이를 정확히 쓰면 다음과 같습니다.

 

정리 1 (산술의 기본 정리)

자연수 \( n >1 \) 이 있다고 가정하자. 수 \( n \) 은 다음과 같이 쓸 수 있다.

\[ n = p_1^{e_1} \cdots p_r^{e_r} = \prod_{i=1}^r p_i^{e_i} \]

여기서 모든 \( 1 \leq i \leq n \) 에 대해서 \( e_i \geq 1 \) 인 자연수이다. 만약,

\[ p_1^{e_1} \cdots p_r^{e_r} = q_1^{f_1} \cdots q_s^{f_s} \]

이면 \( r = s \) 이며  첨수 (index)를 적당히 바꾸면 모든 \( 1 \leq i \leq n \) 에 대해서 \( e_i = f_i \) 가 성립한다. 

 

예 2 숫자 \( 36 \) 를 예로 들어봅시다. 

\[ 36 = 18 \cdot 2 = 9 \cdot 2 \cdot 2 = 3 \cdot 3 \cdot 2 \cdot 2 = 2^2 \cdot 3^2  \]

 과

\[ 36 = 12 \cdot 3 = 6 \cdot 2 \cdot 3 = 2 \cdot 3 \cdot 2 \cdot 3 = 2^2 \cdot 3^2 \]

처럼 두 가지 방법으로 숫자 \( 36 \) 을 소인수분해 할 수 있습니다. 순서를 재배열해보니 같은 소인수분해에 도달았다는 것을 깨달을 수 있습니다.

 

사실 모든 수가 소수의 곱으로 나타낼 수 있다는 것은 귀납법 (Induction)을 사용하면 간단히 증명할 수 있습니다.

 

증명 (모든 수는 소인수분해가 가능하다)

\( n = 2 \) 는 소수임으로 소수 한 개의 곱으로 치부합니다. 이제 \( n \geq 3 \) 이라고 가정해봅시다. 만약 \( n \) 이 소수이면 이미 소인수분해가 되어있기 때문에 \( n \)이 소수가 아니라고 해봅시다. 그렇다면 \( 1 < m_1, m_2 < n \) 이며 \( n = m_1 m_2 \) 이 성립하는 \( m_1 \) 과 \( m_2 \)이 존재합니다. 강한 귀납법 (Strong Induction) 에 의해서 \( m_1 \) 과 \( m_2 \) 는 소인수분해가 가능합니다. 즉 \( n \) 은 소수의 곱으로 나타낼 수 있다는 것이 증명됩니다.

 

유일성을 증명하기 위해서는 다음 소정리 (Lemma)가 필요합니다.

 

소정리 3 (유클리드) 만약 \( p \) 가 소수이면 \( p | ab \Rightarrow p|a \text{ 혹은 } p |b \)가 성립한다. 

 

사실 이 반대도 성립합니다. 만약 \( n > 1 \) 이 

\[ n | ab \Rightarrow n|a \text{ 혹은 } n|b \]

을 성립한다고 합시다. 만약 소수가 아니라면 \( 1 < m_1, m_2 < n \) 과 \( n = m_1 m_2 \) 을 성립하는 \( n \) 의 약수 \(m_1\) 과 \(m_2 \) 이 존재합니다. 그렇다면 \( n | n = m_1 m_2 \Rightarrow n | m_1 \text{ 혹은 } n | m_2 \) 이 성립한다. 하지만 \( n | m_i  \Rightarrow n \leq m_i \) 임으로 모순이 생깁니다. 다시 말해서 \( n \) 은 소수입니다. 

 

다음 포스팅부터 위의 소정리를 증명할 준비를 할 예정입니다. 이제부터 소정리 3을 유클리드 소 정리라고 부르겠습니다.