소수 의 집합을
P
⊂
Z
+
{\displaystyle \mathbb {P} \subset \mathbb {Z} ^{+}}
라고 하자. 산술의 기본 정리 에 따르면, 임의의 양의 정수
n
∈
Z
+
{\displaystyle n\in \mathbb {Z} ^{+}}
에 대하여, 곱하여
n
{\displaystyle n}
이 되는 소수의 유한 중복집합 이 유일하게 존재한다. 즉, 다음 성질을 만족시키는
p
1
,
…
,
p
k
⊂
P
{\displaystyle p_{1},\dots ,p_{k}\subset \mathbb {P} }
및
r
1
,
…
,
r
k
∈
Z
+
{\displaystyle r_{1},\dots ,r_{k}\in \mathbb {Z} ^{+}}
가 존재하며, 이는
i
=
1
,
…
,
k
{\displaystyle i=1,\dots ,k}
의 순열 을 무시하면 유일하다.
n
=
p
1
r
1
p
2
r
2
⋯
p
k
r
k
{\displaystyle n=p_{1}^{r_{1}}p_{2}^{r_{2}}\cdots p_{k}^{r_{k}}}
만약
n
=
1
{\displaystyle n=1}
인 경우,
k
=
0
{\displaystyle k=0}
이며, 이 소수 중복집합은 공집합이 된다.
추상대수학 의 용어를 사용하면, 이는 정수의 환
Z
{\displaystyle \mathbb {Z} }
가 유일 인수 분해 정역 이라는 명제와 동치 이다.
이 정리의 증명은 다음과 같은 두 단계로 나뉜다.
첫 번째로 1보다 큰 양의 정수가 소수의 곱으로 표현할 수 있음을 증명한다. 1보다 큰 양의 정수
n
{\displaystyle n}
의 두 번째로 작은 약수는 반드시 소수여야한다.(첫 번째로 작은 약수는 1이다.) 만약
m
{\displaystyle m}
이 두 번째로 작은 약수이고, 소수가 아니라고 한다면 (즉 합성수라면), 합성수의 정의에 의해서
1
<
l
<
m
{\displaystyle 1<l<m}
이면서
m
{\displaystyle m}
을 나누는 양의 정수
l
{\displaystyle l}
이 존재하게 되고, 따라서
l
{\displaystyle l}
은
n
{\displaystyle n}
도 나눌 수 있기 때문에,
m
{\displaystyle m}
이 두 번째로 작은 약수라는 가정에 모순이 생긴다. 따라서
n
{\displaystyle n}
은 반드시 소수인 약수를 갖게 되며 이를 다음과 같이 표현할 수 있다.
n
=
p
1
n
1
{\displaystyle n=p_{1}n_{1}}
만약,
n
1
{\displaystyle n_{1}}
이 소수라면, 증명은 여기서 종료된다. 하지만,
n
1
{\displaystyle n_{1}}
가 소수가 아니라면,
n
1
{\displaystyle n_{1}}
역시 1을 제외한 약수 중에 가장 작은 약수를 소수로 갖기 때문에 다음과 같이 표현할 수 있다.
n
=
p
1
p
2
n
2
{\displaystyle n=p_{1}p_{2}n_{2}}
이를 소수만 남을때까지 반복 할 수 있기 때문에, 따라서, 1보다 큰 모든 양의 정수는, 소수의 곱으로 표현 가능하다.
두 번째로, 그렇게 표현한 소수의 곱이 (각 인수들의 자리바꿈을 제외한다면) 유일함을 귀류법 으로 증명한다.
만약, 소수의 곱이 유일하지 않은 1보다 큰 양의 정수가 있다고 가정해 보자. 그 수 중에서 제일 작은 수를 n 이라고 한다면,
n
=
p
1
p
2
p
3
.
.
.
p
k
=
q
1
q
2
q
3
.
.
.
q
l
,
{\displaystyle n=p_{1}p_{2}p_{3}...p_{k}=q_{1}q_{2}q_{3}...q_{l},}
(
p
1
≤
p
2
≤
p
3
≤
.
.
.
≤
p
k
,
q
1
≤
q
2
≤
q
3
≤
.
.
.
≤
q
l
{\displaystyle p_{1}\leq p_{2}\leq p_{3}\leq ...\leq p_{k},q_{1}\leq q_{2}\leq q_{3}\leq ...\leq q_{l}}
이고,
p
i
{\displaystyle p_{i}}
와
q
j
{\displaystyle q_{j}}
는 소수, 그리고
p
i
≠
q
j
{\displaystyle p_{i}\neq q_{j}}
)
(
p
i
=
q
j
{\displaystyle p_{i}=q_{j}}
이면,
n
′
=
n
p
i
=
n
q
j
<
n
{\displaystyle n'={\frac {n}{p_{i}}}={\frac {n}{q_{j}}}<n}
인
n
′
{\displaystyle n'}
을 얻을 수 있는데 이는 소수의 곱이 유일하지 않은 1 보다 큰 정수 중 가장 작은 수가 n이라는 가정과 모순된다.)
한편
p
1
2
≤
n
,
q
1
2
≤
n
{\displaystyle p_{1}^{2}\leq n,q_{1}^{2}\leq n}
이고
p
1
2
{\displaystyle p_{1}^{2}}
과
q
1
2
{\displaystyle q_{1}^{2}}
은 동시에
n
{\displaystyle n}
이 될 수 없으므로,
0
<
p
1
q
1
<
n
{\displaystyle 0<p_{1}q_{1}<n}
N
=
n
−
p
1
q
1
{\displaystyle N=n-p_{1}q_{1}}
이라고 한다면,
0
<
N
<
n
{\displaystyle 0<N<n}
이고, 또한
p
1
|
N
{\displaystyle p_{1}|N}
,
q
1
|
N
{\displaystyle q_{1}|N}
이기 때문에,
N
{\displaystyle N}
의 유일한 소인수분해의 표현에는
p
1
{\displaystyle p_{1}}
과
q
1
{\displaystyle q_{1}}
가 동시에 존재하여야 한다.
따라서,
p
1
q
1
|
N
{\displaystyle p_{1}q_{1}|N}
이므로
N
=
p
1
q
1
S
{\displaystyle N=p_{1}q_{1}S}
(
S
{\displaystyle S}
는 양의정수)
n
=
N
+
p
1
q
1
=
p
1
q
1
(
S
+
1
)
{\displaystyle n=N+p_{1}q_{1}=p_{1}q_{1}(S+1)}
양변을
p
1
{\displaystyle p_{1}}
으로 나누면
n
p
1
=
q
1
(
S
+
1
)
{\displaystyle {\frac {n}{p_{1}}}=q_{1}(S+1)}
p
2
p
3
p
4
.
.
.
p
k
=
q
1
(
S
+
1
)
{\displaystyle p_{2}p_{3}p_{4}...p_{k}=q_{1}(S+1)}
, 즉
q
1
|
p
2
p
3
p
4
.
.
.
p
k
{\displaystyle q_{1}|p_{2}p_{3}p_{4}...p_{k}}
그러나
n
p
1
{\displaystyle {\frac {n}{p_{1}}}}
는
n
{\displaystyle n}
보다 작기 때문에 소인수분해가 유일하고 ,
q
1
≠
p
i
{\displaystyle q_{1}\neq p_{i}}
이면서, 동시에
q
1
{\displaystyle q_{1}}
은 소수이므로, 소수의 곱이 유일하지 않는 양의 정수가 있다는 가정은 모순이다.