Euklidész tétele

Euklidész tétele a számelmélet alapvető eleme . Azt állítja, hogy a prímek bármely véges listájához van egy prím, amely nem szerepel ebben a listában (azaz végtelen sok prímszám van ).

Ennek a tételnek számos bizonyítása ismert .

Euklidész bizonyítása

Ennek a ténynek a legrégebbi ismert bizonyítékát Eukleidész adta az Elemekben (IX. könyv, 20. állítás [1] ). Ugyanakkor Eukleidész nem használja a végtelen fogalmát, hanem a következő megfogalmazással bizonyítja ezt az állítást: több prímszám van, mint bármelyik kiválasztott véges halmaz .

Eukleidész ezt a következőképpen bizonyítja [2] .

Tegyük fel, hogy kapunk egy véges prímlistát . Eukleidész bebizonyítja, hogy van olyan prímszám, amely nem szerepel ebben a listában. $a,b,\dots z$

Legyen ezeknek a számoknak a legkisebb közös többszöröse , . $P$ $P=a*b*...*z$

Euklidész a számot veszi figyelembe . Ha prím, akkor olyan prímszámot találunk, amely nem szerepel az adott listában (mert nagyobb, mint a listán szereplő összes szám). $Q=P+1$ $K$ ${\megjelenítési stílus {a,b,...z))$

Ha nem prím, akkor van olyan prímszám , amellyel a szám egyenletesen osztható . De nem lehet egyszerre osztója és eleme a listának , mert akkor a -val osztva maradna eggyel. Ez azt jelenti, hogy létezik olyan prímszám , amely nem szerepel egyetlen (véges) prímszámlistában sem . $K$ $x$ $K$ $x$ $K$ ${\megjelenítési stílus {a,b,...z))$ $K$ $x$ $x$ ${\megjelenítési stílus {a,b,...z))$

Az euklidészi tétel bizonyítása során gyakran kezdjük az ÖSSZES prímszám halmazának egyidejű figyelembevételével (feltételezve, hogy ez a halmaz véges sok elemet tartalmaz), majd a tétel bizonyítása ellentmondással történik. Bár egy ilyen bizonyítás is lehetséges, Euklidész eredeti érvelése elegánsabb – mégpedig bármely véges prímhalmazra, és azt bizonyítja, hogy kell lennie olyan prímszámnak, amely nem szerepel ebben a (egyik) prímhalmazban [3] .

Euklidész bizonyításának rövid formája:

Adjuk meg a prímszámok véges halmazát. Mutassuk meg, hogy létezik olyan prímszám, amely nem szerepel ebben a halmazban. Szorozd meg a számokat ebből a halmazból, és adj hozzá egyet. A kapott szám nem osztható az adott halmazból egyetlen számmal sem, mert bármelyikkel való osztás maradéka egyet ad. Ez azt jelenti, hogy a számnak oszthatónak kell lennie olyan prímszámmal, amely nem szerepel ebben a halmazban.

Eukleidész bizonyításának variációja a faktoriális

Eukleidész bizonyításának más változatai a faktoriálist használják : n ! osztható bármely 2-től n -ig terjedő egész számmal , mivel ez a szorzatuk. Ezért n ! A + 1 nem osztható 2-től n - ig terjedő természetes számmal (ha e számok bármelyikével osztjuk, a maradék 1). Szóval n ! + 1 vagy maga a prím, vagy osztható egy n -nél nagyobb prímmel . Mindenesetre minden n természetes számra van legalább egy n - nél nagyobb prímszám . Ebből arra következtetünk, hogy végtelen sok prímszám van [4] .

Euklideszi számok

Ennek a tételnek néhány kapcsolódó bizonyítása az úgynevezett euklideszi számokat használja ( A006862 sorozat az OEIS -ben ): , ahol az első prímszámok szorzata ( primorial ). Ugyanakkor formálisan az Eukleidész által adott bizonyítás nem használja ezeket a számokat. Ahogy fentebb említettük, Eukleidész megmutatja, hogy bármely véges prímhalmazhoz (nem feltétlenül az első prímekhez) van olyan prímszám, amely nem szerepel ebben a halmazban [5] . $E_{n}=p_{n}\#+1$ $p_{n}\#$ $n$ $n$

Euler bizonyítása

Egy másik bizonyíték, amelyet Leonhard Euler kínált, az aritmetika alaptételére támaszkodik , kijelentve, hogy minden egész számnak egyedi prímtényezőssége van. Ha P - vel jelöljük az összes prímszám halmazát, felírhatjuk az egyenlőségeket:

\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)).

Az első egyenlőséget a szorzat minden egyes szorzójában a geometriai sorozat képletéből kapjuk. A második egyenlőséget a szorzat és az összeg felcserélésével kapjuk:

{\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 } }=\sum _{n}{\frac {1}{n}}\end{igazított}}

Ennek eredményeként a prímszámok bármely szorzata csak egyszer szerepel a képletben, majd az aritmetika alaptétele szerint az összeg megegyezik az összes természetes szám összegével [a] .

