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

a
a (hiv. korr, AWB)
 
1. ''n'' [[bikondicionális|akkor és csak akkor]] álprím a ''b'' alapra, ha a ''mod n''
maradékosztályok csoportjában ''b'' [[multiplikatív rend|rendje]] osztója ''n-1'' -nek.
 
2. Legyen ''lnko(b<sub>1</sub>,n)=lnko(b<sub>2</sub>,n)=1''. Ha ''n'' álprím a ''b''<sub>1</sub> és a \''b''<sub>2</sub> alapra
3. Legyenek most ''b''<sub>1</sub><''b''<sub>2</sub>< … <''b''<sub>''k''</sub> 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''<sub>1</sub><''b''<sub>2</sub>< … <''b''<sub>''k''</sub> számokat, ezek páronként inkongruensek lesznek.
 
'''''Állítás''''' - ''n'' bukja a tesztet ezekre a ''tb''<sub>1</sub><''tb''<sub>2</sub>< … <''tb''<sub>''k''</sub> számokra.
 
Tegyük fel indirekt, hogy ''tb''<sub>''i''</sub> -re nem bukja a tesztet, azaz ''n'' álprím erre az alapra. Ekkor ''mod n'' számolva a [[redukált maradékrendszer|redukált maradékosztályok]] csoportjában ''n'' a ''tb''<sub>''i''</sub>''b''<sub>''i''</sub><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==
'''Tétel: '''Legyen ''n'' páratlan összetett szám. ''n'' akkor és csak akkor Carmichael-szám, ha teljesülnek rá a következők:
'''Tétel:'''
 
1. ''n'' [[négyzetmentes szám|négyzetmentes]] és
Legyen ''n'' páratlan összetett szám. ''n'' akkor és csak akkor Carmichael-szám, ha teljesülnek rá a következők:
 
2. Minden n minden ''p'' prímosztójára ''<math>p-1'' osztója ''|n-1'' -nek</math>.
1. ''n'' [[négyzetmentes szám|négyzetmentes]]
 
'''Bizonyítás'''
2. Minden ''p'' prímosztójára ''p-1'' osztója ''n-1'' -nek.
 
1. Tegyük fel, hogy ''pn''<sup>2</sup> osztója ''n''nem -neknégyzetmentes. Belátjuk, hogy ''n'' nem lehet Carmichael-szám.
'''Bizonyítás'''
 
Mivel ''n'' nem négyzetmentes, van olyan ''p'' prímszám, hogy <math>p^2| n</math>.
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|primitív gyököt]] moduló ''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:
 
'':<math> b kongruens\equiv g mod \pmod{p^2''}</math>
:<math> b \equiv 1 \pmod{m}</math>.
 
Ez a kongruenciarendszer megoldható, mert ''m'' és ''p^2''<sup>2</sup> relatív prímek. Vegyük a kongruenciarendszer egy ''b'' megoldását.
''b kongruens 1 mod m''
 
'''''Állítás''''' - ''n'' bukja a tesztet a ''b'' alapra nézve.
Ez megoldható, mert ''m'' és ''p^2'' relatív prímek. Vegyük a kongruenciarendszer egy ''b'' megoldását.
 
Tegyük fel indirekt, hogy <math>b^{n-1}\equiv 1\pmod{n}</math>.
'''Á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<supmath>p^2 |n</supmath>'' 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:
:<math>b^{p-1}\equiv 1\pmod{p}</math>.
Mivel <math>p|n</math>, ezért minden ''b'' relatív prímre és ''p'' prímosztóra:
:<math>b^{n-1}\equiv 1\pmod{p}</math> .
Tekintsük a következő kongruenciarendszert:
 
:<math> b \equiv g \pmod{p}</math>
''b kongruens g mod p''
:<math> b \equiv 1 \pmod{m}</math>,
 
ahol ''m=n/p'', és ''g'' primitív gyök ''mod p''.
''b kongruens 1 mod m'',
 
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
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''
:<math> b^{n-1} \equiv g^{n-1} \pmod{p}</math>.
Ez teljesül, ha <math>p-1|n-1</math>, ugyanis ''g'' rendje ''p-1 mod p'', és éppen ez az állítás. Különben
:<math> b^{n-1}\not\equiv 1 \pmod{p}</math>, így
:<math> b^{p-1}\not\equiv 1 \pmod{n}</math>.
 
 
 
==Források==
73

szerkesztés