소수의 무한성 증명

유클리드의 증명

귀류법으로 소수가 $n$개로 유한하다고 가정하고, 그 유한한 소수들의 집합을 $P=\left\{ p_1,\,p_2,\,\cdots,\,p_n \right\}$라 하고, 새로운 수 $N=p_1\,p_2\, \cdots \,p_n+1$을 정의하자. $N$은 $p_k$ ($k$는 $n$ 이하의 자연수)보다 큰 자연수이므로 $N \notin P$이다. 따라서 $N$은 합성수이므로, $\dfrac{N}{p_k} \in \mathbb{N}$이도록 하는 $p_k$가 존재해야 한다. $$\begin{eqnarray} && \dfrac{N}{p_k}=\dfrac{p_1\,p_2\,\cdots\,p_n+1}{p_k} \\ && =p_1\,p_2\,\cdots\,p_{k-1}\,p_{k+1}\,\cdots\,p_n+\dfrac{1}{p_k} \end{eqnarray}$$에서, $p_k>1$이므로 $\dfrac{1}{p_k} \notin \mathbb{N}$이다. 따라서 $\dfrac{N}{p_k} \in \mathbb{N}$이도록 하는 $p_k$는 존재하지 못한다. 모순이 발생하였으므로 소수는 무한하다.   $\blacksquare$

 

오일러의 증명

다음을 이용한다.

$$\sum_{n = 1}^{\infty}{\dfrac{1}{n}}=\infty$$

(증명은 https://exp-onential.tistory.com/16 참고)

귀류법으로 소수가 $k$개로 유한하다고 가정하고, 그 유한한 소수들을 $p_1$, $p_2$, $\cdots$, $p_k$라 하자. 이제, 다음 식 $$\displaystyle\sum_{n = 1}^{\infty}{\dfrac{1}{n}}$$을 생각하자. $$\begin{eqnarray}\sum_{n = 1}^{\infty}{\dfrac{1}{n}}&&=\dfrac{1}{1}+\dfrac{1}{2}+\dfrac{1}{3}+\dfrac{1}{4} \\ && \quad \ +\dfrac{1}{5}+\dfrac{1}{6}+\dfrac{1}{7}+\dfrac{1}{8} \cdots \\&& =1+\dfrac{1}{2}+\dfrac{1}{3}+\dfrac{1}{2^2} \\ && \quad \ + \dfrac{1}{5}+\dfrac{1}{2 \times 3}+\dfrac{1}{7}+\dfrac{1}{2^3}+\cdots\end{eqnarray}$$

더해지는 분수들의 분모를 소인수분해하면, 주어진 식이 다음과 같다는 사실을 알 수 있다.

$$\begin{eqnarray}\displaystyle\sum_{n = 1}^{\infty}{\dfrac{1}{n}}&&=(1+\dfrac{1}{p_1}+\dfrac{1}{p_1^2}+\cdots) \\ && \quad \times (1+\dfrac{1}{p_2}+\dfrac{1}{p_2^2}+\cdots) \\ && \quad \times \cdots \\ && \quad \times (1+\dfrac{1}{p_k}+\dfrac{1}{p_k^2}+\cdots)\\&&=\displaystyle\sum_{n = 0}^{\infty}{\dfrac{1}{p_1^n}} \displaystyle\sum_{n = 0}^{\infty}{\dfrac{1}{p_2^n}} \cdots \displaystyle\sum_{n = 0}^{\infty}{\dfrac{1}{p_k^n}} \end{eqnarray}$$

곱해지는 각각의 항들은 무한등비급수이므로$$\displaystyle\sum_{n = 0}^{\infty}{\dfrac{1}{p_i^n}}=\dfrac{1}{1-\dfrac{1}{p_i}}=\dfrac{p_i}{p_i-1}$$

이때, $p_i>1$이므로 $$\dfrac{p_i}{p_i-1}<2$$이다. 따라서, 식은 $$\displaystyle\sum_{n = 1}^{\infty}{\dfrac{1}{n}}=\dfrac{p_1-1}{p_1} \times \cdots \times \dfrac{p_k-1}{p_k}<2^k$$이게 된다. 이때 $k$는 정해진 자연수이므로, 식은 $2^k$보다 작은 값에서 수렴한다. 그러나 실제로는 이 식은 발산하므로, 모순이 발생하였다. 따라서 소수는 무한하다.   $\blacksquare$

 

골드바흐의 증명

$n \in \mathbb{N}_0$에 대하여 $F_n=2^{2^n}+1$로 정의되는 수를 페르마 수라고 한다. 이제, 페르마 수끼리는 모두 서로소임을 증명하자. 그러기 위하여 다음 등식을 이용한다.

$$\displaystyle\prod_{k=0}^n F_k = F_n-2$$

위의 등식의 증명은 수학적 귀납법을 이용한다.

1. $n=1$일 때 $F_0=3$이고, $F_1=5$이므로 성립한다.

2. $n=m-1$일 때 성립을 가정하면 $n=m$일 때

$$\begin{eqnarray} \displaystyle\prod_{k=0}^m F_k && =\left(\displaystyle\prod_{k=0}^{m-1} F_k \right)F_m =(F_m-2)F_m \\&& =(2^{2^m}-1)(2^{2^m}+1)=2^{2^{m+1}}-1 \\ && =F_{m+1}-2 \end{eqnarray}$$

이므로 성립한다.

위에서 $F_1F_2\cdots F_{n-2}F_{n-1}=F_n-2$임을 증명하였다. 이를 이용하여 모든 페르마 수끼리는 서로소임을 증명하자.

임의의 자연수 $k<n$에 대하여 $F_k$의 약수 $p$가 $F_n$을 나누려면 $2$도 나누어야 한다. 따라서 $F_k$와 $F_n$의 공약수는 $2$의 약수이다. 이때 페르마 수는 홀수이므로 공약수는 $1$만 가능하다. 따라서 임의의 두 페르마 수는 서로소이다.

만약 소수의 개수가 유한하다면 페르마 수의 소인수들 중 결국 겹치는 것이 존재할 것이다. 따라서 무한히 많은 페르마 수들이 모두 서로소라는 것은 곧 소수의 개수가 무한해야 함을 뜻한다.   $\blacksquare$

 

Exponential 17 김지하