A jobb oldali összeg egy harmonikus sorozat , amely divergál, tehát a bal oldali szorzatnak is divergálnia kell, ami nem lehetséges, ha P -ben véges az elemek száma.

E bizonyítás segítségével Euler erősebb állítást kapott, mint Euklidész tétele, nevezetesen a prímszámok reciprok összegének divergenciáját .

Erdős bizonyítása

Erdős Pál adott egy harmadik bizonyítást, amely szintén az aritmetika alaptételére támaszkodik. Először is figyeljünk arra, hogy bármely n természetes szám ábrázolható így

{\displaystyle rs^{2))

ahol r négyzetmentes ( nem osztható tökéletes négyzettel ). Felvehetjük s 2 -nek az n -t osztó legnagyobb négyzetet , és ekkor r = n / s 2 . Tegyük fel, hogy csak véges számú prím van, és jelölje ezt a prímszámot k -val . Mivel minden négyzet nélküli szám felbontásában minden prímszám csak egyszer szerepelhet, az aritmetika alaptétele szerint csak 2k négyzetmentes szám van.

Most rögzítünk néhány N természetes számot , és figyelembe vesszük az 1 és N közötti természetes számokat . Ezen számok mindegyike felírható rs 2 -ként , ahol r négyzet nélküli szám, s 2 pedig négyzet:

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

A listában N különböző szám található , és mindegyiket úgy kapjuk meg, hogy egy négyzet nélküli számot megszorozunk egy N értéket meg nem haladó négyzettel . Vannak ilyen négyzetek. Most minden N - t nem meghaladó négyzet minden lehetséges szorzatát képezzük minden négyzetmentes számmal. Pontosan ilyen számok vannak, mindegyik más, és tartalmazza a listánkon szereplő összes számot, és talán még többet is. Így, . Itt az egész részt jelenti . $\lfloor {\sqrt {N}}\rfloor$ $2^{k}\lfloor {\sqrt {N}}\rfloor$ $2^{k}\lfloor {\sqrt {N}}\rfloor \geqslant N$ $\lfloor {x}\rfloor$

Mivel az egyenlőtlenség elég nagy N esetén meghiúsul, végtelen sok prímnek kell lennie.

Furstenberg bizonyítása

1955-ben Hillel Furstenberg kiadta a prímszámok végtelenségének új bizonyítását a ponthalmazok topológiájával .

Néhány újabb bizonyíték

Saidak

2006-ban Phillip Sajdak a következő konstruktív bizonyítást adta , amely nem használja az abszurditásig való redukciót [6] vagy az Euklidész-lemmát (hogy ha egy p prímszám osztja ab -t , akkor a -t vagy b -t kell osztania ).

Mivel minden természetes számnak (> 1) van legalább egy prímtényezője, és két egymást követő n és ( n + 1) számnak nincs közös osztója, az n ( n + 1) szorzatnak több különböző prímosztója van, mint az n számnak. magát . Így a téglalap alakú számok lánca :
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}, · · ·
végtelenül bővülő prímhalmazok sorozatát adja meg.

Pinasco

2009-ben Juan Pablo Piasco a következő bizonyítást javasolta [7] .

Legyen a legkisebb N prímszám. Ekkor a befogadó-kizárási elv szerint az x -et meg nem haladó és ezekkel a prímekkel osztható pozitív egészek száma ${\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}}}\jobbra\rfloor -\cdots \\&\cdots \pm (-1)^{N+1}\left\lfloor {\frac {x}{p_{1}\cdots p_{N}}}\jobbra\rpadló .\qquad (1)\end{igazított}}

Ha elosztjuk x -szel és hagyjuk , azt kapjuk $x\to \infty$

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

Ezt át lehet írni így

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

Ha nincs más prímszám, mint az, akkor az (1) kifejezés egyenlő , a (2) kifejezés egyenlő 1-gyel, de egyértelmű, hogy a (3) kifejezés nem egyenlő eggyel. Így a -tól eltérő prímszámoknak kell lenniük . $p_{1},\dots ,p_{N}$ $\lfloor x\rfloor$ $p_{1},\dots ,p_{N}$

Wang

2010-ben Jun Ho Peter Wang a következő ellentmondásos bizonyítékot tette közzé [8] . Legyen k valamilyen természetes szám. Ezután a Legendre-képlet szerint

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

(termék az összes prímszám felett)

ahol

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.

De ha csak véges számú prím van,

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

(a tört számlálója exponenciálisan növekszik , míg Stirling képlete szerint a nevező gyorsabban növekszik, mint az egyszerű exponenciális), ami ellentmond annak, hogy minden k esetén a számláló nagyobb vagy egyenlő, mint a nevező.

Bizonyítás irracionalitás használatával $\pi$

A Leibniz-képletet $\pi$ Euler szorzataként ábrázolva [9] jön létre .

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

A számlálók páratlan prímszámok, és minden nevező a 4 legközelebbi többszöröse a számlálóhoz.

Ha véges számú prím lenne, ez a képlet racionális reprezentációt adna , amelynek nevezője az összes szám szorzata, ami ellentétes az irracionalitással . $\pi$ $\pi$

Bizonyítás információelmélet segítségével

