Valaki tud ellen példát hozni?

Ha utána olvasol a prímszámoknak, akkor láthatod, hogy nincs biztos módszer egy prím (a következő) kiszámítására.

Vannak prím tesztek, amelyek különböző biztonsággal valószínűsítik egy számról, hogy prím, de biztos választ csak a törzstényezős felbontással lehet kapni.

Ha ilyen egyszerű lenne a prím számokat kiszámítani, az igen nagy csapás lenne a számítástechnikai biztonságra, mert az nagyrészt az RSA algoritmusra alapoz. Ez viszont attól olyan biztonságos, hogy egy igen hosszú (több száz jegyű) szám esetén a törzstényezős felbontás gyakorlatilag kivitelezhetetlen (vagyis évezredekig, évmilliókig tartana).

Amíg nincs egyszerűbb (és főleg gyorsabb) lehetőség a törzstényezős felbontásnál, addig biztonságosak az RSA eljárások, és addig nem tudunk gyorsan prímet számítani.

Pedro

A "Végelen sok prím szám van" tétel bizonyítása a következő:

Fogjuk az eddig megtalált összes prímszámot, szorozzuk össze őket majd az eredményhez adjunk hozzá 1-et.

Az így kapott számnak egész biztosan nem osztója egyik eddigi prím sem, így egy új prímszámot kaptunk.

Ezt akárhányszor megtehetjük, így végtelen sok prím szám van.

Na most ekkor ez a bizonyítás nem helyes.

Vagy hol a hiba a gondolatmenetben?

Miért nem igaz az állításod?

Nyilvánvaló, hogy az összeszorzott prímek ±1-gyel kapott számnak egész biztosan nem osztója egyik eddigi prím sem,

de csak akkor prím, ha a négyzetgyökéig egyik prím sem osztója.

A hosszabb szorzatoknál már nagy a különbség, és csak ritkábban prímek.

Pl.: 2*3*5*7*11*13+1=30031, 13-ig ugyan nincs prímosztója, de 17...√(30031)~173,3 között lehet, és van is.

Prímszorzatok ±1 prím-e?

5 True 7 True

29 True 31 True

209 False 211 True

2309 True 2311 True

30029 True 30031 False

510509 False 510511 False

9699689 False 9699691 False

223092869 False 223092871 False

6469693229 False 6469693231 False

200560490129 False 200560490131 True

Áhh, rosszul emlékeztem a bizonyításra, való igaz...

Helyesen: [link]