Олимпиадная задача по теории чисел про удобные числа и делимость
Нет ответа
Задача
Назовём натуральное число n удобным, если n² + 1 делится на 1000001. Докажите, что среди чисел 1, 2, ..., 1000000 чётное число удобных.
Решение
(1000001 – n)² + 1 = 1000001(1000001 – 2n) + n² + 1. Поэтому если n – удобное число, то и 1000001 – n – также удобное. Осталось проверить, что число 500000 – неудобное. Действительно, (5·105)² + 1 = 25·1010 + 1 = 25·104(106 + 1) – (25·104 – 1), а второе слагаемое меньше 106 + 1.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
Комментариев нет