Alexander Shen és munkatársai az összenyomhatatlansági módszer [10] és a Kolmogorov-komplexitás segítségével bizonyítottak :

Tegyük fel, hogy csak k prímszám van ( ). Az aritmetika alaptétele szerint bármely n természetes szám ábrázolható így $p_{1},\pontok ,p_{k}$

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

ahol a nemnegatív e i egész számok egy véges méretű prímlistával együtt elegendőek a szám rekonstruálásához. Mivel minden i esetén ebből az következik, hogy mind (ahol a 2-es bázis logaritmusát jelenti). $p_{i}\geqslant 2$ $e_{i}\leqslant \log n$ $\log$

Ez a következő méretű n kódolási módszert ad ( "nagy O" jelöléssel ):

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

bit.

Ez sokkal hatékonyabb kódolás, mint az n közvetlen bináris megjelenítése, amely biteket igényel. A megállapított veszteségmentes tömörítési eredmény azt állítja, hogy nincs algoritmus N bit információ veszteségmentes tömörítésére N bitnél kevesebbre . A fenti ábrázolás sérti ezt az állítást, mert kellően nagy n esetén . $N=O(\log n)$ $\log \log n=o(\log n)$

Így végtelen sok prímszám van.

Prímszámok aszimptotikus eloszlása

A prímszám-eloszlás tétele kimondja, hogy az n -nél kisebb prímek száma , amelyet jelöl , [11] -vel nő . $\pi(n)$ $n/\ln(n)$

Lásd még

Megjegyzések

↑ Ez az egyenlőség az Euler-szorzat képletének speciális esete a Riemann-zéta függvény esetében .

Jegyzetek

↑ The Beginnings of Euclid, 1949-1951 , IX. könyv, 20. tézis, p. 89.
↑ James Williamson (fordító és kommentátor), The Euclid, With Dissertations , Clarendon Press , Oxford, 1782, 63. oldal, Euklidész bizonyítékának angol fordítása Archiválva 2011. január 23-án a Wayback Machine -nél
↑ Kemény, Michael; Woodgold, Catherine. Prime Simplicity (angol) // The Mathematical Intelligencer . - 2009. - 1. évf. 31 , sz. 4 . - P. 44-52 . - doi : 10.1007/s00283-009-9064-8 . (Angol)
↑ Bostock, Chandler, Rourke, 2014 , p. 168.
↑ Rómeó Mestrovic. Eukleidész tétele a prímszámok végtelenségéről: bizonyítások történeti áttekintése (Kr. e. 300--2012) és egy másik új bizonyítás // arXiv:1202.3670 [math]. — 2012-02-16. Az eredetiből archiválva : 2018. június 12.
↑ Saidak, 2006 .
↑ Pinasco, 2009 , p. 172–173.
↑ Whang, 2010 , p. 181.
↑ Debnath, 2010 , p. 214.
↑ Verescsagin, Uszpenszkij, Shen, 2013 , p. 267.
↑ Diamond G. Elemi módszerek a prímszámok eloszlásának vizsgálatában // Uspekhi Mat . - 1990. Archiválva : 2018. július 7.

Irodalom

Eukleidész kezdetei / Görög fordítás és D. D. Mordukhai-Boltovsky megjegyzései M. Ya. Vygodsky és I. N. Veselovsky szerkesztői közreműködésével . - M. - L .: GTTI, 1949-1951. - (A természettudomány klasszikusai).
Michael Hardy, Catherine Woodgold. Prime Simplicity (angol) // The Mathematical Intelligencer . - 2009. - 1. évf. 31 , sz. 4 . - P. 44-52. .
Eukleidész elemei, értekezésekkel // Clarendon Press / James Williamson (fordítás és kommentár). - Oxford, 1782. - S. 63 .
Junho Peter Whang. A prímszámok végtelenségének újabb bizonyítéka // American Mathematical Monthly . - 2010. - február ( 117. évf. , 2. szám ). - S. 181 .
Fülöp Saidak. Euklidész tételének új bizonyítása // American Mathematical Monthly . - 2006. - December ( 113. évf. , 10. szám ). - doi : 10.2307/27642094 .
Lokenath Debnath. Leonhard Euler öröksége: Tricentenáriumi tiszteletadás . - World Scientific, 2010. - 214. o . — ISBN 9781848165267 .
Nyikolaj Konsztantyinovics Verescsagin , Vlagyimir Andrejevics Uszpenszkij , Alekszandr Shen . Kolmogorov komplexitás és algoritmikus véletlenszerűség . — A Moszkvai Matematikai Folyamatos Oktatási Központ kiadója, 2013.
Juan Pablo Pinasco. Euklidész és Euler tételeinek új bizonyításai // American Mathematical Monthly . - 2009. - február ( 116. évf. , 2. szám ).

Linkek

Weisstein, Eric W. Euclid's Theorem (angolul) a Wolfram MathWorld webhelyen .
Euklidész elemei, IX. könyv, Prop. 20 (Euklidész bizonyítéka, David Joyce honlapján a Clark Egyetemen)
Euklidész tételének 125 bizonyítása