Euklids teorem

Euklids teorem är en grundläggande del av talteorin . Den anger att för alla ändliga primtal finns det ett primtal som inte ingår i denna lista (det vill säga det finns oändligt många primtal ).

Det finns flera kända bevis för denna sats .

Euklids bevis

Det äldsta kända beviset för detta faktum gavs av Euclid in the Elements (bok IX, proposition 20 [1] ). Samtidigt använder Euklids inte begreppet oändlighet, utan bevisar detta påstående i följande formulering: det finns fler primtal än någon vald finit uppsättning av dem .

Euklid bevisar detta enligt följande [2] .

Anta att vi får en ändlig lista med primtal . Euklid bevisar att det finns ett primtal som inte finns med i denna lista. $a,b,\dots z$

Låta vara den minsta gemensamma multipeln av dessa tal, . $P$ $P=a*b*...*z$

Euklids överväger antal . Om är ett primtal, så hittas ett primtal som inte ingår i den givna listan (eftersom det är större än varje tal från listan). $Q=P+1$ $F$ ${\displaystyle {a,b,....z))$

Om det inte är primtal, så finns det något primtal med vilket talet är jämnt delbart . Men det kan inte vara både en divisor och ett element i listan , för då när man dividerar med , skulle det finnas en rest lika med ett. Det betyder att det finns ett primtal som inte ingår i någon (ändlig) lista med primtal . $F$ $x$ $F$ $x$ $F$ ${\displaystyle {a,b,....z))$ $F$ $x$ $x$ ${\displaystyle {a,b,....z))$

Ofta, när man presenterar beviset för Euklids sats, börjar man med att betrakta mängden ALLA primtal på en gång (förutsatt att denna mängd innehåller ett ändligt antal element), och sedan genomförs beviset för satsen genom motsägelse. Även om ett sådant bevis också är möjligt, är Euklids ursprungliga resonemang mer elegant - nämligen för vilken ändlig uppsättning primtal som helst, och bevisar att det måste finnas något primtal som inte ingår i denna (någon) uppsättning primtal [3] .

Kort form av Euklids bevis:

Låt oss ges en ändlig uppsättning primtal. Låt oss visa att det finns ett primtal som inte ingår i denna uppsättning. Multiplicera siffrorna från denna uppsättning och lägg till ett. Det resulterande talet är inte delbart med något tal från den givna mängden, eftersom resten av divisionen med någon av dem ger ett. Det betyder att talet måste vara delbart med något primtal som inte ingår i denna uppsättning.

En variant av Euklids bevis med hjälp av faktorial

Andra varianter av Euklids bevis använder faktorn : n ! är delbart med vilket heltal som helst från 2 till n eftersom det är deras produkt. Därför n ! + 1 är inte delbart med något naturligt tal från 2 till och med n (när man dividerar med något av dessa tal är resten 1). Så n ! + 1 är antingen primtal själv eller delbart med ett primtal större än n . I alla fall har vi för alla naturliga tal n minst ett primtal som är större än n . Därför drar vi slutsatsen att det finns oändligt många primtal [4] .

Euklidiska tal

Några relaterade bevis för denna sats använder de så kallade euklidiska talen (sekvens A006862 i OEIS ): , där är produkten av de första primtalen ( primorial ). Samtidigt, formellt sett, använder Euklids bevis inte dessa siffror. Som nämnts ovan visar Euklid att för varje ändlig uppsättning primtal (inte nödvändigtvis de första primtalen) finns det ett primtal som inte ingår i denna uppsättning [5] . $E_{n}=p_{n}\#+1$ $p_{n}\#$ $n$ $n$

Eulers bevis

Ett annat bevis, som erbjuds av Leonhard Euler , förlitar sig på aritmetikens grundläggande teorem , som säger att vilket heltal som helst har en unik primtalsfaktorisering. Om vi betecknar med P mängden av alla primtal kan vi skriva likheterna:

