Find all integer solutions of 399x + 188y = 3570.

Step-by-step solution

1. 1

   Check solvability with the gcd. Integer solutions exist if and only if $\gcd(399,188)$ divides $3570$. Euclid's algorithm:

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

   so $\gcd(399,188)=1$, which divides everything. Solutions exist.

2. 2

   Reduce to a congruence. Working modulo $188$ kills the $y$ term:

   $399x\equiv3570\pmod{188}$

   Reducing both coefficients: $399-2(188)=23$, and $3570-18(188)=3570-3384=186$, so

   $23x\equiv186\pmod{188}$

3. 3

   Find the modular inverse of 23 by back-substitution. Reversing the Euclidean steps:

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

   Hence $-49\cdot23\equiv1\pmod{188}$, so the inverse is $-49\equiv139\pmod{188}$. Check: $23\times139=3197=17\times188+1$ ✓.

4. 4

   Multiply through — and do the final reduction carefully.

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

   Now $188\times137=25756$, and $25854-25756=98$, so

   $x\equiv98\pmod{188}$

   This is the step where errors creep in: a value of $18$ is sometimes quoted here, but $188\times137=25756$ leaves remainder $98$, not $18$.

5. 5

   Correct a widely repeated wrong answer. The pair $(x,y)=(18,-19)$ is often given as a particular solution, but substituting gives

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

   It is off by $40$. The genuine particular solution from $x=98$ is

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

   and $399(98)+188(-189)=39102-35532=3570$ ✓.

6. 6

   Write the general solution. Adding $188$ to $x$ and subtracting $399$ from $y$ leaves the left side unchanged, since $399\cdot188-188\cdot399=0$:

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

   For $k=-1$ this gives $(-90,210)$; for $k=-2$, $(-278,609)$.

7. 7

   Note there are no solutions in positive integers, then verify. From the general form, $x>0$ needs $k\ge0$, but then $y=-189-399k\le-189<0$. So $x$ and $y$ can never both be positive. Checking every $x$ from $1$ to $199$, none makes $\tfrac{3570-399x}{188}$ a positive integer ✓, and the general formula was confirmed to give exactly $3570$ for all $k$ from $-6$ to $6$ ✓.