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

→‎Álprímek: 1. bionyításának folytatása
(→‎Álprímek: A Carmichael-számok karakterizációja)
(→‎Álprímek: 1. bionyításának folytatása)
 
1. Ha ''b d'' rendje osztója ''n-1'' -nek, akkor ''b^(n-1)kongruens 1 mod n'', mert akkor ''n-1=kd'' valamely egész ''k'' -ra, így ''b^(n-1)=b^(kd)=(b^d)^k kongruens 1^k=1 mod n''.
 
Vizsgáljuk most a redukált ''mod n'' maradékosztályokat. Ha ebben a csoportban valamely elemre igaz az, hogy ''a^n-1'' kongruens ''1 mod n'', és egy másik ''k'' kitevőre is kongruens ''1 mod n'', akkor ''a^n-1-k'' kongruens ''1 mod n'' is teljesül. Így le lehet folytatni az euklidészi algoritmust, és kiderül, hogy ''d=lnko(n-1,k)'' -ra is igaz, hogy ''a^d'' kongruens ''1 mod n''. Tehát van egy ''d'' osztója ''n-1'' -nek, amire a kongruencia teljesül.
 
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''