Задача
NT-B1-M07-P020 Короткий цикл по модулю \(31\)
#20
★★★☆☆ Уровень 3 из 5
Найдите остаток \(2^{1000}\) по модулю \(31\).
Заметьте, что \(2^5\equiv1\pmod{31}\).
\(2^5=32\equiv1\pmod{31}\). Так как \(1000\) делится на \(5\), имеем \(2^{1000}=(2^5)^{200}\equiv1\pmod{31}\).
Сильная привычка: искать малый период до применения Ферма.