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

a
→‎Álprímek: jelölés
a (jelölés)
a (→‎Álprímek: jelölés)
'''Bizonyítás:'''
 
1. Ha ''b d'' rendje osztója ''n-1'' -nek, akkor \''b<sup>''n''-1</sup> kongruens 1 mod n'', mert akkor ''n-1=kd'' valamely egész ''k'' -ra, így \''b''<sup>(''n''-1)</sup>=''b<sup>(kd)</sup>=(b<sup>d)<sup>k</sup></sup> kongruens 1<sup>k</sup>=1 mod n''.
 
Vizsgáljuk most a redukált ''mod n'' maradékosztályokat. Ha ebben a csoportban valamely elemre igaz az, hogy \''a''<sup>''n''-1</sup> kongruens ''1 mod n'', és egy másik ''k'' kitevőre is kongruens ''1 mod n'', akkor \''a''<sup>n-1-k<\sup> kongruens ''1 mod n'' is teljesül. Így le lehet folytatni az euklideszi 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)<sup>d</sup>(b_2)<sup>d</sup>=(b_1b_2)<sup>d</sup>'' (merthogy a redukált maradékosztályok csoportja kommutatív). Másrészt, ha ''b'' rendje ''d'', akkor inverzének rendje is ''d''
 
3. Legyenek most ''b_1<b_2< ... <b_k'' páronként inkongruens alapok, amelyekre n álprím. Most tekintsünk egy olyan ''n'' -hez relatív prím ''t'' -t, amelyre ''n'' bukja a tesztet. Szorozzuk meg vele az előbbi ''b_1<b_2< ... <b_k'' számokat, ezek páronként inkongruensek lesznek.