\prod _{p\in P}{\frac {1}{1-1/p}}=\prod _{p\in P}\sum _{k\geqslant 0}{\frac {1 }{p^{k))}=\summa _{n}{\frac {1}{n)).

Den första likheten erhålls från formeln för den geometriska serien i varje multiplikator av produkten. Den andra likheten erhålls genom att utbyta produkten och summan:

{\begin{aligned}\prod _{p\in P}\sum _{k\geqslant 0}{\frac {1}{p^{k))}&=\sum _{k\geqslant 0}{\frac {1}{2^{k))}\cdot \sum _{k\geqslant 0}{\frac {1}{3^{k))}\cdot \sum _{k\geqslant 0}{\frac {1}{5^{k}}}\cdot \sum _{k\geqslant 0}{\frac {1}{7^{k}}}\cdots \\[8pt]&= \sum _{k,\ell ,m,n,\cdots \geqslant 0}{\frac {1}{2^{k}3^{\ell }5^{m}7^{n}\cdots } }=\summa _{n}{\frac {1}{n}}\end{aligned}}

Som ett resultat förekommer vilken produkt av primtal som helst i formeln endast en gång, och sedan, enligt aritmetikens grundsats, är summan lika med summan över alla naturliga tal [a] .

Summan till höger är en övertonsserie som divergerar, så produkten till vänster måste också divergera, vilket inte är möjligt om antalet element i P är ändligt.

Med hjälp av detta bevis fick Euler ett starkare uttalande än Euklids teorem, nämligen divergensen av summan av reciproka primtal .

Erdős bevis

Pal Erdős gav ett tredje bevis, som också bygger på aritmetikens grundläggande sats. Låt oss först uppmärksamma det faktum att vilket naturligt tal n som helst kan representeras som

rs^{2}

där r är kvadratfritt (inte delbart med någon perfekt kvadrat ). Vi kan ta som s 2 den största kvadraten som delar n , och sedan r = n / s 2 . Antag nu att det bara finns ett ändligt antal primtal, och beteckna det antalet primtal med k . Eftersom varje primtal bara kan förekomma en gång i sönderdelningen av ett kvadratfritt tal, enligt aritmetikens grundsats, finns det bara 2k kvadratfria tal.

Nu fixar vi ett naturligt tal N och betraktar naturliga tal mellan 1 och N . Vart och ett av dessa tal kan skrivas som rs 2 , där r är ett kvadratfritt tal och s 2 är en kvadrat:

( 1 1, 2 1, 3 1, 1 4, 5 1, 6 1, 7 1, 2 4, 1 9, 10 1, ...)

Det finns N olika tal i listan , och vart och ett av dem erhålls genom att multiplicera ett kvadratfritt tal med en kvadrat som inte överstiger N . Det finns sådana rutor. Nu bildar vi alla möjliga produkter av alla kvadrater som inte överstiger N med alla kvadratfria tal. Det finns exakt sådana siffror, de är alla olika och inkluderar alla siffror på vår lista, och kanske fler. Alltså ,. Här betyder hela delen . $\lfloor {\sqrt {N}}\rfloor$ $2^{k}\lfloor {\sqrt {N}}\rfloor$ $2^{k}\lfloor {\sqrt {N}}\rfloor \geqslant N$ $\lfloor {x}\rfloor$

Eftersom ojämlikheten misslyckas för tillräckligt stort N måste det finnas oändligt många primtal.

Furstenbergs bevis

År 1955 publicerade Hillel Furstenberg ett nytt bevis på oändligheten av antalet primtal med hjälp av topologin för punktmängder .

Några nya bevis

Saidak

2006 gav Phillip Sajdak följande konstruktiva bevis , som inte använder reduktion till absurditet [6] eller Euklids lemma (att om ett primtal p delar ab måste det dividera antingen a eller b ).

Eftersom varje naturligt tal (> 1) har minst en primtalsfaktor, och två på varandra följande tal n och ( n + 1) inte har en gemensam divisor, har produkten n ( n + 1) fler olika primtalare än talet n sig själv . Alltså, kedjan av rektangulära tal :
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}, · · ·
ger en sekvens av oändligt expanderande uppsättningar av primtal.

