Задачи

Пусть p – искомая степень. Согласно малой теореме Ферма 10^p ≡ 1 (mod (p + 1)). Тогда p = 12, то есть при делении числа 10¹² на 13 в остатке получается 1.

Осталось проверить, что для меньших степеней это сравнение не выполняется. Имеем:

101 ≡ 10 (mod 13)	105 ≡ 4 (mod 13)
102 ≡ 9 (mod 13)	106 ≡ 1 (mod 13)
103 ≡ 12 (mod 13)	…
104 ≡ 3 (mod 13)

Итак, в процессе проверки выяснилось, что существует меньшее, чем 12, натуральное число p = 6, для которого выполняется указанное в условии равенство. Это не противоречит теореме Ферма: она не запрещает существование других p, для которых выполняется указанное сравнение.

Правильный ответ: 6.