„Fermat-prímteszt” változatai közötti eltérés

[nem ellenőrzött változat][nem ellenőrzött változat]
Tartalom törölve Tartalom hozzáadva
→‎Álprímek: 1. bionyításának folytatása
→‎Álprímek: 1. bizonyításának befejezése
42. sor:
 
Vizsgáljuk most a redukált ''mod n'' maradékosztályokat. Ha ebben a csoportban valamely elemre igaz az, hogy ''a^n-1'' kongruens ''1 mod n'', és egy másik ''k'' kitevőre is kongruens ''1 mod n'', akkor ''a^n-1-k'' kongruens ''1 mod n'' is teljesül. Így le lehet folytatni az euklidészi algoritmust, és kiderül, hogy ''d=lnko(n-1,k)'' -ra is igaz, hogy ''a^d'' kongruens ''1 mod n''. Tehát van egy ''d'' osztója ''n-1'' -nek, amire a kongruencia teljesül.
 
Ha a legkisebb ilyen ''k'' -t vesszük, akkor ez az előzőek szerint osztója lesz ''n-1'' -nek, mert ha nem lenne meg maradéktalanul benne, akkor az a maradék kisebb lenne. Ez a legkisebb ''k'' kitevő pedig definíció szerint ''a'' maradékosztályának rendje a redukált maradékosztályok csoportjában.
 
2. Az kell, hogy az ilyen redukált maradékosztályok csoportot alkotnak. Ez így van, mert egyrészt ''(b_1)^d(b_2)^d=(b_1b_2)^d'' (merthogy a redukált maradékosztályok csoportja kommutatív). Másrészt, ha ''b'' rendje ''d'', akkor inverzének rendje is ''d''