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
Alexbot (vitalap | szerkesztései)
31 431 szerkesztés
a Bot: következő hozzáadása: nl:Fermattest
Peti610bot (vitalap | szerkesztései)
51 382 szerkesztés
a Bot: Átirányítások javítása
5. sor:
 
Meg kívánjuk vizsgálni, hogy ''n'' szám ''1''-nél nagyobb páratlan egész prím-e. Legyen
''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ámszámok|összetett]].
 
Ha ''n'' prím, akkor ''a''<sup>''n''-1</sup> kongruens ''1 mod n''. Ha nem így van, akkor ''n''
28. sor:
'''Tétel:'''
 
1. ''n'' [[csakkorbikondicionális|akkor és csak akkor]] álprím a ''b'' alapra, ha a ''mod n''
maradékosztályok csoportjában ''b'' rendje osztója ''n-1'' -nek.
 
54. sor:
'''Á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ékosztálymaradékrendszer|redukált maradékosztályok]]ok 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==
A lap eredeti címe: „https://hu.wikipedia.org/wiki/Fermat-prímteszt”