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

a
jelölés
(→‎A Carmichael-számok karakterizációja: 2. bizonyításának befejezése)
a (jelölés)
''1<a<n''. [[Euklidészi algoritmus]]sal ellenőrizhető, hogy ''n'' és ''a'' [[relatív prímek]]. Ha nem azok, akkor ''n'' bukja a tesztet, [[összetett szám|összetett]].
 
Ha ''n'' prím, akkor \''a^(''<sup>''n-1)''-1</sup> kongruens ''1 mod n''. Ha nem így van, akkor ''n''
bukja a tesztet, összetett. Ha igen, akkor újabb véletlen ''a'' -val
folytatódik a vizsgálat, egészen addig, amíg eléggé biztossá nem
==Álprímek==
 
Ha ''n'' összetett, és \''a^(''<sup>''n''-1)</sup> ''kongruens 1 mod n'' valamely ''a'' -ra, akkor ''n a''
alapú '''álprím''', másként '''pszeudoprím'''. Ilyen például a ''341'', ami álprím a ''2'' alapra.
 
 
2. Legyen ''lnko(b_1,n)=lnko(b_2,n)=1''. Ha ''n'' álprím a ''b_1 ''és a ''b_2'' alapra
nézve, akkor álprím a ''b_1b_2'', és a \''b_1b_2^(-1)''<sup>-1</sup> alapokra is, ahol
\''b_2^(-1)''<sup>-1</sup> a redukált mod n maradékosztályok csoportján értendő.
 
3. Ha ''n'' csak egyetlen hozzá relatív prím ''t'' -re is bukja a
'''Bizonyítás:'''
 
1. Ha ''b d'' rendje osztója ''n-1'' -nek, akkor \''b^(<sup>''n''-1)</sup> kongruens 1 mod n'', mert akkor ''n-1=kd'' valamely egész ''k'' -ra, így \''b^''<sup>(''n''-1)</sup>=''b^<sup>(kd)</sup>=(b^<sup>d)^<sup>k</sup></sup> kongruens 1^<sup>k</sup>=1 mod n''.
 
Vizsgáljuk most a redukált ''mod n'' maradékosztályokat. Ha ebben a csoportban valamely elemre igaz az, hogy \''a^''<sup>''n-1''-1</sup> 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.
 
Ha a legkisebb ilyen ''k'' -t vesszük, akkor ez az előzőek szerint osztója lesz ''n-1'' -nek, mert ha nem lenne meg maradéktalanul benne, akkor az a maradék kisebb lenne. Ez a legkisebb ''k'' kitevő pedig definíció szerint ''a'' maradékosztályának rendje a redukált maradékosztályok csoportjában.
 
2. Az kell, hogy az ilyen redukált maradékosztályok csoportot alkotnak. Ez így van, mert egyrészt \''(b_1)^<sup>d</sup>(b_2)^<sup>d</sup>=(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''
 
3. Legyenek most ''b_1<b_2< ... <b_k'' páronként inkongruens alapok, amelyekre n álprím. Most tekintsünk egy olyan ''n'' -hez relatív prím ''t'' -t, amelyre ''n'' bukja a tesztet. Szorozzuk meg vele az előbbi ''b_1<b_2< ... <b_k'' számokat, ezek páronként inkongruensek lesznek.
'''Állítás''' - ''n'' bukja a tesztet ezekre a ''tb_1<tb_2< ... <tb_k'' számokra.
 
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''<sup>-1</sup> maradékosztály minden elemére álprím, így a ''t'' számra is, ami ellentmondás.
 
==A Carmichael-számok karakterizációja==
'''Bizonyítás'''
 
1. Tegyük fel, hogy \''p^2''<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 \''mod p^2''<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^2''<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^2''<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]]