유클리드의 정리

수론에서 유클리드의 정리(Euclid의定理, 영어: Euclid’s theorem)는 무한한 수의 소수들이 존재한다는 정리이다.

정의

소수는 정확히 두 개의 양의 정수 약수를 갖는 양의 정수이다. 유클리드의 정리에 따르면, 소수의 집합 $\mathbb {P}$ 의 크기는 무한하다.

|\mathbb {P} |=\aleph _{0}

수천 년 동안에 유클리드의 정리의 수많은 증명들이 발표되었다.

이 증명은 기원전 3세기에 작성된 에우클레이데스의 《원론》 9권 정리 20번에 수록되어 있다.

귀류법을 사용하여, 소수의 개수가 유한하다고 가정하자. 그렇다면 수

q=\prod _{p\in \mathbb {P} }p+1

를 생각하자. 이 수는

q>\max \mathbb {P}

q\equiv 1{\pmod {p\in \mathbb {P} }}

이므로 모든 소수보다 크며, 소인수를 갖지 않는다. 이는 모순이다. 따라서, 소수의 수는 무한하다.

크리스티안 골드바흐는 1730년에 레온하르트 오일러에게 보내는 서신에서 페르마 수가 쌍마다 서로소 정수들의 무한 집합을 이룬다는 것을 보여 유클리드의 정리를 증명하였다.^[1]

레온하르트 오일러는 유클리드의 정리를 조화 급수를 사용하여 다음과 같이 증명하였다. 산술의 기본 정리에 따라, 모든 양의 정수는 유일한 소인수 분해를 가지므로, 분배 법칙을 사용하여 다음 식이 성립함을 쉽게 알 수 있다.

\prod _{p\in \mathbb {P} }{\frac {1}{1-1/p}}=\prod _{p\in \mathbb {P} }\sum _{k\geq 0}p^{-k}=\sum _{n=1}^{\infty }{\frac {1}{n}}=\infty

우변은 조화급수이며, 이는 발산한다는 것을 쉽게 보일 수 있다. 좌변은 유한한 수들의 곱이므로, 만약 $\mathbb {P}$ 가 유한 집합이라고 하면 좌변은 유한하게 되고, 등식이 성립할 수 없다. 따라서, $\mathbb {P}$ 는 무한 집합이다.

힐렐 퓌르스텐베르크는 다음과 같은 증명을 1955년에, 아직 학부 학생일 때 발표하였다.^[2]

$\mathbb {Z}$ 위에, 다음과 같은 기저 ${\mathcal {B}}$ 를 갖는 위상을 정의하자.

{\mathcal {B}}=\left\{a\mathbb {Z} +b\colon a,b\in \mathbb {Z} ,\;a\neq 0\right\}

즉, ${\mathcal {B}}$ 는 등차수열들의 집합이다. 모든 기저 집합이 무한 집합이므로, 모든 열린집합은 무한 집합이다.

이 위상에서, 기저의 열린집합 $B\in {\mathcal {B}}$ 들은 다음과 같이 모두 열린닫힌집합이다.

a\mathbb {Z} +b=\mathbb {Z} \setminus \bigcup _{c=b+1}^{a+b-1}(a\mathbb {Z} +c)

이제, 다음 등식이 성립함을 쉽게 알 수 있다.

\{1,-1\}=\mathbb {Z} \setminus \bigcup _{p\in \mathbb {P} }p\mathbb {Z}

만약 $\mathbb {P}$ 가 유한 집합이라면, 우변은 유한 개의 닫힌집합의 합집합의 여집합이므로, 열린집합이다. 그러나 좌변은 유한 집합이므로 열린집합일 수 없다. 따라서, $\mathbb {P}$ 는 무한 집합이다.

↑ Aigner, Martin; Ziegler, Günter M. 《Proofs from The Book》 (영어) 4판. Springer. 3쪽. doi:10.1007/978-3-642-00856-6. ISBN 978-3-642-00855-9.
↑ Furstenberg, Harry (1955). “On the infinitude of primes”. 《American Mathematical Monthly》 (영어) 62 (5): 353. doi:10.2307/2307043. JSTOR 2307043. MR 0068566.

Pinasco, Juan Pablo (2009년 2월). “New proofs of Euclid’s and Euler’s theorems”. 《The American Mathematical Monthly》 (영어) 116 (2): 172–174. JSTOR 27642694.
Rubinstein, Michael (1993년 4월). “A formula and a proof of the infinitude of the primes”. 《The American Mathematical Monthly》 (영어) 100 (4): 388–392. JSTOR 2324965.
Wunderlich, M. (1965년 3월). “Another proof of the infinite primes theorem”. 《The American Mathematical Monthly》 (영어) 72 (3): 305–305. JSTOR 2313710.
Aldaz, J. M.; A. Bravo (2003년 2월). “Euclid’s argument on the infinitude of primes”. 《The American Mathematical Monthly》 (영어) 110 (2): 141–142. doi:10.2307/3647773. JSTOR 3647773.
Cosgrave, John B. (1989년 4월). “A remark on Euclid’s proof of the infinitude of primes”. 《The American Mathematical Monthly》 (영어) 96 (4): 339–341. JSTOR 2324090.

Weisstein, Eric Wolfgang. “Euclid's theorem”. 《Wolfram MathWorld》 (영어). Wolfram Research.