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

a
Bot: Átirányítások javítása
a (Bot: következő hozzáadása: nl:Fermattest)
a (Bot: Átirányítások javítása)
 
Meg kívánjuk vizsgálni, hogy ''n'' szám ''1''-nél nagyobb páratlan egész prím-e. Legyen
''1<a<n''. [[Euklidészi algoritmus]]sal ellenőrizhető, hogy ''n'' és ''a'' [[relatív prímek]]. Ha nem azok, akkor ''n'' bukja a tesztet, [[összetett számszámok|összetett]].
 
Ha ''n'' prím, akkor ''a''<sup>''n''-1</sup> kongruens ''1 mod n''. Ha nem így van, akkor ''n''
'''Tétel:'''
 
1. ''n'' [[csakkorbikondicionális|akkor és csak akkor]] álprím a ''b'' alapra, ha a ''mod n''
maradékosztályok csoportjában ''b'' rendje osztója ''n-1'' -nek.
 
'''Állítás''' - ''n'' bukja a tesztet ezekre a ''tb''<sub>1</sub><''tb''<sub>2</sub>< ... <''tb''<sub>''k''</sub> számokra.
 
Tegyük fel indirekt, hogy ''tb''<sub>''i''</sub> -re nem bukja a tesztet, azaz ''n'' álprím erre az alapra. Ekkor ''mod n'' számolva a [[redukált maradékosztálymaradékrendszer|redukált maradékosztályok]]ok csoportjában ''n'' a ''tb''<sub>''i''</sub>''b''<sub>''i''</sub><sup>-1</sup> maradékosztály minden elemére álprím, így a ''t'' számra is, ami ellentmondás.
 
==A Carmichael-számok karakterizációja==
51 382

szerkesztés