정수론, 그 아홉 번째 이야기 | 산술의 기본정리

 

산술의 기본정리는 아래와 같은 정리를 의미하며, 일반적인 정수를 분석하는 데에 도움을 준다.

 

$n > 1$ 인 정수 $n$ 은 인수가 나타나는 순서를 고려하지 않을 때 소수들의 곱으로 유일하게 표현된다.

 

Proof :

$n$ 은 $1$ 보다 큰 정수이므로 소수 또는 합성수이다. 만약 $n$ 이 소수인 경우 더 증명할 것이 없다.

$n$이 합성수일 경우, $1 < d < n$ 이고 $d \mid n$ 인 정수 $d$ 가 존재한다.

이러한 정수 $d$ 중 가장 작은 것을 선택하여 $p_1$ 이라고 부르자.

 

만약 $p_1$ 이 소수가 아니라면, $1 < q < p_1$ 이고 $q \mid p_1$ 인 정수 $q$ 가 존재하는데,

$q \mid n$ 이므로 $p_1$ 이 $n$ 을 나누는 1이 아닌 최소의 정수임에 모순이다. 따라서 $p_1$ 은 소수.

 

그러므로 $n = p_1 n_1$ 으로 표현 가능하고, 이 때 $p_1$ 은 소수, $1 < n_1 < n$ 이다.

 

이 때, $n_1$ 이 소수이면 우리는 $n$ 을 소수의 곱으로 표현하였다.

만약 $n_1$ 이 소수가 아니라면, 우리는 위와 같은 방법을 반복하여 $n_1 = p_2 n_2$ 로 표현할 수 있다.

 

따라서 $n = p_1 p_2 n_2$ 이고, 이 때 $p_1, p_2$ 는 소수, $1 < n_2 < n_1 < n$ 이다.

 

그런데 $n_i$ 는 감소수열이므로 위와 같은 과정이 $n_i$ 에 대해 무한히 반복될 수는 없다.

 

따라서 유한 번의 과정 후에 $n_{k-1}$ 은 소수가 되고, 이 때 $n_{k-1} = p_k$ 라고 하면

$$n = p_1 p_2 \cdots p_k$$ 처럼 $n$ 을 소수의 곱으로 표현할 수 있다.

 

 

이제 $n$ 을 소수의 곱으로 표현하는 방법이 두 가지 존재한다고 가정하자.

$n = p_1 p_2 \cdots p_r = q_1 q_1 \cdots q_s$ 라고 하면, (단, $r \leq s$)

 

이 때, $p_i$ 와 $q_j$ 는 모두 순서이고, 오름차순으로 정렬되어있다고 하자. (이는 교환법칙에 의해 가능하다.)

 

이 때, $p_1 \mid q_1 q_2 \cdots q_s$ 이므로, 어떤 $k \in \mathbb{N}$ 에 대해 $p_1 = q_k$ 임을 알 수 있다.

소수 글에 이에 대한 증명이 있다.

 

따라서 $p_1 \geq q_1$ 이고, 같은 방법을 적용하여 $q_1 \geq p_1$ 따라서 $p_1 = q_1$ 이다.

 

그러므로 양 변을 $p_1$ 으로 나누어 $p_2 p_3 \cdots p_r = q_2 q_3 \cdots q_s$ 를 얻는다.

 

위와 같은 과정을 계속 반복하면 $p_2 = q_2$, $p_3 = q_3$, $\cdots$ $p_r = q_r$ 을 얻는다.

 

그런데 $q_i > 1$ 이므로 $r \neq s$ 이면 모순이다. 따라서 $r = s$ 이고

초기에 잡은 두 개의 표현은 결국 같은 것임을 알 수 있다.

 

이렇게 존재성과 유일성을 보여 산술의 기본정리 증명이 완성되었다.

 

 

위의 표현에서 같은 인수들을 거듭제곱으로 모아 다음과 같이 표현하기도 한다.

이렇게 산술의 기본정리를 이용하는 과정을 소인수분해라는 전문용어로 부르기도 한다.

 

모든 양의 정수 $n > 1$ 은 $i = 1, 2, \cdots r$ 에 대해 $k_i$ 는 양수, $p_i$ 는 $p_1 < p_2 < \cdots < p_r$      을 만족하는 소수일 때, 다음과 같은 형태로 표현할 수 있다. 이는 표준형 (Canonical form) 이라고 한다.$$n = {p_1}^{k_1} {p_2}^{k_2} \cdots {p_r}^{k_r}$$