Benutzer:Abrankov/Lucas Test/Beispiel

Wir wollen zeigen, dass ${}n=61$ prim ist. Wegen ${}n-1=60=2^{2}\cdot 3\cdot 5$ folgt dies aus

${}2^{\frac {60}{2}}=2^{30}=(2^{6})^{5}=64^{5}\equiv 3^{5}\equiv 60\not \equiv 1\mod 61$,

${}2^{\frac {60}{3}}=2^{20}=(2^{6})^{3}\cdot 2^{2}={64}^{3}\cdot 2^{2}\equiv 3^{3}\cdot 4\equiv 47\not \equiv 1\mod 61$,

${}2^{\frac {60}{5}}=2^{12}=(2^{6})^{2}=64^{2}\equiv 3^{2}\equiv 9\not \equiv 1\mod 61$.