Végtelen sok prímszám létezik – bizonyítás

3 perc olvasá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.

Hirdetés

Indirekt módon tegyük fel, hogy csak véges sok prímszám van; legyenek ezek $p_1, p_2, p_3, p_4, \ldots , p_n.$ 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 $p_{n+1}$ számot a következőképpen: $p_{n+1} = p_1p_2p_3 \ldots p_n + 1.$ Mivel a $p_1p_2p_3 \ldots p_n$ szorzat pozitív, ezért $p_{n+1} > 1,$ így $p_{n+1}$ vagy prímszám, vagy összetett szám. Vizsgáljuk meg mindkét esetet:

$p_{n+1}$ prímszám: A definíció miatt $p_{n+1}$ nagyobb, mint bármelyik $p_i$ prím, speciálisan mindegyiküktől különbözik. Ezzel találtunk egy $(n+1).$ prímet, ami ellentmond azon feltevésünknek, miszerint csak a $p_1,p_2, \ldots ,p_n$ számok prímek.
$p_{n+1}$ összetett szám: Tudjuk, hogy $p_{n+1}>1,$ így a számelmélet alaptétele szerint $p_{n+1}$ (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 $p_1, p_2, \ldots, p_n$ az összes prímszám, ezért ez a prím $p_i$ lesz valamelyik $i$ indexre. Erre a prímszámra $p_i | p_{n+1}$ lesz, azaz valamilyen alkalmas $k$ egész számra $p_{n+1} = kp_i.$ Ezt az összefüggést beírva $p_{n+1}$ definíciójába az alábbi egyenletekhez jutunk:

$p_1p_2p_3 \ldots p_n + 1 = p_{n+1} = kp_i$

$1 = kp_i - p_1p_2p_3 \ldots p_n$

Az egyenlet jobb oldalának mindkét tagjában szerepel $p_i,$ mint szorzótényező, tehát mindkét tag osztható $p_i$ -vel, ami folytán az egész jobb oldal is osztható $p_i$ -vel. Az egyenlőség miatt így a bal oldalnak is oszthatónak kell lennie $p_i$ -vel.

Hirdetés

Azt kaptuk, hogy egy egynél nagyobb prímszám osztja az $1$ -et, ami lehetetlen. Ezzel a $p_{n+1}$ -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.