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

(→‎A Carmichael-számok karakterizációja: 2. bizonyítás bevezetése)
Tegyük fel indirekt, hogy ''b^(n-1) kongruens 1 mod n''. Ekkor a kongruencia ''p^2'' -re is teljesül, hiszen ''p^2'' osztója ''n'' -nek. ''b mod p^2'' rendje osztója ''n-1'' -nek, de ''b'' primitív gyök ''mod p^2''. Ezért ''p-1'' és ''p'' is osztója ''n-1'' -nek, és ez ellentmondás, mert két szomszédos egész szám mindig relatív prím egymáshoz.
 
2. Legyen most ''n'' páratlan, összetett és négyzetmentes. Ha most ''b'' relatív prím ''n'' -hez, akkor a Fermat-tétel szerint teljesül ''b^(p-1) kongruens 1 mod p''. Mivel ''p'' osztója ''n'' -nek, azért ''b^(n-1) kongruens 1 mod p'' fennáll minden ''b'' relatív prímre és ''p'' prímosztóra. Tekintsük a következő kongruenciarendszert:
 
''b kongruens g mod p''
 
''b kongruens 1 mod m'',
 
ahol ''m=n/p'', és ''g'' primitív gyök ''mod p''
 
Ez megoldható, mert ''m'' és ''p^2'' relatív prímek. Vegyük a kongruenciarendszer egy ''b'' megoldását.
 
[[Kategória:Számelmélet]]