유클리드의 정리

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

정의[편집]

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

|\mathbb P|=\aleph_0

증명[편집]

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

에우클레이데스의 증명[편집]

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

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

q=\prod_{p\in\mathbb P}+1

를 생각하자. 이 수는

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

이므로, 소수이어야 한다. 그러나

q>\max\mathbb P

이므로, q는 소수일 수 없으며, 이는 모순이다. 따라서, 소수의 수는 무한하다.

오일러의 증명[편집]

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

\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\frac1n=\infty

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

퓌르스텐베르크의 증명[편집]

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

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

\mathcal B=\left\{a\mathbb Z+b\colon a,b\in\mathbb Z,\;a\ne0\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는 무한집합이다.

참고 문헌[편집]

  1. (영어) Furstenberg, Harry (1955년). On the infinitude of primes. 《American Mathematical Monthly》 62 (5): 353. doi:10.2307/2307043. JSTOR 2307043. MR0068566.
  • (영어) 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.

바깥 고리[편집]