Pinasco

2009 föreslog Juan Pablo Piasco följande bevis [7] .

Låt vara de minsta N primtalen. Sedan enligt inkluderings-exkluderingsprincipen är antalet positiva heltal som inte överstiger x och är delbart med dessa primtal ${\displaystyle p_{1},\dots ;p_{N))$

{\begin{aligned}1+\sum _{i}\left\lfloor {\frac {x}{p_{i))}\right\rfloor -\sum _{i<j}\left\ lfloor {\frac {x}{p_{i}p_{j}}}\höger\rfloor &+\sum _{i<j<k}\left\lfloor {\frac {x}{p_{i}p_ {j}p_{k}}}\höger\rgolv -\cdots \\&\cdots \pm (-1)^{N+1}\vänster\lgolv {\frac {x}{p_{1}\cdots p_{N}}}\right\rfloor .\qquad (1)\end{aligned}}

Dividera med x och låta får vi $x\till \infty$

\sum _{i}{\frac {1}{p_{i}}}-\summa _{i<j}{\frac {1}{p_{i}p_{j}}}+\ summa _{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)

Detta kan skrivas om som

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

Om det inte finns några andra primtal än , är uttrycket i (1) lika och uttrycket (2) är lika med 1, men det är tydligt att uttrycket (3) inte är lika med ett. Det måste alltså finnas andra primtal än . $p_{1},\dots ,p_{N}$ $\lfloor x\rfloor$ $p_{1},\dots ,p_{N}$

Wang

År 2010 publicerade Jun Ho Peter Wang följande motstridiga bevis [8] . Låt k vara ett naturligt tal. Sedan, enligt Legendre-formeln

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

(produkt över alla primtal)

var

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} }\leqslant k.

Men om det bara finns ett ändligt antal primtal,

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

(täljaren för ett bråk växer exponentiellt medan nämnaren enligt Stirlings formel växer snabbare än enkel exponentialitet), vilket motsäger det faktum att för varje k är täljaren större än eller lika med nämnaren.

Bevis med irrationalitet $\pi$

Att representera Leibniz formel för $\pi$ som en produkt av Euler ger [9] .

{\frac {\pi }{4}}={\frac {3}{4}}\cdot {\frac {5}{4}}\cdot {\frac {7}{8}}\ cdot {\frac {11}{12}}\cdot {\frac {13}{12}}\cdot {\frac {17}{16}}\cdot {\frac {19}{20}}\cdot { \frac {23}{24}}\cdot {\frac {29}{28}}\cdot {\frac {31}{32}}\cdot \cdots

Täljare är udda primtal, och varje nämnare är den närmaste multipeln av 4 till täljaren.

Om det fanns ett ändligt antal primtal skulle denna formel ge en rationell representation där nämnaren är produkten av alla tal, vilket strider mot irrationalitet . $\pi$ $\pi$

Bevis med informationsteori

Alexander Shen et al gav ett bevis med hjälp av inkompressibilitetsmetoden [10] och Kolmogorovs komplexitet :

Anta att det bara finns k primtal ( ). Enligt aritmetikens grundläggande sats kan vilket naturligt tal n som helst representeras som $p_{1},\dots ,p_{k}$

n={p_{1}}^{e_{1}}{p_{2}}^{e_{2}}\cdots {p_{k}}^{e_{k}},

där icke-negativa heltal e i tillsammans med en ändlig storlekslista med primtal är tillräckliga för att rekonstruera talet. Eftersom för all i , följer det att alla (där betyder logaritm till bas 2). $p_{i}\geqslant 2$ $e_{i}\leqslant \log n$ $\logga$

Detta ger en kodningsmetod för n av följande storlek (med "stor O"-notation ):

O({\text{prime list size}}+k\log \log n)=O(\log \log n)

bit.

