유클리드 정리

수론에서 유클리드의 정리는 무한히 많은 소수가 존재한다고 주장하는 기본적인 진술입니다. 그것은 유클리드에 의해 그의 작품 "요소"에서 처음으로 증명되었습니다. 그 정리에는 몇 가지 증명이 있습니다.

유클리드의 증명

유클리드는 여기에 비유된 그의 저작 <요소>(제9권, 명제 20)^[1]에 출판된 증명을 제시했습니다.^[2]

소수 p₁, p₂, ..., p의_n 임의의 유한한 목록을 생각해 보자. 이 목록에 없는 적어도 하나의 추가적인 소수가 존재함을 보일 것이다. P를 목록의 모든 소수의 곱이라 하자: P = pp... p. q = P + 1 이라고 하자. 그러면 q는 소수이거나 그렇지 않습니다.

• 만약 q가 소수라면, 목록에 없는 적어도 하나의 소수, 즉 q 자체가 더 있습니다.
• 만약 q가 소수가 아니라면, 어떤 소인수 p는 q를 나눕니다. 만약 이 소인수 p가 목록에 있다면, 그것은 P를 나눕니다(P는 목록에 있는 모든 수의 곱이므로); 그러나 p는 또한 방금 말한 것처럼 P + 1 = q를 나눕니다. 만약 p가 P와 q를 나눈다면, p는 (P + 1) - P 또는 단지 1인 두 숫자의 차이도^[3] 나누어야 합니다. 소수가 1을 나누지 않기 때문에 p는 목록에 있을 수 없습니다. 이것은 목록에 있는 것들보다 적어도 하나 이상의 소수가 더 존재한다는 것을 의미합니다.

이것은 모든 소수의 유한한 목록에 대해 목록에 없는 소수가 있다는 것을 증명합니다.^[4] 원작에서 유클리드는 임의의 소수 목록을 작성할 방법이 없었기 때문에 자주 적용하는 방법, 즉 일반화 가능한 예제의 방법을 사용했습니다. 즉, 그는 단지 세 개의 소수를 선택하고 위에서 설명한 일반적인 방법을 사용하여 항상 추가적인 소수를 찾을 수 있다는 것을 증명합니다. 유클리드는 아마도 독자들이 원래 몇 개의 소수를 선택했든 간에 비슷한 증명이 효과가 있을 것이라고 확신한다고 가정할 것입니다.^[5]

유클리드는 종종 처음에 고려된 유한 집합이 모든 소수를 포함한다는 가정에서 시작하여 모순에 의해 이 결과를 증명했다고 잘못 보고되지만 실제로는 경우에 의한 증명, 즉 직접적인 증명 방법입니다.^[6] 철학자 토르켈 프란젠(Torkel Franzén)은 논리학에 관한 책에서 "유클리드가 무한히 많은 소수가 있다는 증거는 간접적인 증거가 아닙니다."라고 말합니다. 주장은 때때로 'q₁, ...q가_n 모든 소수입니다'라는 가정으로 대체하여 간접적인 증거로 공식화됩니다. 그러나 이 가정은 증명에 사용되지도 않기 때문에 재규정은 무의미합니다."^[7]

변주곡

유클리드의 증명에는 다음과 같은 몇 가지 변형이 존재합니다.

양의 정수 n의 계승 n!은 2부터 n까지의 모든 정수로 나누어집니다. 따라서 n! + 1은 2부터 n까지의 정수 중 어느 것으로도 나눌 수 없습니다(각각으로 나누면 나머지가 1이 됩니다). 따라서 n! + 1은 n보다 큰 소수로 나뉠 수도 있습니다. 어느 경우든, 모든 양의 정수 n에 대하여 n보다 큰 소수가 적어도 하나 있습니다. 결론은 소수의 수가 무한하다는 것입니다.^[8]

오일러의 증명

