Végtelen sok prímszám létezik – bizonyítás
Indirekt módon bebizonyítjuk, hogy végtelen sok prímszám van. Eukleidész már az ókorban bebizonyította, hogy nincs legnagyobb prímszám. A most közölt bizonyítás az ő gondolatmenetén alapul.
Indirekt módon tegyük fel, hogy csak véges sok prímszám van; legyenek ezek Az indirekt feltevésünkből ellentmondásra fogunk jutni, ez bizonyítja azt, hogy valóban végtelen sok prímszám létezik.
Definiáljuk a számot a következőképpen:
Mivel a
szorzat pozitív, ezért
így
vagy prímszám, vagy összetett szám. Vizsgáljuk meg mindkét esetet:
prímszám: A definíció miatt
nagyobb, mint bármelyik
prím, speciálisan mindegyiküktől különbözik. Ezzel találtunk egy
prímet, ami ellentmond azon feltevésünknek, miszerint csak a
számok prímek.
összetett szám: Tudjuk, hogy
így a számelmélet alaptétele szerint
(a prímtényezők sorrendjétől eltekintve egyértelműen) felbomlik prímtényezők szorzatára. Szemeljük ki tetszőlegesen az egyik prímszámot, amelyik szerepel ebben a szorzatban; mivel feltevésünk szerint
az összes prímszám, ezért ez a prím
lesz valamelyik
indexre. Erre a prímszámra
lesz, azaz valamilyen alkalmas
egész számra
Ezt az összefüggést beírva
definíciójába az alábbi egyenletekhez jutunk:
Az egyenlet jobb oldalának mindkét tagjában szerepel mint szorzótényező, tehát mindkét tag osztható
-vel, ami folytán az egész jobb oldal is osztható
-vel. Az egyenlőség miatt így a bal oldalnak is oszthatónak kell lennie
-vel.
Azt kaptuk, hogy egy egynél nagyobb prímszám osztja az -et, ami lehetetlen. Ezzel a
-re vonatkozó mindkét vizsgált esetben ellentmondásra jutottunk, emiatt a kezdeti feltevésünk hamis. Bebizonyítottuk, hogy végtelen sok prímszám létezik.