Олимпиада имени Леонарда Эйлера 2022-2023 учебный год, II тур дистанционного этапа

Остаток от деления натурального числа $n$ на 2021 на 800 больше, чем остаток от деления числа $n$ на 2020. Найдите наименьшее такое $n$. ( А. Голованов )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.    
Ответ. $2020\cdot 1221 = 2 \ 466 \ 420$.
Решение. Пусть для натурального числа $m$ выполнено условие задачи. Тогда для некоторых $d_1$, $d_2$, $d_3$ и $r$ выполнено равенство $m = 2020d_1+r = 2021d_2+r+800$. Но в этом случае выполнено и равенство $m-r = 2020d_1 = 2021d_2 +800$, так что число $m-r$ тоже удовлетворяет условию задачи. Значит, искомое наименьшее число $n$ делится на 2020, а при делении на 2021 дает остаток 800.
Заметим, что $2020d = 2021d-d = 2021(d-1)+(2021-d)$. Из этого следует, что число $2020d$ при $d \le 2021$ дает при делении на 2021 остаток $2021-d$. С ростом $d$ этот остаток убывает, становясь равным 800 при $d = 1221$. Поэтому наименьшее число, кратное 2020, которое при делении на 2021 дает остаток 800, равно $2020\cdot 1221$.

Сделаем два уравнения $n$=2021$k$+800+$x$ $n$=2020$m$+$x$ получим

2021$k$+800=2020$m$ $\Rightarrow$ $НОД$(2020;800)=20 $\Rightarrow$ $k$=20$h$

40420$h$+800=2020$m$ сократим на 20 2021$h$+40=101$m$ Заметим что

$2021 \equiv 1 \pmod {101}$ откуда $h$$\geq$61 $\Rightarrow$ $n$$\geq$2466420+x

Подставив минимальный $x$=0 Нетрудно убедится что $n$=2466420 подходит