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

→‎Álprímek: 3. állítás bizonyításának elkezdése
(→‎Álprímek: tudom, nem a legjobb ez a bizonyítás, de majd keresek jobbat)
(→‎Álprímek: 3. állítás bizonyításának elkezdése)
''b_2^(-1)'' a redukált mod n maradékosztályok csoportján értendő.
 
3. Ha ''n'' csak egyetlen hozzá relatív prím ''bt'' -re is bukja a
Fermat-tesztet, akkor a redukált maradékosztályoknak legalább a felére
bukja.
2. Az kell, hogy az ilyen redukált maradékosztályok csoportot alkotnak. Ez így van, mert egyrészt ''(b_1)^d(b_2)^d=(b_1b_2)^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ét 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.
[[Kategória:Számelmélet]]