Eukleideen lause

Eukleideen lause on lukuteorian peruselementti . Siinä todetaan, että mille tahansa äärelliselle alkulukuluettelolle on alkuluku, joka ei sisälly tähän luetteloon (eli alkulukuja on äärettömän monta ).

Tälle lauseelle on useita tunnettuja todisteita .

Eukleideen todiste

Vanhimman tunnetun todisteen tästä tosiasiasta antoi Euclid in the Elements (Kirja IX, Proposition 20 [1] ). Samanaikaisesti Eukleides ei käytä äärettömyyden käsitettä, vaan todistaa tämän väitteen seuraavalla muotoilulla: alkulukuja on enemmän kuin mitä tahansa niistä valittua äärellistä joukkoa .

Euklids todistaa tämän seuraavasti [2] .

Oletetaan, että meille annetaan jokin äärellinen alkulukuluettelo . Euklid todistaa, että on olemassa alkuluku, joka ei sisälly tähän luetteloon. ${\näyttötyyli a,b,\pisteet z}$

Antaa olla pienin yhteinen monikerta näistä numeroista, . $P$ $P=a*b*...*z$

Euklids ottaa huomioon numeron . Jos on alkuluku, niin löydetään alkuluku, joka ei sisälly annettuun listaan (koska se on suurempi kuin jokainen listan luku). $Q=P+1$ $K$ ${\näyttötyyli {a,b,...z))$

Jos se ei ole alkuluku, on olemassa jokin alkuluku , jolla luku on tasan jaollinen . Mutta se ei voi olla sekä jakaja että listan elementti , koska silloin jakamalla luvulla jäännös olisi yhtä suuri kuin yksi. Tämä tarkoittaa, että on olemassa alkuluku , joka ei sisälly mihinkään (äärelliseen) alkulukuluetteloon . $K$ $x$ $K$ $x$ $K$ ${\näyttötyyli {a,b,...z))$ $K$ $x$ $x$ ${\näyttötyyli {a,b,...z))$

Usein Eukleideen lauseen todistetta esitettäessä aloitetaan tarkastelemalla KAIKKI alkulukujen joukko kerralla (olettaen, että tämä joukko sisältää äärellisen määrän alkioita), ja sitten lauseen todistus suoritetaan ristiriitaisesti. Vaikka tällainen todiste on myös mahdollinen, Eukleideen alkuperäinen päättely on tyylikkäämpi - nimittäin mille tahansa äärelliselle alkulukujoukolle, ja se todistaa, että täytyy olla jokin alkuluku, joka ei sisälly tähän (mitään) alkulukujen joukkoon [3] .

Lyhyt muoto Eukleideen todisteesta:

Olkoon meille annettu äärellinen joukko alkulukuja. Osoitetaan, että on olemassa alkuluku, joka ei sisälly tähän joukkoon. Kerro tämän joukon luvut ja lisää yksi. Saatu luku ei ole jaollinen millään annetusta joukosta, koska jakojäännös millä tahansa niistä antaa yhden. Tämä tarkoittaa, että luvun on oltava jaollinen jollakin alkuluvulla, joka ei sisälly tähän joukkoon.

Muunnelma Eukleideen todistuksesta kertoimella

Muut Eukleideen todistuksen muunnelmat käyttävät faktoriaalia : n ! on jaollinen millä tahansa kokonaisluvulla välillä 2 - n , koska se on heidän tulonsa. Siksi n ! + 1 ei ole jaollinen millään luonnollisella luvulla 2:sta n :ään (kun jaetaan millä tahansa näistä luvuista, jäännös on 1). Joten n ! + 1 on joko itse alkuluku tai jaollinen alkuluvulla, joka on suurempi kuin n . Joka tapauksessa meillä on mille tahansa luonnolliselle luvulle n vähintään yksi alkuluku, joka on suurempi kuin n . Tästä päätämme, että alkulukuja on äärettömän monta [4] .

Euklidiset luvut

