В какую наименьшую натуральную степень нужно возвести число 10, чтобы при делении на 13 оно дало в остатке единицу?
Решение.
Пусть p – искомая степень. Согласно малой теореме Ферма 10p ≡ 1 (mod (p + 1)). Тогда p = 12, то есть при делении числа 1012 на 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.
Задачи
4 из 4
