Megegyezhet-e két prímszám utolsó ezer számjegye?

ha nem választható ki G úgy, hogy nem rel prímek, akkor minden prímszámnak csak véges darabszámú többszöröse lehet H-ban. Innentől teljes indukcióval: ha már n elemet kiválasztottunk H-ból, az véges*véges=véges darabszámú elemet zár ki, tehát mindig választhatunk hozzá még 1-et, ami az összes korábbihoz rel prím.

RSA-hoz sok jó leírás van, nem hinném, hogy ne bírkóznál meg vele.

Tehát H-ban végtelen természetes szám van. pl. {6,7,9,12,13,15,25,...}

Ha van olyan P prímszám, amelynek végtelen sok többszöröse van benne, akkor ezeket beválasztva G-be olyan halmazt kapunk, hogy bármely kettő nem relatív prím, mivel a legnagyobb közös osztójuknak osztója a P.

Innentől tehát feltesszük, hogy nincs ilyen P, vagyis minden prímszámnak véges sok többszöröse van H-ban, pl. csak 5db páros van benne.

Ezután elkezdünk válogatni H-ból. G[n] a H olyan n-elemű részhalmazát jelöli, amelyben a számok páronként relatív prímek. Pl. G[3] = {6,7,13}

Tudjuk, hogy G[n]-ben n (véges sok) elem van és mind véges sok prímtényezőből áll. Ezek által véges sok elemet zárnak ki H-ból. Pl. a G[3]={6,7,13} a 2,3,7 és 13 többszöröseit zárja ki, ami mind véges sok, és véges sok véges szám összege is véges sok. Mivel H-ban végtelen sok elem van, ezért lesz benne olyan, amit nem zártunk ki (pl. 25), ezt hozzávéve az eredetileg kiválasztott elemekhez, egy nagyobb G[i=n+1] halmazt kaptunk (pl. G[4]={6,7,13,25} )

Az első elemet tetszőleges módon választhatjuk. Tehát teljes indukcióval igazoltuk, hogy akármennyi elemet kiválaszthatunk. Ez esetünkben azt jelenti, hogy (megszámlálhatóan) végtelen sok elemet is kiválaszthatunk. G=unió(i=1..végtelen, G[i])

Megegyezhet-e két prímszám utolsó ezer számjegye?

Igen megegyezhet, de bizonyitásom nincs, csak filozófiai jellegű:

Végetelen sok szám van, és végtelen sok prímszám is.

Vegyünk egy számot: x = y* 10^1000 + z

Ahol z<10^1000, vagyis csak maximum 1000 számjegyből áll. És y>=1, valamint x és y csak természetes szám lehet.

Ekkor rájöhetünk, hogy az y bármennyi lehet, azaz végtelen féle x alakú szám létezik.

Ebből az következik, hogy végtelen féle ilyen alakú primszám létezik.

Ekkor vegyük a következő számot, ami szintén x alakú:

a= b*10^1000 + z

Ebből megint arra jutunk, hogy végtelen féle ilyen szám van, ami nem egyenlő a feltételezett x primszámunkkal.

Ebből logikusnak tűnik, hogy végtelen olyan primszám létezik, aminek az utolsó ezer számjegye megegyezik.

Ez nem bizonyitás... de remélem elég... :P