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

a
a (→‎Menete: segédjel törlése)
'''Bizonyítás'''
 
1. Tegyük fel, hogy \''p''<sup>2</sup> 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 \''p''<sup>2</sup>. Legyen ''m'' a legnagyobb olyan osztója ''n'' -nek, ami négyzetmentes, és nem osztható ''p'' -vel. Tekintsük a következő kongruenciarendszert:
 
''b kongruens g mod p^2''
'''Állítás''' - ''n'' bukja a tesztet a ''b'' alapra nézve.
 
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''
ahol ''m=n/p'', és ''g'' primitív gyök ''mod p''
 
Ez megoldható, mert ''m'' és \''p''<sup>2</sup> relatív prímek. Vegyük a kongruenciarendszer egy ''b'' megoldását.
 
Következik, hogy \''b''<sup>''n''-1</sup> ''kongruens g''<sup>''n''-1</sup> ''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<sup>(n-1)</sup> nem kongruens 1 mod p'', így \''b''<sup>''p''-1</sup> ''nem kongruens 1 mod n''
[[Kategória:Számelmélet]]