Задача 30600

Темы:    [ Делимость чисел. Общие свойства ] [ Симметрия и инволютивные преобразования ]

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

Условие

Назовём натуральное число n удобным, если  n² + 1  делится на 1000001. Докажите, что среди чисел 1, 2, ..., 1000000 чётное число удобных.

Подсказка

Если n – удобное число, то и  1000001 – n  – также удобное.

Решение

(1000001 – n)² + 1 = 1000001(1000001 – 2n) + n² + 1.  Поэтому если n – удобное число, то и  1000001 – n  – также удобное. Осталось проверить, что число 500000 – неудобное. Действительно,  (5·10⁵)² + 1 = 25·10¹⁰ + 1 = 25·10⁴(10⁶ + 1) – (25·10⁴ – 1),  а второе слагаемое меньше  10⁶ + 1.

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

книга
Автор	Генкин С.А., Итенберг И.В., Фомин Д.В.
Год издания	1994
Название	Ленинградские математические кружки
Издательство	Киров: "АСА"
Издание	1
глава
Номер	10
Название	Делимость-2
Тема	Теория чисел. Делимость
задача
Номер	014