求 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$，而 $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 的模逆元。 把欧几里得算法的步骤倒着走：

   $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}$

   错误常常就是从这一步溜进来的：有人在这里写成 $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

   写出通解。 给 $x$ 加上 $188$、同时给 $y$ 减去 $399$，左端的值不变，因为 $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$ 逐一代入通解，结果都恰好是 $3570$ ✓。