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

Формулировка малой теоремы Ферма: если р - простое число, то для любого натурального а разность а^ (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.