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

 

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

 

$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\le 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\ge q_1$ 이고, 같은 방법을 적용하여 $q_1\ge 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\ne 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}$$