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

Ha ''n'' prím, akkor \''a^(''^''n-1)''-1 kongruens ''1 mod n''. Ha nem így van, akkor ''n''

Ha ''n'' összetett, és \''a^(''^''n''-1) ''kongruens 1 mod n'' valamely ''a'' -ra, akkor ''n a''

nézve, akkor álprím a ''b_1b_2'', és a \''b_1b_2^(-1)''^-1 alapokra is, ahol

\''b_2^(-1)''^-1 a redukált mod n maradékosztályok csoportján értendő.

1. Ha ''b d'' rendje osztója ''n-1'' -nek, akkor \''b^(^''n''-1) kongruens 1 mod n'', mert akkor ''n-1=kd'' valamely egész ''k'' -ra, így \''b^''^(''n''-1)=''b^^(kd)=(b^^{d)^^k} kongruens 1^^k=1 mod n''.

Vizsgáljuk most a redukált ''mod n'' maradékosztályokat. Ha ebben a csoportban valamely elemre igaz az, hogy \''a^''^''n-1''-1 kongruens ''1 mod n'', és egy másik ''k'' kitevőre is kongruens ''1 mod n'', akkor \''a^''<sup>n-1-k''<\sup> kongruens ''1 mod n'' is teljesül. Így le lehet folytatni az euklideszi algoritmust, és kiderül, hogy ''d=lnko(n-1,k)'' -ra is igaz, hogy ''a^d'' kongruens ''1 mod n''. Tehát van egy ''d'' osztója ''n-1'' -nek, amire a kongruencia teljesül.

2. Az kell, hogy az ilyen redukált maradékosztályok csoportot alkotnak. Ez így van, mert egyrészt \''(b_1)^^d(b_2)^^d=(b_1b_2)^<sup>d'' (merthogy a redukált maradékosztályok csoportja kommutatív). Másrészt, ha ''b'' rendje ''d'', akkor inverzének rendje is ''d''

Tegyük fel indirekt, hogy ''tb_i'' -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_ib_i^-1''^-1 maradékosztály minden elemére álprím, így a ''t'' számra is, ami ellentmondás.

1. Tegyük fel, hogy \''p^2''² osztója ''n'' -nek. Belátjuk, hogy ''n'' nem lehet Carmichael-szám.

Mivel ''n'' páratlan, azért ''p>2''. Vegyünk egy ''g'' primitív gyököt \''mod p^2''². Legyen ''m'' a legnagyobb olyan osztója ''n'' -nek, ami négyzetmentes, és nem osztható ''p'' -vel. Tekintsük a következő kongruenciarendszert:

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

Ez megoldható, mert ''m'' és \''p^2''² relatív prímek. Vegyük a kongruenciarendszer egy ''b'' megoldását.

Következik, hogy \''b^(''^''n''-1) ''kongruens g^(''^''n''-1) ''mod p''. Ez teljesül, ha ''p-1'' osztója ''n-1'' -nek, ugyanis ''g'' rendje ''p-1 mod p'', és éppen ez az állítás. Különben \''b^^(n-1) nem kongruens 1 mod p'', így \''b^(''^''p''-1) ''nem kongruens 1 mod n''