Задача 31263

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

Сложность: 3 Классы: 6,7,8

Условие

Доказать, что  3ⁿ + 1  не делится на 10100.

Подсказка

Оно не делится даже на 8.

Решение

3^2k + 1 = 9^k + 1 ≡ 1^k + 1 = 2 (mod 8).
3^2k+1 + 1 = 3·9^k + 1 ≡ 4 (mod 8).

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

книга
Автор	Иванов С.В.
Название	Математический кружок
глава
Номер	11
Название	Остатки
Тема	Деление с остатком
задача
Номер	33