산술의 기본 정리 문서 원본 보기

{{위키데이터 속성 추적}}
'''산술의 기본 정리'''(算術의基本定理, {{llang|en|fundamental theorem of arithmetic}})는 모든 양의 [[정수]]는 유일한 [[소인수 분해]]를 갖는다는 정리이다.

== 정의 ==
[[소수 (수론)|소수]]의 집합을 <math>\mathbb P\subset\mathbb Z^+</math>라고 하자. '''산술의 기본 정리'''에 따르면, 임의의 양의 정수 <math>n\in\mathbb Z^+</math>에 대하여, 곱하여 <math>n</math>이 되는 소수의 유한 [[중복집합]]이 유일하게 존재한다. 즉, 다음 성질을 만족시키는 <math>p_1,\dots,p_k\subset\mathbb P</math> 및 <math>r_1,\dots,r_k\in\mathbb Z^+</math>가 존재하며, 이는 <math>i=1,\dots,k</math>의 [[순열]]을 무시하면 유일하다.
:<math>n = p_1^{r_1} p_2^{r_2} \cdots p_k^{r_k}</math>
만약 <math>n=1</math>인 경우, <math>k=0</math>이며, 이 소수 중복집합은 공집합이 된다.

[[추상대수학]]의 용어를 사용하면, 이는 정수의 환 <math>\mathbb Z</math>가 [[유일 인수 분해 정역]]이라는 명제와 [[동치]]이다.

== 증명 ==
이 정리의 증명은 다음과 같은 두 단계로 나뉜다.
=== 1 단계 ===
첫 번째로 1보다 큰 양의 정수가 소수의 곱으로 표현할 수 있음을 증명한다. 1보다 큰 양의 정수 <math>n</math>의 두 번째로 작은 약수는 반드시 소수여야한다.(첫 번째로 작은 약수는 1이다.) 만약 <math>m</math>이 두 번째로 작은 약수이고, 소수가 아니라고 한다면 (즉 합성수라면), 합성수의 정의에 의해서  <math> 1<l<m </math>이면서 <math>m</math>을 나누는 양의 정수 <math>l</math>이 존재하게 되고, 따라서 <math>l</math>은 <math>n</math>도 나눌 수 있기 때문에, <math>m</math>이 두 번째로 작은 약수라는 가정에 모순이 생긴다. 따라서 <math>n</math>은 반드시 소수인 약수를 갖게 되며 이를 다음과 같이 표현할 수 있다.

<math> n=p_1n_1 </math>

만약,<math>n_1</math>이 소수라면, 증명은 여기서 종료된다. 하지만, <math>n_1</math>가 소수가 아니라면, 
<math> n_1</math> 역시 1을 제외한 약수 중에 가장 작은 약수를 소수로 갖기 때문에 다음과 같이 표현할 수 있다.

<math> n=p_1p_2n_2 </math>

이를 소수만 남을때까지 반복 할 수 있기 때문에, 따라서, 1보다 큰 모든 양의 정수는, 소수의 곱으로 표현 가능하다.

=== 2 단계 ===
두 번째로, 그렇게 표현한 소수의 곱이 (각 인수들의 자리바꿈을 제외한다면) 유일함을 [[귀류법]]으로 증명한다. 
만약, 소수의 곱이 유일하지 않은 1보다 큰 양의 정수가 있다고 가정해 보자. 그 수 중에서 제일 작은 수를 n 이라고 한다면,

<math>n=p_1p_2p_3...p_k=q_1q_2q_3...q_l,</math> (<math>p_1 \le p_2 \le p_3 \le ... \le p_k, q_1 \le q_2 \le q_3 \le ... \le q_l</math> 이고, <math>p_i</math> 와 <math>q_j</math>는 소수, 그리고 <math>p_i \ne q_j</math>)

(<math>p_i=q_j</math>이면, <math> n'=\frac{n}{p_i}=\frac{n}{q_j}<n</math> 인 <math> n'</math> 을 얻을 수 있는데 이는 소수의 곱이 유일하지 않은 1 보다 큰 정수 중 가장 작은 수가 n이라는 가정과 모순된다.)

한편 <math>p_1^2 \le n, q_1^2 \le n</math>이고 <math>p_1^2</math>과 <math>q_1^2</math>은 동시에 <math>n</math>이 될 수 없으므로, <math>0<p_1q_1<n</math>

<math>N=n-p_1q_1</math> 이라고 한다면, <math>0<N<n</math> 이고,  또한 <math>p_1|N</math>, <math>q_1|N</math> 이기 때문에, <math>N</math>의 유일한 소인수분해의 표현에는 <math>p_1</math>과 <math>q_1</math>가 동시에 존재하여야 한다.

따라서, <math>p_1q_1|N</math>이므로 <math>N=p_1q_1S</math> (<math>S</math>는 양의정수)

<math>n=N+p_1q_1=p_1q_1(S+1)</math>

양변을 <math>p_1</math>으로 나누면

<math>\frac{n}{p_1}=q_1(S+1)</math>

<math>p_2p_3p_4...p_k=q_1(S+1)</math>, 즉 <math>q_1|p_2p_3p_4...p_k</math>

그러나 <math>\frac{n}{p_1}</math>는 <math>n</math> 보다 작기 때문에 소인수분해가 유일하고 ,<math>q_1 \ne p_i</math>이면서, 동시에 <math>q_1</math>은 소수이므로, 소수의 곱이 유일하지 않는 양의 정수가 있다는 가정은 모순이다.

== 같이 보기 ==
* [[대수학의 기본 정리]]
* [[리만 제타 함수]]
* [[오일러의 곱셈 공식]]
* [[유일 인수 분해 정역]]
* [[제곱수]]

[[분류:소수에 관한 정리]]
[[분류:인수분해]]
[[분류:기본 정리]]