Ezt hogy kéne megcsinálni? Kongruencia

Az utolsó két számjegy a 100-as maradékból derül ki, tehát

66^143 = x mod(100)

Jó lenne, hogyha lehetne használni az Euler-Fermat-tételt, csak az a baj, hogy a 66 és a 100 nem relatív prímek egymáshoz. Szóval ki kellene valamit találni, hogy lehessen használni.

Első körben alakítsuk át a jobb oldalt a tanultak szerint:

66^2 * 66^141 = x mod(100)

Ez azért jó, mert itt már tudunk 4-gyel osztani, így:

33^2 * 66^141 = x/4 mod(25)

Első körben foglalkozzunk a 33^2-nel, ezt még akár fejben is ki lehet számolni; 1089, így:

1089 * 66^141 = x/4 mod(25)

Tudjuk, hogy ha azonos maradékosztályba eső számokat összeszorzunk, akkor a maradékok is összeszorzódnak; például 3*5=15, ennek 4-es maradéka 3, viszont ha külön-külön vesszük a maradékokat, akkor 3-at és 1-et kapunk, ezek szorzatának 4-es maradéka szintén 3. Ennek fényében külön vizsgálhatjuk a szorzótényezőket;

1089 = 14 mod(25), ez majd később lesz jelentős.

Most nézzük a másik részt;

66^141 = ? mod(25)

Itt már jók vagyunk, mivel a 66 és a 25 relatív prímek. Azt biztosan tudjuk a tétel szerint, hogy

66^fi(25) = 1 mod(25), fi(25) értéke 20, tehát

66^20 = 1 mod(25). Ezt, valamint a korábbi állítást felhasználva:

66^20 * 66^20 * 66^20 * 66^20 * 66^20 * 66^20 * 66^20 * 66^1 = ? mod(25)

Mivel a 66^20-oknak a 25-ös maradéka 1, a maradékok pedig összeszorzódnak, ez lesz belőle:

1 * 1 * 1 * 1 * 1 * 1 * 1 * 66 = ? mod(25), ennek pedig a vége:

66 = 16 mod(25).

Térjünk vissza oda, hogy

1089 * 66^141 = x/4 mod(25)

Az 1089-ből 14 lett, a 66^141-ből 16, így

14 * 16 = x/4 mod(25), szorzás után

224 = x/4 mod(25), ebből

24 = x/4 mod(25), majd visszaszorozva a 4-gyel:

96 = x mod(100), tehát a szám százas maradéka, vagyis az utolsó két számjegye a 96.