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

a
→‎Álprímek: segédjelek eltáv
a (→‎Álprímek: indexek jav)
a (→‎Álprímek: segédjelek eltáv)
maradékosztályok csoportjában ''b'' rendje osztója ''n-1'' -nek.
 
2. Legyen \''lnko(b<sub>1</sub>,n)=lnko(b<sub>2</sub>,n)=1''. Ha ''n'' álprím a \''b''<sub>1</sub> és a \''b''<sub>2</sub> alapra
nézve, akkor álprím a \''b''<sub>1</sub>''b''<sub>2</sub>, és a \''b''<sub>1</sub>''b''<sub>2</sub><sup>-1</sup> alapokra is, ahol
''b''<sub>2</sub><sup>-1</sup> a redukált mod n maradékosztályok csoportján értendő.
 
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.
 
'''Á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ály]]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==