Задача
NT-B2-M04-P012 Эйлер или CRT
#12
★★★★☆ Уровень 4 из 5
Найдите остаток \(7^{222}\) при делении на \(100\).
Можно использовать \(\varphi(100)=40\), но короткий цикл ещё лучше.
Заметим, что \(7^4\equiv1\pmod{100}\). Так как \(222\equiv2\pmod4\), получаем \(7^{222}\equiv7^2=49\pmod{100}\).
Хорошо обсудить, что Эйлер даёт допустимое, но не всегда кратчайшее сокращение.