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 の逆元を逆代入で求める。 互除法の各段階を逆にたどると：

   $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$を引いた余りは$18$ではなく$98$である。

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

   一般解を書き下す。 $399\cdot188-188\cdot399=0$なので、$x$に$188$を足し$y$から$399$を引いても左辺は変わらない：

   $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}$が正の整数になるものは1つもなく ✓、また$k$が$-6$から$6$までのすべてで一般式がちょうど$3570$を与えることも確認できる ✓。