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

a
→‎Álprímek: dőlés jav
(→‎Források: új forrás hozzáadása)
a (→‎Álprímek: dőlés jav)
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''<sub>1</sub>)<sup>''d''</sup>(''b''<sub>2</sub>)<sup>''d''</sup>=(''b''<sub>1</sub>''b''<sub>2</sub>)<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''<sub>1</sub><''b''<sub>2</sub>< ... <''b''<sub>''k''</sub> 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''<sub>1</sub><''b''<sub>2</sub>< ... <''b''<sub>''k''</sub> számokat, ezek páronként inkongruensek lesznek.