Euler-fermat képlettel (vagy Kis-Fermattal) hogyan oldható meg ez a feladat?

Mivel az utolsó két számjegyre van szükséged, ezért mod(100) a kérdés. Nyilván ide a Kis Fermat-tétel nem lesz jó, mert akkor mod(p) kellene.

Az Euler-Fermat-tétel szerint 19^(phi(100)) = 1 mod(100). Meg kell nézni, hogy a 100-hoz hány relatív prím van. phi(100)=40, ami azt jelenti, hogy 19^40 = 1 mod(100), amiből következően 19^80 = 1 mod(100). Mivel nekünk 19^81 van, ezért 19-cel szorozva mindkét oldalt 19^81 = 19 mod(100)-at kapjuk, tehát a 19^81 utolsó két számjegye a 19.

Ellenőrzés:

[link]