Задача 60689

Тема:    [ Арифметика остатков (прочее) ]

Сложность: 3+ Классы: 8,9,10

Условие

Найдите остатки от деления числа 2²⁰⁰¹ на 3, 5, 7, 9, 11, 13, 15, 17.

Решение

2³ ≡ – 1 (mod 9),  значит,  2²⁰⁰¹ = (2³)⁶⁶⁷ ≡ –1 (mod 9).
2⁴ ≡ 1 (mod 15),  значит,  2²⁰⁰¹ = 2·(2⁴)⁵⁰⁰ ≡ 2 (mod 15).
2³ ≡ 1 (mod 7),  значит,  2²⁰⁰¹ = (2³)⁶⁶⁷ ≡ 1 (mod 7).
2⁵ ≡ –1 (mod 11),  значит,  2²⁰⁰¹ = 2·(2⁵)⁴⁰⁰ ≡ 2 (mod 11).
2⁶ ≡ –1 (mod 13),  значит,  2²⁰⁰¹ = 8·(2⁶)³³³ ≡ 5 (mod 13).
2⁴ ≡ –1 (mod 17),  значит,  2²⁰⁰¹ = 2·(2⁴)⁵⁰⁰ ≡ 2 (mod 17).

Ответ

2, 2, 1, 8, 2, 5, 2, 2.

Источники и прецеденты использования

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	4
Название	Арифметика остатков
Тема	Деление с остатком. Арифметика остатков
параграф
Номер	3
Название	Сравнения
Тема	Деление с остатком. Арифметика остатков
задача
Номер	04.063