Jotkut tämän lauseen asiaan liittyvät todistukset käyttävät ns. euklidisia lukuja (sekvenssi A006862 OEIS : ssä ): , jossa on ensimmäisten alkulukujen tulo ( primorial ). Samalla muodollisesti Eukleideen antama todistus ei käytä näitä lukuja. Kuten edellä mainittiin, Euclid osoittaa, että mille tahansa äärelliselle alkulukujoukolle (ei välttämättä ensimmäisille alkuluvuille) on alkuluku, joka ei sisälly tähän joukkoon [5] . $E_{n}=p_{n}\#+1$ $p_{n}\#$ $n$ $n$

Eulerin todiste

Toinen Leonhard Eulerin tarjoama todiste perustuu aritmeettisen peruslauseeseen , jonka mukaan millä tahansa kokonaisluvulla on ainutlaatuinen alkulukujako. Jos merkitsemme P :llä kaikkien alkulukujen joukkoa, voimme kirjoittaa yhtäläisyydet:

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

Ensimmäinen yhtälö saadaan geometrisen sarjan kaavasta jokaisessa tuotteen kertoimessa. Toinen yhtälö saadaan vaihtamalla tulo ja summa keskenään:

{\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}}

Tämän seurauksena mikä tahansa alkulukujen tulo esiintyy kaavassa vain kerran, ja sitten aritmeettisen peruslauseen mukaan summa on yhtä suuri kuin kaikkien luonnollisten lukujen summa [a] .

Oikeanpuoleinen summa on harmoninen sarja , joka hajoaa, joten myös vasemman tulon täytyy hajota, mikä ei ole mahdollista, jos P :n alkioiden lukumäärä on äärellinen.

Tämän todistuksen avulla Euler sai vahvemman väitteen kuin Eukleideen lause, nimittäin alkulukujen käänteissumman hajaantumisen .

Erdősin todiste

Pal Erdős antoi kolmannen todisteen, joka myös nojaa aritmeettisen peruslauseeseen. Ensin kiinnitetään huomiota siihen, että mikä tahansa luonnollinen luku n voidaan esittää muodossa

rs^{2}

missä r on neliötön (ei jaollinen millään täydellisellä neliöllä ). Voimme ottaa s 2 :ksi suurimman n:n jakavan neliön , jolloin r = n / s2 . Oletetaan nyt, että alkulukuja on vain äärellinen määrä, ja merkitse tämä alkulukujen määrä k :lla . Koska jokainen alkuluku voi esiintyä vain kerran minkä tahansa neliöttömän luvun hajotuksessa, aritmeettisen peruslauseen mukaan neliövapaita lukuja on vain 2k .

Nyt korjataan luonnollinen luku N ja tarkastellaan luonnollisia lukuja välillä 1 ja N. Jokainen näistä luvuista voidaan kirjoittaa muodossa rs 2 , missä r on neliötön luku ja s 2 on neliö:

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

Listassa on N erilaista lukua , ja jokainen niistä saadaan kertomalla neliötön luku neliöllä, joka ei ylitä N . Tällaisia neliöitä on. Nyt muodostetaan kaikki mahdolliset tulot kaikista neliöistä, jotka eivät ylitä N :ää kaikilla neliöttömällä luvulla. Tällaisia numeroita on, ne ovat kaikki erilaisia ja sisältävät kaikki luettelossamme olevat numerot ja ehkä enemmänkin. Siten ,. Tämä tarkoittaa koko osaa . $\lfloor {\sqrt {N}}\rfloor$ $2^{k}\lfloor {\sqrt {N}}\rfloor$ $2^{k}\lfloor {\sqrt {N}}\rfloor \geqslant N$ $\lfloor {x}\rfloor$

Koska epäyhtälö epäonnistuu riittävän suurelle N :lle, alkulukuja täytyy olla äärettömän monta.

Furstenbergin todiste

Vuonna 1955 Hillel Furstenberg julkaisi uuden todisteen alkulukujen määrän äärettömyydestä käyttämällä pistejoukkojen topologiaa .

Joitakin viimeaikaisia todisteita

Saidak

Vuonna 2006 Phillip Sajdak antoi seuraavan rakentavan todisteen , jossa ei käytetä pelkistystä absurdiksi [6] eikä Euklidesin lemmaa (että jos alkuluku p jakaa ab , sen täytyy jakaa joko a tai b ).

