NT-B1-M10-P019 Делимость на \(31\)

Найдите порядок \(10\) по модулю \(31\).

Так как \(31\) взаимно просто с \(9\), условие \(31\mid R_n\) эквивалентно \(10^n\equiv1\pmod{31}\). Вычисления дают \(10^5\equiv25\), \(10^{15}\equiv1\pmod{31}\), и меньшие делители \(1,3,5\) числа \(15\) не дают \(1\). Поэтому порядок равен \(15\), а значит \(31\mid R_n\) тогда и только тогда, когда \(15\mid n\).

Задача заставляет проверять не только найденную степень, но и минимальность.