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

a
Tegyük fel indirekt, hogy ''b''<sup>(''n''-1)</sup> ''kongruens 1 mod n''. Ekkor a kongruencia ''p''<sup>2</sup> -re is teljesül, hiszen ''p<sup>2</sup>'' osztója ''n'' -nek. ''b mod p<sup>2</sup>'' rendje osztója ''n-1'' -nek, de ''b'' primitív gyök ''mod p<sup>2</sup>''. 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''<sup>(''p''-1)</sup> ''kongruens 1 mod p''. Mivel ''p'' osztója ''n'' -nek, azért ''b''<sup>(''n''-1)</sup> ''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''