Koska jokaisella luonnollisella luvulla (> 1) on vähintään yksi alkutekijä ja kahdella peräkkäisellä luvulla n ja ( n + 1) ei ole yhteistä jakajaa, tulolla n ( n + 1) on enemmän erilaisia alkujakajia kuin luvulla n . itse . Näin ollen suorakaiteen muotoisten lukujen ketju :
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}, · · ·
antaa joukon äärettömästi laajenevia alkulukujoukkoja.

Pinasco

Vuonna 2009 Juan Pablo Piasco ehdotti seuraavaa todistetta [7] .

Antaa olla pienin N alkulukua. Sitten sisällyttäminen-poissulkemisperiaatteen mukaan positiivisten kokonaislukujen määrä, joka ei ylitä x :ää ja jaollinen näillä alkuluvuilla on ${\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}}}\right\rfloor &+\sum _{i<j<k}\left\lfloor {\frac {x}{p_{i}p_ {j}p_{k}}}\oikea\rfloor -\cdots \\&\cdots \pm (-1)^{N+1}\left\lfloor {\frac {x}{p_{1}\cdots p_{N}}}\oikea\rlattia .\qquad (1)\end{aligned}}

Jakamalla x :llä ja antamalla , saamme $x\to \infty$

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

Tämä voidaan kirjoittaa uudelleen muotoon

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

Jos muita alkulukuja ei ole kuin , lauseke (1) on yhtä suuri ja lauseke (2) on yhtä suuri kuin 1, mutta on selvää, että lauseke (3) ei ole yhtä suuri kuin yksi. Siten on oltava muita alkulukuja kuin . $p_{1},\dots ,p_{N}$ $\lfloor x\rfloor$ $p_{1},\dots ,p_{N}$

Wang

Vuonna 2010 Jun Ho Peter Wang julkaisi seuraavan ristiriitaisen todisteen [8] . Olkoon k jokin luonnollinen luku. Sitten Legendren kaavan mukaan

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

(tuote yli kaikkien alkulukujen)

missä

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

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

Mutta jos alkulukuja on vain äärellinen määrä,

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

(murtoluvun osoittaja kasvaa eksponentiaalisesti , kun taas Stirlingin kaavan mukaan nimittäjä kasvaa nopeammin kuin yksinkertainen eksponentiaalisuus), mikä on ristiriidassa sen tosiasian kanssa, että jokaisen k :n osoittaja on suurempi tai yhtä suuri kuin nimittäjä.

Todiste käyttämällä irrationaalisuutta $\pi$

