오일러의 증명: 소수는 무한히 존재한다
정리
소수는 무한히 많이 존재한다.
증명
전략: 어떤 방법을 사용하든 같은 결과에만 도달한다면야 상관은 없지만, 정말 특이하게 풀어냈다면 그 자체로 공부할 가치가 있다. 유클리드의 증명처럼 단순 명료 깔끔한 맛은 없지만 정수론의 문제를 해석적인 툴로 해결했다는 점이 매우 흥미롭다. 오일러가 남긴 많은 증명들이 그렇듯 한 번 보면 잊기 힘들 정도의 충격을 선사한다. 천재의 발상을 따라 증명 자체를 음미해보도록 하자.
조화급수 $$ \sum_{ n = 1 }^{ \infty } {{1} \over {n}} = 1 + {{1} \over {2}} + {{1} \over {3}} + {{1} \over {4}} + {{1} \over {5}} + {{1} \over {6}} + \cdots $$ 를 생각해보자. $n$ 이 소수의 거듭제곱인 것들로 묶어내면 $$ \sum_{ n = 1 }^{ \infty } {{1} \over {n}} = 1 + \left( {{1} \over {2}} + {{1} \over {4}} + \cdots \right) + \left( {{1} \over {3}} + {{1} \over {9}} + \cdots \right) + \left( {{1} \over {5}} + {{1} \over {25}} + \cdots \right) + \cdots+ {{1} \over {6}} + \cdots $$ 한편 산술의 기본정리에 의해, 하나의 자연수와 하나의 소인수분해는 일대일 대응을 갖는다. 예를 들면 $6= 2 \cdot 3$ 이므로, $\displaystyle \left( {{1} \over {2}} + {{1} \over {4}} + \cdots \right)$ 와 $\displaystyle \left( {{1} \over {3}} + {{1} \over {9}} + \cdots \right)$ 에서 각각 $\displaystyle {{1} \over {2}}$ 과 $\displaystyle {{1} \over {3}}$ 를 뽑아 곱하면 정확하게 $\displaystyle {{1} \over {6}}$ 하나가 나타나는 것이다. 어떤 자연수든 소수의 거듭제곱들 사이에서 뽑아내서 곱하면 정확히 하나가 만들어지므로, 조화급수는 $$ \sum_{ n = 1 }^{ \infty } {{1} \over {n}} = \left( 1 + {{1} \over {2}} + {{1} \over {4}} + \cdots \right) \left( 1 + {{1} \over {3}} + {{1} \over {9}} + \cdots \right) \left( 1 + {{1} \over {5}} + {{1} \over {25}} + \cdots \right) \cdots $$ 으로 나타낼 수 있다. 기하급수로 다시 정리하면 $$ \sum_{ n = 1 }^{ \infty } {{1} \over {n}} = \left( {{1} \over {1 - {{1} \over {2}} }} \right) \left( {{1} \over {1 - {{1} \over {3}} }} \right) \left( {{1} \over {1 - {{1} \over {5}} }} \right) \cdots $$ 간결하게 곱의 꼴로 나타내면 소수 $p$ 에 대해 $$ \sum_{ n = 1 }^{ \infty } {{1} \over {n}} = \prod_{p} \left( 1 - {{1} \over {p}} \right)^{-1} $$ 한편 모든 소수 $p$ 에 대해 $$ \left( 1 - {{1} \over {p}} \right)^{-1} = {{1} \over {1 - {{1} \over {p}} }} > 1 $$ 이므로$\displaystyle \prod_{p} \left( 1 - {{1} \over {p}} \right)^{-1}$ 가 발산한다는 것은 소수 $p$ 가 무한히 존재한다는 것이다. 물론 조화급수는 발산하므로 $$ \prod_{p} \left( 1 - {{1} \over {p}} \right)^{-1} = \sum_{ n = 1 }^{ \infty } {{1} \over {n}} = \infty $$ 이고, 따라서 소수는 무한히 존재한다.
■