Prímszámok száma végtelen

Eukleidész  már az ókorban bebizonyította, hogy nincs legnagyobb prímszám.
Az ő bizonyítása mai megfogalmazással a következő:

Állítás:  Nincs legnagyobb prímszám.

Bizonyítás (indirekt bizonyítás):

    1. Tételezzük fel az ellenkezőjét, azaz tételezzük fel, hogy van legnagyobb prímszám, azaz a prímszámok száma véges. Tegyük fel, hogy „k” darab prímszám van: p1=2, p2=3, p3=5 és a feltételezett utolsó prímszám a k-ik pk.
    2. Szorozzuk össze a feltételezett összes prímszámot: p1⋅p2⋅p3⋅….⋅pk, majd adjunk hozzá 1-t!
      Az így kapott N=p1⋅p2⋅p3⋅….⋅pk +1 szám vagy prím, vagy összetett.

      • Ha az így képzett N szám prím, akkor különbözik mindegyiktől, amit összeszoroztunk, tehát nem igaz, hogy az összes prímszám szerepel az N szám képzésében.
      • Ha pedig N összetett szám, akkor van prímosztója.
        De az oszthatóság szabályai szerint ez nem lehet egyik sem a pk-ig terjedő prímszámok között.
    3. Van tehát az általunk gondolt összes (k db) prímszámon kívül más prímszám is. Ez ellentmond annak a feltételezésnek, hogy véges számú prímszám van.

Eukleidész ugyanezt így fogalmazta meg Elemek című művében:

“Prímszámból prímszámok bármely sokaságánál több van. Legyenek az adott prímszámok a, b és c. Azt állítom, hogy több prímszám van, mint a, b és c. Vegyük ugyanis a, b és c legkisebb közös többszörösét, legyen ez DE, és adjuk hozzá DE-hez a DF egységet. Ekkor EF vagy prím, vagy nem. Legyen először prím. Találtunk tehát az a, b és c számoknál több prímet, a-t, b-t, c-t és EF-t. Ne legyen most EF prím. Ekkor osztja valamelyik prímszám. Osztja a g prím. Azt állítom, hogy g az a, b és c egyikével sem azonos. Tegyük föl ugyanis, hogy az a, b és c osztják DE-t, tehát g is osztja DE-t. Viszont EF-t is osztja, tehát a maradék DF egységet is osztja g, noha szám, ami ellentmondás. A g tehát nem azonos az a, b, c számok egyikével sem. S feltétel szerint prím, tehát találtunk az adott a, b, c prímeknél több prímet, a-t, b-t, c-t, g-t. Éppen ezt kellett megmutatni.” 

 (Quod erat demonstrandum. Q.E.D.)

Megjegyzés: A prímszámok halmaza megszámlálhatóan végtelen számosságú halmaz.

Bár tudjuk, hogy nincs legnagyobb prímszám, ennek ellenére a matematikusok egyre nagyobb prímszámok után kutatnak.

Print Friendly, PDF & Email

Comments are closed, but trackbacks and pingbacks are open.