Detta är en mycket effektivare kodning än att representera n direkt i binär, vilket kräver bitar. Det etablerade förlustfria komprimeringsresultatet anger att det inte finns någon algoritm för att förlustfritt komprimera N bitar av information till mindre än N bitar. Ovanstående representation bryter mot detta uttalande, eftersom för tillräckligt stor n . $N=O(\log n)$ $\log \log n=o(\log n)$

Det finns alltså oändligt många primtal.

Asymptotisk fördelning av primtal

Primtalsfördelningssatsen säger att antalet primtal mindre än n , betecknat med , växer som [11] . $\stift)$ $n/\ln(n)$

Se även

Kommentarer

↑ Denna likhet är ett specialfall av formeln för Euler-produkten för Riemann zeta-funktionen .

Anteckningar

↑ The Beginnings of Euclid, 1949-1951 , Bok IX, Proposition 20, sid. 89.
↑ James Williamson (översättare och kommentator), The Elements of Euclid, With Dissertations , Clarendon Press , Oxford, 1782, sidan 63, engelsk översättning av Euclids bevis Arkiverad 23 januari 2011 på Wayback Machine
↑ Hardy, Michael; Woodgold, Catherine. Prime Simplicity (engelska) // The Mathematical Intelligencer . - 2009. - Vol. 31 , nr. 4 . - S. 44-52 . - doi : 10.1007/s00283-009-9064-8 . (Engelsk)
↑ Bostock, Chandler, Rourke, 2014 , sid. 168.
↑ Romeo Mestrovic. Euklids teorem om primtals oändlighet: en historisk översikt över dess bevis (300 f.Kr.--2012) och ytterligare ett nytt bevis // arXiv:1202.3670 [matte]. — 2012-02-16. Arkiverad från originalet den 12 juni 2018.
↑ Saidak, 2006 .
↑ Pinasco, 2009 , sid. 172–173.
↑ Whang, 2010 , sid. 181.
↑ Debnath, 2010 , sid. 214.
↑ Vereshchagin, Uspensky, Shen, 2013 , sid. 267.
↑ Diamant G. Elementära metoder i studien av fördelningen av primtal // Uspekhi Mat . - 1990. Arkiverad den 7 juli 2018.

Litteratur

Beginnings of Euclid / Översättning från grekiska och kommentarer av D. D. Mordukhai-Boltovsky med redaktionellt deltagande av M. Ya. Vygodsky och I. N. Veselovsky. - M. - L .: GTTI, 1949-1951. - (Klassiker inom naturvetenskap).
Michael Hardy, Catherine Woodgold. Prime Simplicity (engelska) // The Mathematical Intelligencer . - 2009. - Vol. 31 , nr. 4 . - S. 44-52. .
The Elements of Euclid, With Dissertations // Clarendon Press / James Williamson (översättning och kommentarer). - Oxford, 1782. - S. 63 .
Junho Peter Whang. Ännu ett bevis på primtalens oändlighet // American Mathematical Monthly . - 2010. - Februari ( vol. 117 , nr 2 ). - S. 181 .
Philip Saidak. Ett nytt bevis på Euklids sats // American Mathematical Monthly . - 2006. - December ( vol. 113 , nummer 10 ). - doi : 10.2307/27642094 .
Lokenath Debnath. The Legacy of Leonhard Euler: A Tricentennial Tribute . - World Scientific, 2010. - S. 214 . — ISBN 9781848165267 .
Nikolai Konstantinovich Vereshchagin , Vladimir Andreevich Uspensky , Alexander Shen . Kolmogorovs komplexitet och algoritmisk slumpmässighet . — Publishing House of the Moscow Center for Continuous Mathematical Education, 2013.
Juan Pablo Pinasco. Nya bevis för Euklids och Eulers satser // American Mathematical Monthly . - 2009. - Februari ( vol. 116 , nr 2 ).

Länkar

Weisstein, Eric W. Euclid's Theorem (engelska) på Wolfram MathWorld- webbplatsen .
Euklids element, bok IX, Prop. 20 (Euclids bevis, på David Joyces hemsida vid Clark University)
125 bevis för Euklids sats