Question

Найдите остаток каждого из чисел 5^17, 4^18, 3^19, 2^20 при делении на 19. В ответе укажите наибольший из остатков.

Answer 1

Формулировка малой теоремы Ферма:если р — простое число, то для любого натурального а разность а^(p)-а делится на р

Можно сформулировать так:

если р — простое число, то для любого натурального а, не делящегося на р, разность а^(р-1)-1 делится на р

Другими словами, если р — простое, то остаток от деления степени а^(р-1)-1 на р равен 1. 

19- простое число, тогда остаток от деления
5¹⁹⁻¹-1 делится на 19
или 5¹⁸-1 делится на 19, а 5¹⁸ при делении на 19 дает остаток 1.
Пусть 5¹⁷ при делении на 19 дает остаток k.
5¹⁷=19n+k
Чтобы получить из 5¹⁷ новое число 5¹⁸ надо 5¹⁷ умножить на 5,
5·5¹⁷=5·19n+5k,
5k при делении на 19 дает остаток 1,
значит 5k=20,
k=4

4¹⁹⁻¹-1 делится на 19, а 4¹⁸ при делении на 19 дает остаток 1.
3¹⁹⁻¹-1 делится на 19, а 3¹⁸ при делении на 19 дает остаток 1.
3¹⁸=19m+1
3¹⁹=3·3¹⁸=3·(19m+1)=3·19m+3  имеет остаток 3.

2¹⁹⁻¹-1 делится на 19, а 2¹⁸ при делении на 19 дает остаток 1.
2¹⁸=19s+1
2²⁰=2²·2¹⁸=2²·(19s+1)=4·19s+4 имеет остаток 4
Наибольший остаток 4.