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

a
→‎Menete: link jav
a (→‎Menete: link jav)
 
Legyen a tesztelendő ''n'' szám ''1''-nél nagyobb páratlan egész, és 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ám|összetett]].
prímek]]. Ha nem azok, akkor ''n'' bukja a tesztet, [[összetett szám|összetett]].
 
Ha ''n'' prím, akkor ''a^(n-1)'' kongruens ''1 mod n''. Ha nem így van, akkor ''n''