스위스 수학자 레온하르트 오일러의 또 다른 증거는 모든 정수가 고유한 소인수분해를 갖는다는 산술의 기본 정리에 의존합니다. 오일러가 쓴 것은 (이 현대적 표기법을 사용하지 않고, 현대 표준과 달리, 합과 곱의 인수를 정수의 유한 집합으로 제한하지 않음) 우리가^[9] 가지고 있는 문장과 동등합니다.

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

여기서 ${\displaystyle {Pk}_{}}$ ${\$는 k개의 첫 번째 소수들의 집합을 나타내고$$ ${\displaystyle {Nk}_{}}${\$displaystyle N_{k}$는 소수들이$$ 모두 ${\displaystyle {Pk}_{}}$에 있는 양의 정수들의 집합입니다.$${\$displaystyle P_{k}}$

이를 보여주기 위해 곱의 각 인자를 기하급수로 확장하고, 곱을 합에 걸쳐 분배합니다(이는 리만 제타 함수에 대한 오일러 곱 공식의 특별한 경우입니다).

${\displaystyle {\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{align}}}$

소수의 모든 곱은 궁극적으로 한 번씩만 나타나고, 따라서 산술의 기본 정리에 의해 마지막 등식이 참입니다. $이$ 결과에 대한 그의 첫 번째 상관 관계에서 오일러는 ∞ ${\displaystyle$ \infty}와 유사한 기호로 « 절대 무한 »을 나타내고 문장의 무한 합은 « 값 » 로그 ⁡ ∞ {\displaystyle \log \infty}와 같다고 $적습니다$. 따라서 무한 곱도 동일합니다(현대 용어에서 이는 고조파 급수의 $최대$ x ${\displaystyle$ x$}$까지의 부분 합이 ${\displaystyle \mathrm{로그}}$ ⁡ x${\displaystyle$ $\$log x}처럼 점근적으로 발산한다고 말하는 것과 같습니다). 그런 다음 오일러는 그의 두 번째 상관식에서 다음과 같이 언급합니다.

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

유한 값 2로 수렴하고, 결과적으로 제곱보다 소수가 더 많다는 것(« 순서 무한은 numeros primos »). 이것은 유클리드의 정리를 증명합니다.^[10]

같은 논문에서 오일러는 실제로 위의 등식을 사용하여 그의 앞에 알려지지 않은 훨씬 더 강력한 정리, 즉 급수를 증명했습니다.

${\displaystyle \sum_{p\in P}{\frac {1}{p}}$

는 발산하며, 여기서 P는 모든 소수들의 집합을 나타냅니다(Euler는 무한합 = ${\displaystyle \mathrm{로그}\mathrm{}}$⁡ 로그 ⁡ ∞ {\displaystyle =\log \infty}, 이는 현대 용어에서 이 시리즈의 $최대$ x ${\displaystyle$ x$}$까지의 부분 합이 ${\displaystyle \mathrm{로그}}$ ⁡ $로그$⁡ x ${\displaystyle$\log x})처럼 점근적으로 동작한다고 말하는 것과 같습니다.

Erdős's proof

폴 에르트 ő스는 산술의 기본 정리에도 의존하는 증명을 내놓았습니다. 모든 양의 정수는 제곱이 없는 r과 제곱수로² 고유한 인수분해를 갖습니다. 예를 들어 75,600 = 2 3 5 7 = 21 ⋅ 60입니다.

N을 양의 정수라 하고, K를 N보다 작거나 같은 소수라고 하자. 이 소수들을 p₁, ..., p라고 부른다_k. N보다 작거나 같은 양의 정수 a는 다음과 같은 형태로 쓸 수 있습니다.

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

여기서 각 e는_i 0 또는 1입니다. a의 정사각형이 없는 부분을 형성하는 방법은^k 두 가지입니다. 그리고 s는 기껏해야 N일 수 있으므로 ≤ √N입니다. 따라서 최대 2개의 √N 숫자를 이 형식으로 작성할 수 있습니다. 다시 말해,

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

또는 n보다 작거나 같은 소수의 개수인 k를 재배열하면 1/2log₂ N보다 크거나 같습니다. N은 임의였으므로 N을 적절히 선택하면 k는 원하는 만큼 커질 수 있습니다.

퍼스텐버그의 증명

1950년대에 Hille Furstenberg는 점집합 위상을 사용하여 모순에 의한 증명을 도입했습니다.^[12]

빈 집합, ∅이거나 산술 수열들의 조합인 경우에만 부분집합 U ⊆ Z를 열린 집합으로 선언함으로써 정수 Z에 대한 위상을 정의합니다(≠ 0의 경우).

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

그러면 유한한 정수 집합은 열 수 없고, 기저 집합 S(a, b)가 열림과 닫힘을 동시에 갖는 성질로부터 모순이 뒤따릅니다. 이는 다음과 같습니다.

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

여집합은 유한하므로 닫힐 수 없지만, 닫힌 집합의 유한 결합이므로 닫힙니다.

최근 증명

포함-배제 원리를 이용한 증명

후안 파블로 피나스코는 다음과 같은 증거를 썼습니다.^[13]

p₁, ..., p를_N 가장 작은 N개의 소수라고 하자. 포함-배제 원리에 의해, x보다 작거나 같은 양의 정수들 중 하나로 나누어지는 수는

${\displaystyle {\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 → ∞가 다음을 제공하도록 합니다.

${\displaystyle \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)}$

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

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

p, ..., p 이외의 다른 소수가 존재하지 않는 경우, (1)의 $식은$⌋ x ⌊ {\$displaystyle$ \lfloor x\rfloor}이고 (2)의 표현식은 1과 같지만 (3)의 표현식은 1과 같지 않습니다. 따라서₁ p, ..., p보다_N 더 많은 소수가 있어야 합니다.

Legendre 공식을 사용한 증명

2010년 준호 피터 황은 다음과 같은 모순에 의한 증명을 발표했습니다.^[14] 임의의 양의 정수라고 합니다. 그렇다면 레전드레의 공식에 따르면 (때로는 드 폴리냐크에게 귀속되기도 함)

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

어디에

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

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

하지만 아주 많은 소수만 존재한다면,

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

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

시공별 증명

필리핀 사이닥은 작도법으로 다음과 같은 증거를 제시했는데, 이 증명은 귀납법이나^[15] 유클리드의 보조정리(소수 p가 a나 b를 나누면 a나 b를 나누어야 한다는 것)를 사용하지 않습니다.

각 자연수(> 1)는 적어도 하나의 소인수를 가지며, 연속되는 두 개의 수 n과 (n + 1)은 공통적으로 소인수가 없으므로, 곱 n(n + 1)은 수 n 자체보다 더 많은 소인수를 갖습니다. 따라서 소수의 연쇄는 다음과 같습니다.
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}, · · ·
는 무제한 성장하는 소수 세트를 제공합니다.

비압축성 방법을 사용한 증명

k개의 소수(p₁, ..., p_k)만 있다고 가정합니다. 산술의 기본 정리에 의해, 임의의 양의 정수 n은 다음과 같이 나타낼 수 있습니다.

음이 아닌 정수 지수 e와_i 유한한 크기의 소수 목록은 수를 재구성하기에 충분합니다. $모든$ i에 대해 $pi$≥ 2 {\$displaystyle p_{i$}\geq 2}이므로$,$ ${\displaystyle {모든}_{}}$ ${\displaystyle i}$에 ${\displaystyle \mathrm{대해}}$${\displaystyle e}$≤ $lg$⁡$$n${\displaystyle$ e_{i}\leq \lg n${\displaystyle {}_{}}$$여기$서 lg${\displaystyle$ \lg }는 밑-2 로그를 나타냅니다). 이를 통해 다음과 같은 크기의 n에 대한 인코딩을 얻을 수 있습니다(big O 표기법 사용).

$O$+ k${\displaystyle \lg }$ ${\displaystyle }$lg ⁡$n$) = O${\displaystyle (}$lg ⁡${\displaystyle }$lg ⁡ n) {\displaystyle O({\text{프라임리스트 크기}}+k\lg \lg${\displaystyle }$n) = O(\lg \lg n)} 비트.

$이것$은 N = ${\displaystyle O}$ ($lg$⁡ n) {\displaystyle N = O(\lg n)} 비트를 이진법으로 직접 표현하는 것보다 훨씬 효율적인 인코딩입니다. 무손실 데이터 압축의 확립된 결과는 일반적으로 N 비트의 정보를 N 비트 미만으로 압축할 수 없다는 것입니다. 위 표현은 ${\displaystyle \lg }$ ⁡ lg ⁡ $n$ = o ( lg ⁡ n) {\displaystyle \lg \lg n = o(\lg n)} 이므로 n이 충분히 큰 경우에는 이를 위반합니다. 따라서 소수의 수는 유한하지 않아야 합니다.^[16]

더 강력한 결과

이 절의 정리들은 동시에 유클리드의 정리와 다른 결과들을 암시합니다.

산술 진행에 관한 디리클레 정리

디리클레 정리는 임의의 두 개의 양의 코프라임 정수 a와 d에 대하여, n도 양의 정수인 a + n의 형태의 소수가 무한히 많다는 것을 말합니다. 즉, 모듈형에 합동인 소수들이 무한히 많다는 것입니다.

소수정리

임의의 실수 x에 대하여 x보다 작거나 같은 소수의 개수를 제공하는 소수 계산 함수를 π(x)라고 가정해 보자. 그런 다음 소수 정리는 x가 경계 없이 증가할 때 두 함수 π(x)와 x / log x의 몫의 극한은 1이므로 x / log x는 π(x)에 대한 좋은 근사치라고 말합니다.

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

점근 표기법을 사용하여 이 결과를 다음과 같이 다시 표기할 수 있습니다.

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

이것은 ${\displaystyle \frac{\lim }{}}$ ${\displaystyle \underset{}{x}}$ → ∞ x $log$∞ x = ⁡이기 때문에 유클리드 정리를 $산출합니다.$ {\$displaystyle$ \lim_{x\rightarrow \infty}{\frac {x}{\log x}}=\infty .}

베르트랑-체비셰프 정리

수론에서 베르트랑의 공준은 임의의 n> ${\display n>$ 1$}$에 대하여 적어도 하나의 소수가 항상 존재한다는 것을 나타내는 정리입니다.

${\displaystyle n<p<2n.}$

베르트랑-체비셰프 정리는$$π(x) ${\displaystyle \$pi$($x)}와의 관계로도 표현할 수 있습니다${\displaystyle .}$ ${\displaystyle \mathrm{여기}}$서$$π(x) ${\displaystyle$ \pi(x)}는 소수 계산 함수(x${\$displaystyle x\,} $이하$의$$소수)입니다.

${\displaystyle }$($x$$$ - ≥ (x${\displaystyle }$2) ≥ 1, {\displaystyle \$pi$ (x)-\pi({\tfrac {x}{2$}})\$geq 1,} 모${\displaystyle 든}$ x π 2. {\displaystyle x\geq 2.}

이 진술은 1845년 조셉 베르트랑(Joseph Bertrand^[17], 1822~1900)에 의해 처음 추측되었습니다. Bertrand 자신은 간격 [2, 3 × 10⁶]의 모든 숫자에 대해 자신의 진술을 확인했습니다. 그의 추측은 1852년^[18] 체비셰프(1821–1894)에 의해 완전히 증명되었고, 따라서 이 공준은 베르트랑-체비셰프 정리 또는 체비셰프 정리라고도 불립니다.

참고사항 및 참고사항

외부 링크

• Weisstein, Eric W. "Euclid's Theorem". MathWorld.
• 유클리드의 원소, 제9권, 제20권 (유클리드의 증명, 클라크 대학의 데이비드 조이스 웹사이트에 있음)