Euclid's theorem

Original article: w:Euclid's theorem

This article is about the theorem on the infinitude of prime numbers. For the theorem on perfect numbers and Mersenne primes, see Euclid–Euler theorem. For the theorem on the divisibility of products by primes, see Euclid's lemma.

유클리드의 정리(Euclid's theorem)는 무한하게 많은 소수가 있다고 주장하는 숫자 이론에서 기본 명제입니다. 그것은 유클리드에 의해 그의 연구 원론(Elements)에서 처음으로 입증했습니다. 그 정리에 대한 몇 가지 증명이 있습니다.

Euclid's proof

유클리드는 그의 저서 Elements (Book IX, Proposition 20)에서 출판된 증명을 제공했으며, 여기에 의역됩니다.

소수 p₁, p₂, ..., p_n의 임의의 유한 목록을 생각해 보십시오. 적어도 하나의 추가적인 소수가 이 목록에 있지 않음을 보일 것입니다. P를 목록에 있는 모든 소수의 곱: P = p₁p₂...p_n이라고 놓고, q = P + 1이라고 놓습니다. 그런-다음 q는 소수이거나 소수가 아닙니다:

• 만약 q가 소수이면, 목록에 있지 않은 적어도 하나의 소수, 즉, q 자체가 있습니다.
• 만약 q가 소수가 아니면, 어떤 소수 인수(prime factor) p는 q를 나눕니다. 만약 이 인수 p가 목록에 있으면, 그것은 P를 나눌 것입니다 (왜냐하면 P는 목록에 있는 모든 각 숫자의 곱이기 때문입니다); 그러나 p는 방금 말했듯이 역시 P + 1 = q도 나눕니다. 만약 p가 P와 q도 나누면, p는 두 숫자의 차이도 나누어야 하며, 이는 (P + 1) − P 또는 단지 1입니다. 1을 나누는 소수가 없기 때문에, p는 목록에 포함될 수 없습니다. 이것은 목록에 있는 소수 외에 적어도 하나 이상의 소수가 존재함을 의미합니다.

이것은 모든 각 유한한 소수의 목록에 대해 목록에 없는 소수가 있음을 입증합니다. 원래 연구에서, 유클리드는 임의적인 소수의 목록을 작성할 수 없었기 때문에, 그가 자주 적용하는 방법, 즉 일반화-가능한 예제의 방법을 사용했습니다. 즉, 그는 세 개의 소수만을 선택하고 위에서 설명한 일반적인 방법을 사용하여 그가 항상 추가적인 소수를 찾을 수 있음을 입증합니다. 유클리드는 아마도 그의 독자들이 처음에 얼마나 많은 소수를 선택했는지에 관계없이 유사한 증명이 작동할 것이라고 확신한다고 가정했을 것입니다.

유클리드는 처음에 고려한 유한 집합(finite set)이 모든 소수를 포함한다는 가정에서 시작하여 모순에 의해 이 결과를 입증했다고 종종 잘못 보고되지만, 실제로는 직접 증명(direct proof) 방법인 경우에 의한 증명(proof by cases)입니다. 철학자 토르켈 프란젠(Torkel Franzén)은, 논리학에 관한 책에서, 다음과 같이 말합니다: "무한하게 많은 소수가 있다는 유클리드의 증명은 간접 증명이 아닙니다 [...] 그 논증은 때때로 'q₁, ..., q_n이 모두 소수라고 가정한다'라는 가정으로 대체함으로써 간접 증명으로 공식화됩니다. 어쨌든, 이 가정은 증명에도 사용되지 않았기 때문에 재구성은 무의미합니다."

Variations

유클리드의 증명에 대한 여러 가지 변형이 다음을 포함하여 존재합니다:

양의 정수 n의 팩토리얼(factorial) n! 은 2에서 n까지의 모든 각 정수로 나눌 수 있는데, 왜냐하면 그것이 그것들 모두의 곱이기 때문입니다. 따라서, n! + 1은 2에서 n까지의 정수 중 어떤 것으로 나눌 수 없습니다 (각 정수로 나눌 때 나머지가 1이 됩니다). 따라서 n! + 1은 소수이거나 n보다 큰 소수로 나눌 수 있습니다. 두 경우 모두에서, 모든 각 양의 정수 n에 대해, n보다 큰 적어도 하나의 소수가 있습니다. 결론은 소수의 개수가 무한하다는 것입니다.

Euler's proof

스위스 수학자 레온하르트 오일러(Leonhard Euler)에 의한 또 다른 증명은 모든 각 정수가 고유한 소수 인수분해를 가진다는 산술의 기본 정리(fundamental theorem of arithmetic)에 의존합니다. 오일러가 쓴 것 (이 현대 표기법을 갖는 것이 아니라, 현대 표준과 달리, 합과 곱에서 인수를 정수의 임의의 유한 집합으로 제한하지 않음)은 다음과 같은 명제와 동등합니다:

$\prod _{p\in P_{k}}{\frac {1}{1-{\frac {1}{p}}}}=\sum _{n\in N_{k}}{\frac {1}{n}},$

여기서 $P_{k}$는 k개의 처음 소수의 집합을 나타내고, $N_{k}$는 소수 인수가 모두 $P_{k}$에 있는 양의 정수의 집합입니다.

이를 보여주기 위해, 곱에서 각 인수를 기하 급수(geometric series)로 전개하고, 합에 걸쳐 곱을 분배합니다 (이것은 리만 제타 함수에 대한 오일러 곱 공식의 특수한 경우입니다).

${\begin{aligned}\prod _{p\in P_{k}}{\frac {1}{1-{\frac {1}{p}}}}&=\prod _{p\in P_{k}}\sum _{i\geq 0}{\frac {1}{p^{i}}}\\&=\left(\sum _{i\geq 0}{\frac {1}{2^{i}}}\right)\cdot \left(\sum _{i\geq 0}{\frac {1}{3^{i}}}\right)\cdot \left(\sum _{i\geq 0}{\frac {1}{5^{i}}}\right)\cdot \left(\sum _{i\geq 0}{\frac {1}{7^{i}}}\right)\cdots \\&=\sum _{\ell ,m,n,p,\ldots \geq 0}{\frac {1}{2^{\ell }3^{m}5^{n}7^{p}\cdots }}\\&=\sum _{n\in N_{k}}{\frac {1}{n}}.\end{aligned}}$

끝에서 두 번째 합에서 소수의 모든 각 곱은 정확하게 한 번 나타나고, 따라서 산술의 기본 정리에 의해 마지막 상등은 참입니다. 이 결과에 대한 그의 첫 번째 따름정리에서, 오일러는 $\infty$와 유사한 기호로 « 절대 무한대 »를 표시하고 명제에서 무한 합이 « 값 » $\log \infty$와 같다고 쓰며, 따라서 무한 곱도 같습니다 (현대에서 용어 이것은 조화 급수의 $x$까지의 부분 합이 $\log x$와 같이 점근적으로 발산한다고 말하는 것과 같습니다). 그런-다음 그의 두 번째 따름정리에서 오일러는 그 곱이 유한 값 2로 수렴한다고 주목합니다:

$\prod _{n\geq 2}{\frac {1}{1-{\frac {1}{n^{2}}}}}$

그리고 결과적으로 제곱보다 더 많은 소수가 있다는 것입니다 («  sequitur infinities plures esse numeros primos »). 이것은 유클리드의 정리를 입증합니다.

Symbol used by Euler to denote infinity

같은 논문 (정리 19)에서, 오일러는 사실 위의 상등을 그 이전에는 알려지지 않았던 훨씬 더 강력한 정리, 즉 다음 급수가 발산한다고 입증하기 위해 사용했습니다:

$\sum _{p\in P}{\frac {1}{p}}$

여기서 P는 모든 소수의 집합을 나타냅니다 (오일러는 현대 용어로 이 급수의 $x$까지의 부분 합이 $\log \log x$처럼 점근적으로 행동한다고 말하는 것과 동등한 무한 합 $=\log \log \infty$라고 씁니다).

Erdős's proof

폴 에르되시(Paul Erdős)는 역시 산술의 기본 정리에 의존하는 증명을 제시했습니다. 모든 각 양의 정수는 제곱-없는(square-free) 숫자와 제곱 숫자 rs²로의 고유한 인수분해를 가집니다. 예를 들어, 75,600 = 2⁴ 3³ 5² 7¹ = 21 ⋅ 60²입니다.

N을 양의 정수라고 놓고, k를 N보다 작거나 같은 소수의 개수라고 놓습니다. 그것들 소수를 p₁, ... , p_k라고 합니다. N보다 작거나 같은 임의의 양의 정수 a는 다음 형식으로 쓸 수 있습니다:

$a=\left(p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{k}^{e_{k}}\right)s^{2},$

여기서 각 e_i는 0 또는 1 중 하나입니다. a의 제곱-없는 부분을 형성하는 방법에는 2^k 가지가 있습니다. 그리고 s²는 많아야 N일 수 있으므로, $s\leq {\sqrt {N}}$입니다. 따라서, 많아야 $2^{k}{\sqrt {N}}$ 개의 숫자가 이 형식으로 작성될 수 있습니다. 다시 말해서,

$N\leq 2^{k}{\sqrt {N}}.$

또는 N보다 작거나 같은 소수의 개수, k를 다시 정렬하는 것은 1/2log₂ N보다 크거나 같습니다. N은 임의적이므로, N을 적절하게 선택함으로써 k는 원하는 만큼 커질 수 있습니다.

Furstenberg's proof

Main article: Furstenberg's proof of the infinitude of primes

1950년대에, 힐렐 퓌르스텐베르크(Hillel Furstenberg)는 점-집합 토폴로지(point-set topology)를 사용하여 모순에 의한 증명을 도입했습니다.

부분집합 U ⊆ Z를 열린 집합인 것과 그것이 빈 집합, ∅이거나, 그것이 산술 수열 (a ≠ 0에 대해) S(a, b)의 합집합인 것은 필요충분 조건이라고 선언함으로써 균등 간격 정수 토폴로지(evenly spaced integer topology)라고 불리는 정수 Z에 대한 토폴로지를 정의하십시오, 여기서

$S(a,b)=\{an+b\mid n\in \mathbb {Z} \}=a\mathbb {Z} +b.$

그런-다음 정수의 유한 집합이 열릴 것일 수 없다는 속성과 기본 집합 S(a, b)가 열린 것과 닫힌 것 둘 다라는 속성에서 모순이 발생하는데, 왜냐하면 다음은

$\mathbb {Z} \setminus \{-1,+1\}=\bigcup _{p\mathrm {\,prime} }S(p,0)$

여집합이 유한하기 때문에 닫힐 수 없지만, 그것이 닫힌 집합의 유한 합집합이기 때문에 닫혀 있습니다.

Recent proofs

Proof using the inclusion-exclusion principle

John Paul Pinasco는 다음 증명을 작성했습니다.

p₁, ..., p_N을 가장 작은 N 소수라고 놓습니다. 그런-다음 포함-제외 원리(inclusion–exclusion principle)에 의해, 소수 중 하나로 나눌 수 있는 x보다 작거나 같은 양의 정수의 개수는 다음과 같습니다:

${\begin{aligned}1+\sum _{i}\left\lfloor {\frac {x}{p_{i}}}\right\rfloor -\sum _{i<j}\left\lfloor {\frac {x}{p_{i}p_{j}}}\right\rfloor &+\sum _{i<j<k}\left\lfloor {\frac {x}{p_{i}p_{j}p_{k}}}\right\rfloor -\cdots \\&\cdots \pm (-1)^{N+1}\left\lfloor {\frac {x}{p_{1}\cdots p_{N}}}\right\rfloor .\qquad (1)\end{aligned}}$

x로 나누고 x → ∞라고 놓으면 다음을 제공합니다:

$\sum _{i}{\frac {1}{p_{i}}}-\sum _{i<j}{\frac {1}{p_{i}p_{j}}}+\sum _{i<j<k}{\frac {1}{p_{i}p_{j}p_{k}}}-\cdots \pm (-1)^{N+1}{\frac {1}{p_{1}\cdots p_{N}}}.\qquad (2)$

이것은 다음과 같이 쓸 수 있습니다:

$1-\prod _{i=1}^{N}\left(1-{\frac {1}{p_{i}}}\right).\qquad (3)$

만약 p₁, ..., p_N 이외의 다른 소수가 존재하면, (1)에서 표현은 $\lfloor x\rfloor$와 같고 (2)에서 표현은 1과 같지만, 분명히 (3)에서 표현은 1과 같지 않습니다. 따라서, p₁, ..., p_N보다 더 많은 소수가 있어야 합니다.

Proof using Legendre's formula

2010년에, Junho Peter Whang는 다음과 같은 모순에 의한 증명을 발표했습니다. k를 양의 정수라고 놓습니다. 그런-다음 르장드르의 공식(Legendre's formula) (때때로 드 폴리냐크(de Polignac)로 공인된)에 따라,

$k!=\prod _{p{\text{ prime}}}p^{f(p,k)}$

여기서

$f(p,k)=\left\lfloor {\frac {k}{p}}\right\rfloor +\left\lfloor {\frac {k}{p^{2}}}\right\rfloor +\cdots .$

$f(p,k)<{\frac {k}{p}}+{\frac {k}{p^{2}}}+\cdots ={\frac {k}{p-1}}\leq k.$

그러나 유한하게 많은 소수만 존재한다면,

$\lim _{k\to \infty }{\frac {\left(\prod _{p}p\right)^{k}}{k!}}=0,$

(분수의 분자는 하나씩 지수적(singly exponentially)으로 증가하는 반면 스털링의 근사에 의해 분모는 하나씩 지수적으로 증가하는 것보다 더 빠르게 증가합니다), 각 k에 대해 분자가 분모보다 크거나 같다는 사실과 모순됩니다.

Proof by construction

Filip Saidak은 귀류법(reductio ad absurdum) 또는 유클리드의 보조정리 (소수 p가 ab를 나누면 그것은 a 또는 b를 나누어야 함)를 사용하지 않는 다음과 같은 구성에 의한 증명(proof by construction)을 제공했습니다.

각각의 자연수 (> 1)는 적어도 하나의 소수 인수를 가지고 있고, 두 개의 연속된 숫자 n과 (n + 1)에는 공통된 인수가 없기 때문에, 곱 n(n + 1)은 숫자 n 자체보다 더 많은 다른 소수 인수를 가집니다. 따라서 프로닉 숫자(pronic numbers)의 체인은 다음과 같습니다:
1×2 = 2 {2},    2×3 = 6 {2, 3},    6×7 = 42 {2, 3, 7},    42×43 = 1806 {2, 3, 7, 43},    1806×1807 = 3263442 {2, 3, 7, 43, 13, 139}, · · ·
무제한으로 증가하는 일련의 소수의 집합을 제공합니다.

Proof using the incompressibility method

k개의 소수 (p₁, ..., p_k)만 있다고 가정합니다. 산술의 기본 정리(fundamental theorem of arithmetic)에 의해, 임의의 양의 정수 n은 다음과 같이 나타낼 수 있습니다: $$n={p_{1}}^{e_{1}}{p_{2}}^{e_{2}}\cdots {p_{k}}^{e_{k}},$$ 여기서 비-음의 정수 지수 e_i는 유한한 크기의 소수 목록과 함께 숫자를 재구성하기에 충분합니다. 모든 i에 대해 $p_{i}\geq 2$이므로, 모든 i에 대해 $e_{i}\leq \lg n$을 따릅니다 (여기서 $\lg$는 밑수-2 로그를 나타냅니다). 이것은 다음 크기의 n에 대한 인코딩을 산출합니다 (큰 O 표기법 사용):

$O({\text{prime list size}}+k\lg \lg n)=O(\lg \lg n)$ bits.

이것은 $N=O(\lg n)$ 비트를 사용하는 이진법으로 n을 직접 나타내는 것보다 훨씬 효율적인 인코딩입니다. 무손실 데이터 압축(lossless data compression)에서 확립된 결과에 따르면 일반적으로 N비트 정보를 N비트 미만으로 압축할 수 없습니다. 위의 표현은 $\lg \lg n=o(\lg n)$이므로 n이 충분히 클 때 이를 훨씬 위반합니다. 따라서, 소수의 개수는 유한하지 않아야 합니다.

Stronger results

이 섹션의 정리는 유클리드의 정리와 다른 결과를 동시에 암시합니다.

Dirichlet's theorem on arithmetic progressions

Main article: Dirichlet's theorem on arithmetic progressions

디리클레의 정리는 임의의 두 개의 양의 서로소(coprime) 정수 a와 d에 대해, a + nd 형식의 무한하게 많은 소수가 있다고 말하며, 여기서 n은 역시 양의 정수입니다. 다시 말해서, a 모듈로 d와 합동인 무한하게 많은 소수가 있습니다.

Prime number theorem

Main article: Prime number theorem

π(x)를 임의의 실수 x에 대해 x보다 작거나 같은 소수의 개수를 제공하는 소수-세는 함수(prime-counting function)라고 놓습니다. 소수 정리는 그런-다음 x가 경계 없이 증가함에 따라 두 함수 π(x)와 x / log x의 몫의 극한이 1이라는 의미에서, x / log x가 π(x)에 대한 좋은 근사라고 말합니다:

$\lim _{x\rightarrow \infty }{\frac {\pi (x)}{x/\log(x)}}=1.$

점근적 표기법(asymptotic notation)을 사용하여, 이 결과는 다음과 같이 다시 말할 수 있습니다:

$\pi (x)\sim {\frac {x}{\log x}}.$

이것은 유클리드의 정리를 산출하는데, 왜냐하면 $\lim _{x\rightarrow \infty }{\frac {x}{\log x}}=\infty .$

Bertrand–Chebyshev theorem

숫자 이론(number theory)에서, 베르트랑의 공준(Bertrand's postulate)은 임의의 정수 $n>1$에 대해, 항상 다음임을 만족하는 적어도 하나의 소수가 존재한다고 말하는 정리입니다:

$n<p<2n.$

베르트랑-체비쇼프 정리는 $\pi (x)$와의 관계로 나타낼 수도 있으며, 여기서 $\pi (x)$는 소수-세는 함수(prime-counting function) ($x\,$보다 작거나 같은 소수의 개수)입니다:

$\pi (x)-\pi ({\tfrac {x}{2}})\geq 1,$ for all $x\geq 2.$

이 명제는 1845년 조제프 베르트랑(Joseph Bertrand) (1822–1900)에 의해 처음 추측되었습니다. 베르트랑 자신은 구간 [2, 3 × 10⁶]의 모든 숫자에 대해 자신의 명제를 확인했습니다. 그의 추측은 1852년 체비쇼프 (1821–1894)에 의해 완전하게 입증되었고 따라서 베르트랑–체비쇼프 정리(Bertrand–Chebyshev theorem) 또는 체비쇼프의 정리(Chebyshev's theorem)라고도 불립니다.

External links

• Weisstein, Eric W. "Euclid's Theorem". MathWorld.
• Euclid's Elements, Book IX, Prop. 20 (Euclid's proof, on David Joyce's website at Clark University)