Mivel kongruens 4^53 mod 107?

Írjuk át a hatványt;

4^53 = (2^2)^53 = 2^106.

Ha ezt megszorzod 2-vel, akkor 2^107-nt kapjuk. Azt gondolom tudod, hogy a maradékok ciklikusan követik egymást, hogyha önmagával szorozgatjuk a számokat. Ennek megfelelően a 2^107 107-es maradéka megegyeik 2^0 107-es maradékával, ami 1.

Másik lehetőség hogy használod a kis Fermat-tételt;

[link]

Ehhez persze meg kell szorozni a 2^106 hatványt 2-vel, ekkor 2^107 hatványt kapod a tétel alapján

2^107 kongruens 2 mod(107), 2-vel osztás után:

2^106 kongruens 1 mod(107)

Tehát 1 lesz a 107-es maradék.

Most nézem, hogy az első részt elírtam... Nem is kicsit.

Nem vettem figyelembe, hogy ha n-nel nézzük a maradékot, akkor a ciklus hossza nem legfeljebb n, hanem n-1. Ennek megfelelően a 0. kitevőtől indított ciklus a 105. kitevőnél ér véget, és a 106. kitevővel indul újra. Így a 2^106 hatvány 107-es maradéka fog a 2^0-éval megegyezni, ami 1.