Найдите все целые решения уравнения 399x + 188y = 3570.

Step-by-step solution

1. 1

   Проверим существование решений через НОД. Целые решения существуют тогда и только тогда, когда $\gcd(399,188)$ делит $3570$. Алгоритм Евклида:

   $399=2\cdot188+23,\quad 188=8\cdot23+4,\quad 23=5\cdot4+3,\quad 4=1\cdot3+1,\quad 3=3\cdot1+0$

   Значит, $\gcd(399,188)=1$, а единица делит любое число. Следовательно, решения существуют.

2. 2

   Сведём к сравнению по модулю. Рассмотрим уравнение по модулю $188$ — тогда слагаемое с $y$ исчезает:

   $399x\equiv3570\pmod{188}$

   Упростим коэффициенты: $399-2(188)=23$, $3570-18(188)=3570-3384=186$, получаем

   $23x\equiv186\pmod{188}$

3. 3

   Найдём обратный элемент к 23 по модулю 188 методом обратного хода. Восстановим шаги алгоритма Евклида:

   $1=4-3=4-(23-5\cdot4)=6\cdot4-23=6(188-8\cdot23)-23=6\cdot188-49\cdot23$

   Значит, $-49\cdot23\equiv1\pmod{188}$, то есть обратный элемент — $-49\equiv139\pmod{188}$. Проверим: $23\times139=3197=17\times188+1$ — всё верно.

4. 4

   Умножим обе части — аккуратно выполним приведение по модулю.

   $x\equiv186\times139=25854\pmod{188}$

   $188\times137=25756$, $25854-25756=98$, значит

   $x\equiv98\pmod{188}$

   На этом этапе часто ошибаются: иногда приводят $x=18$, но $188\times137=25756$, остаток $98$, а не $18$.

5. 5

   Опровергнем часто встречающуюся ошибку. Пара $(x,y)=(18,-19)$ часто приводится как частное решение, но подставим:

   $399(18)+188(-19)=7182-3572=3610\neq3570$

   Ошибка в $40$. Истинное частное решение при $x=98$:

   $188y=3570-399(98)=3570-39102=-35532\quad\Longrightarrow\quad y=-189$

   Проверим: $399(98)+188(-189)=39102-35532=3570$ — всё верно.

6. 6

   Запишем общее решение. Прибавление $188$ к $x$ и вычитание $399$ из $y$ не изменяет левую часть, так как $399\cdot188-188\cdot399=0$:

   $x=98+188k,\qquad y=-189-399k,\qquad k\in\mathbb{Z}$

   Для $k=-1$ получаем $(-90,210)$; для $k=-2$ — $(-278,609)$.

7. 7

   Покажем, что решений в положительных целых нет, и проверим. Из общей формулы $x>0$ только при $k\ge0$, но тогда $y=-189-399k\le-189<0$. Значит, $x$ и $y$ не могут быть одновременно положительными. Проверка для всех $x$ от $1$ до $199$ показывает, что $\tfrac{3570-399x}{188}$ не даёт положительных целых ✓, а подстановка значений $k$ от $-6$ до $6$ подтверждает формулу ✓.