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

(→‎A Carmichael-számok karakterizációja: 1. bizonyítás befejezése)
(→‎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.
[[Kategória:Számelmélet]]