Esittämällä Leibnizin kaavan $\pi$ Eulerin tulona [ saadaan [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

Osoittajat ovat parittomia alkulukuja, ja jokainen nimittäjä on osoittajaa lähin luvun 4 kerrannainen.

Jos alkulukuja olisi äärellinen määrä, tämä kaava antaisi rationaalisen esityksen, jonka nimittäjä on kaikkien lukujen tulo, mikä on irrationaalisuuden vastaista . $\pi$ $\pi$

Todistus informaatioteorian avulla

Alexander Shen ym. antoivat todisteen kokoonpuristumattomuusmenetelmällä [10] ja Kolmogorov-kompleksisuudella :

Oletetaan, että alkulukuja ( ) on vain k . Aritmeettisen peruslauseen mukaan mikä tahansa luonnollinen luku n voidaan esittää muodossa $p_{1},\pisteet ,p_{k}$

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

missä ei-negatiiviset kokonaisluvut e i yhdessä äärellisen kokoisen alkulukuluettelon kanssa riittävät luvun rekonstruoimiseen. Koska kaikille i , tästä seuraa, että kaikki (missä tarkoittaa logaritmia kantaan 2). $p_{i}\geqslant 2$ $e_{i}\leqslant \log n$ $\Hirsi$

Tämä antaa koodausmenetelmän seuraavan kokoiselle n :lle (käyttäen "suuri O" -merkintää ):

O({\teksti{alkuluettelon koko}}+k\log \log n)=O(\log \log n)

bitti.

Tämä on paljon tehokkaampi koodaus kuin n: n esittäminen suoraan binäärimuodossa, mikä vaatii bittejä. Todettu häviöttömän kompressoinnin tulos toteaa, että ei ole algoritmia N bitin informaation häviöttömäksi pakkaamiseksi alle N bitiksi. Yllä oleva esitys rikkoo tätä väitettä, koska riittävän suurelle n :lle . $N=O(\log n)$ $\log \log n=o(\log n)$

Alkulukuja on siis äärettömän monta.

Alkulukujen asymptoottinen jakauma

Alkulukujakaumalauseessa sanotaan, että alle n :llä merkittyjen alkulukujen määrä kasvaa [11] . $\pi(n)$ $n/\ln(n)$

Katso myös

Kommentit

↑ Tämä yhtälö on Euler-tulon kaavan erikoistapaus Riemannin zeta-funktiolle .

Muistiinpanot

↑ The Beginnings of Euclid, 1949-1951 , Book IX, Proposition 20, s. 89.
↑ James Williamson (kääntäjä ja kommentaattori), The Euclid, With Dissertations , Clarendon Press , Oxford, 1782, sivu 63, Euklidesin todisteen englanninkielinen käännös Arkistoitu 23. tammikuuta 2011 Wayback Machinessa
↑ Hardy, Michael; Woodgold, Catherine. Prime Simplicity (englanniksi) // The Mathematical Intelligencer . - 2009. - Vol. 31 , ei. 4 . - s. 44-52 . - doi : 10.1007/s00283-009-9064-8 . (Englanti)
↑ Bostock, Chandler, Rourke, 2014 , s. 168.
↑ Romeo Mestrovic. Eukleideen lause alkulukujen äärettömyydestä: historiallinen katsaus sen todisteisiin (300 eKr.--2012) ja toinen uusi todistus // arXiv:1202.3670 [math]. – 16.2.2012. Arkistoitu alkuperäisestä 12. kesäkuuta 2018.
↑ Saidak, 2006 .
↑ Pinasco, 2009 , s. 172-173.
↑ Whang, 2010 , s. 181.
↑ Debnath, 2010 , s. 214.
↑ Vereshchagin, Uspensky, Shen, 2013 , s. 267.
↑ Diamond G. Alkulukujakauman tutkimuksen alkeismenetelmät // Uspekhi Mat . - 1990. Arkistoitu 7. heinäkuuta 2018.

Kirjallisuus

Beginnings of Euclid / Käännös kreikasta ja D. D. Mordukhai-Boltovskin kommentit , toimituksellisesti M. Ya. Vygodsky ja I. N. Veselovski. - M. - L .: GTTI, 1949-1951. - (Luonnontieteen klassikot).
Michael Hardy, Catherine Woodgold. Prime Simplicity (englanniksi) // The Mathematical Intelligencer . - 2009. - Vol. 31 , ei. 4 . - s. 44-52. .
Eukleideen elementit, väitöskirjoilla // Clarendon Press / James Williamson (käännös ja kommentit). - Oxford, 1782. - S. 63 .
Junho Peter Whang. Toinen todiste alkulukujen äärettömyydestä // American Mathematical Monthly . - 2010. - Helmikuu ( nide 117 , nro 2 ). - S. 181 .
Philip Saidak. Uusi todiste Eukleideen lauseesta // American Mathematical Monthly . - 2006. - Joulukuu ( nide 113 , numero 10 ). - doi : 10.2307/27642094 .
Lokenath Debnath. Leonhard Eulerin perintö: Tricentennial Tribute . - World Scientific, 2010. - S. 214 . — ISBN 9781848165267 .
Nikolai Konstantinovitš Vereshchagin , Vladimir Andreevich Uspensky , Alexander Shen . Kolmogorov - monimutkaisuus ja algoritminen satunnaisuus . — Moskovan matematiikan jatkuvan koulutuksen keskuksen kustantamo, 2013.
Juan Pablo Pinasco. Uusia todisteita Euclidin ja Eulerin lauseista // American Mathematical Monthly . - 2009. - Helmikuu ( nide 116 , nro 2 ).

Linkit

Weisstein, Eric W. Euclid's Theorem (englanniksi) Wolfram MathWorld -verkkosivustolla .
Euclid's Elements, kirja IX, Prop. 20 (Eukleideen todiste, David Joycen verkkosivuilla Clarkin yliopistossa)
125 todistetta Eukleideen lauseesta