Задача 30599

Темы:    [ Деление с остатком ] [ Разложение на множители ] [ Принцип Дирихле (прочее) ] [ Разбиения на пары и группы; биекции ]

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

Условие

Докажите, что среди 51 целого числа найдутся два, квадраты которых дают одинаковые остатки при делении на 100.

Подсказка

Используйте тождество  x² – y² = (x – y)(x + y).

Решение

Разобьём все остатки от деления на 100 на 50 групп:  {1, 99},  {2, 98},  ...,  {49, 51},  {0, 50}.  Поскольку чисел больше 50, найдутся два числа x и y, остатки которых попадут в одну группу. Если это – одна из первых 49 групп, то либо  x – y,  либо  x + y  делится на 100. Если это последняя группа, то и  x – y  и
x + y  кратны 10. В любом случае  x² – y²  делится на 100.

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

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