ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 66530
Темы:    [ Разложение на множители ]
[ Признаки делимости (прочее) ]
[ Арифметика остатков (прочее) ]
Сложность: 3+
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Автор: Шноль Д.Э.

Найдите наименьшее натуральное число n, для которого n2 + 20n + 19 делится на 2019.

Решение

Первое решение. Заметим, что число 2019 представляется как 3 ċ 673, где числа 3 и 673 – простые, а выражение n2 + 20n + 19 представляется как (n + 19)(n + 1).

Хотя бы одно из чисел n + 19 или n + 1 должно делиться на 3. Но так как эти числа отличаются на 18, то они оба делятся на 3. Кроме того, какое-то из них должно делиться на 673. Значит, какое-то из этих чисел делится на 2019.

Наименьшее n, при котором это возможно – это 2000.

Второе решение. Запишем условие в виде сравнения: n2 + 20n + 19 ≡ 0 (mod 2019), откуда следует n2 + 20n + 19 ≡ 0 ⇔ n2 + 2n + 1 ≡ 0 ⇔ (n + 1)2 ≡ 0 (mod 3) и n2 + 20n + 19 ≡ 0 ⇔ (n + 1)(n + 19) ≡ 0 (mod 673). Первое сравнение имеет по модулю 3 единственное решение –1, второе по модулю 673 имеет два решения: –1 и –19. Учитывая, что числа 3 и 673 простые и –19 ≡ –1 (mod 3), получаем, что n ≡ –1 (mod 2019) или n ≡ –19 (mod 2019), откуда и следует ответ.

Ответ

2000.

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

олимпиада
Название Московская математическая олимпиада
год
Год 2019
Номер 82
класс
Класс 8
задача
Номер 2
олимпиада
Название Московская математическая олимпиада
год
Год 2019
Номер 82
класс
Класс 9
задача
Номер 2

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .