Китайская теорема об остатках

Первое решение.

Разложив делимое и делитель на множители, получаем условие . Значит, одно из чисел или делится на 89 . Рассмотрим два случая.

a) , т.е. . Тогда получаем . Первый множитель делится на 5 при , а второй — при , откуда получаем, что .

б) , т.е. . Тогда получаем . Первый множитель делится на 5 при , а второй — при , откуда получаем, что , .

Итак, условию задачи удовлетворяют числа, дающие остатки при делении на 445, то есть подходят каждые 4 из 445 подряд идущих чисел. Так как , получаем чисел.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение.

. . Числа 5 и 89 простые, поэтому существует 4 случая:

Для каждого такого случая существует ровно одно решение по модулю (по КТО), так как если бы существовала и для, например, третьего случая, то и значит, и делится на 445, то есть .

Отсюда все числа от 1 до 445000 разбиваются на группы по 445 в каждой, из которых есть ровно 4 решения.