Wikipédia

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

Laptörténet interaktív böngészése
[nem ellenőrzött változat][nem ellenőrzött változat]
← Régebbi szerkesztésÚjabb szerkesztés →
Tartalom törölve Tartalom hozzáadva
VizuálisWikiszöveges
a →‎Álprímek: indexek jav
14. sor:
 
==Álprímek==
b<sub>i</sub>
 
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.
29. sor:
maradékosztályok csoportjában ''b'' rendje osztója ''n-1'' -nek.
 
2. Legyen \''lnko(b_1b<sub>1</sub>,n)=lnko(b_2b<sub>2</sub>,n)=1''. Ha ''n'' álprím a \''b_1 b''<sub>1</sub> és a \''b_2b''<sub>2</sub> alapra
nézve, akkor álprím a \''b_1b_2b''<sub>1</sub>''b''<sub>2</sub>, és a \''b''<sub>1</sub>''b_1b_2b''<sub>2</sub><sup>-1</sup> alapokra is, ahol
''b_2b''<sub>2</sub><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
46. sor:
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_1b''<sub>1</sub>)<sup>''d''</sup>(b_2''b''<sub>2</sub>)<sup>''d''</sup>=(b_1b_2''b''<sub>1</sub>''b''<sub>2</sub>)<sup>''d''</sup>'' (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''b_1<b_2sub>1</sub><''b''<sub>2</sub>< ... <b_k''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''b_1<b_2sub>1</sub><''b''<sub>2</sub>< ... <b_k''b''<sub>''k''</sub> számokat, ezek páronként inkongruensek lesznek.
 
'''Állítás''' - ''n'' bukja a tesztet ezekre a \''tb''tb_1<tb_2sub>1</sub><''tb''<sub>2</sub>< ... <tb_k''tb''<sub>''k''</sub> számokra.
 
Tegyük fel indirekt, hogy \''tb_itb''<sub>''i''</sub> -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''<sub>''i''</sub>''b''<sub>''tb_ib_ii''</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==
A lap eredeti címe: „https://hu.wikipedia.org/wiki/Fermat-prímteszt”