% 例題A4.2.5：方程式の整数解3 （One More）★★★
不定方程式$61 x+23 y=1$の整数解をすべて求めよ.
% 解答（例題A4.2.5）
不定方程式$61 x+23 y=1 \cdots (\mathrm{i})$の係数である61と23について,ユークリッドの互除法を用いる.$$\begin{array}{ll} 61=23 \times 2+15 \text{ より,} & 61-23 \times 2=15 \cdots (\mathrm{ii})\\ 23=15 \times 1+8 \text{ より,} & 23-15 \times 1=8 \cdots (\mathrm{iii})\\ 15=8 \times 1+7 \text{ より,} & 15-8 \times 1=7 \cdots (\mathrm{iv})\\ 8=7 \times 1+1 \text{ より,} & 8-7 \times 1=1 \cdots (\mathrm{v}) \end{array}$$(v)に(iv)を代入すると,$8-(15-8 \times 1)\times 1=1$より,$$8\times 2-15\times 1=1$$これに(iii)を代入すると,$(23-15 \times 1)\times 2-15\times 1=1$より,$$23\times 2-15\times 3=1$$これに(ii)を代入すると,$23\times 2-(61-23 \times 2)\times 3=1$より,$$61\times(-3)+23\times 8=1 \cdots (\mathrm{vi})$$したがって,$x=-3,y=8$は不定方程式$61 x+23 y=1$を満たす整数解の1つである.$(\mathrm{i})-(\mathrm{vi})$より,$61(x+3)+23(y-8)=0$ゆえに,$$61(x+3)=23(8-y) \cdots (\mathrm{vii})$$61と23は互いに素であるから,$x+3$は23の倍数となり,$k$を整数とすると,$x+3=23 k$,すなわち,$x=23 k-3$これを(vii)に代入すると,$61 \times 23 k=23(8-y)$$61 k=8-y$より,$y=-61 k+8$よって,求める一般解は,$x=23 k-3,y=-61 k+8(k \text{ は整数})$
% 問題A4.2.5
不定方程式$47 x+19 y=1$の整数解をすべて求めよ.
% 解答A4.2.5
不定方程式$47 x+19 y=1 \cdots (\mathrm{i})$の係数である47と19について,ユークリッドの互除法を用いる.$$\begin{array}{ll} 47=19 \times 2+9 \text{ より,} & 47-19 \times 2=9 \cdots (\mathrm{ii})\\ 19=9 \times 2+1 \text{ より,} & 19-9 \times 2=1 \cdots (\mathrm{iii}) \end{array}$$(iii)に(ii)を代入すると,$19-(47-19 \times 2)\times 2=1$より,$$-47 \times 2+19 \times 5=1 \cdots (\mathrm{iv})$$したがって,$x=-2,y=5$は不定方程式$47 x+19 y=1$を満たす整数解の1つである.$(\mathrm{i})-(\mathrm{iv})$より,$47(x+2)+19(y-5)=0$ゆえに,$47(x+2)=19(5-y) \cdots (\mathrm{v})$47と19は互いに素であるから,$x+2$は19の倍数となり,$k$を整数とすると,$x+2=19 k$,すなわち,$x=19 k-2$これを(v)に代入すると,$47 \times 19 k=19(5-y)$$47 k=5-y$より,$y=-47 k+5$よって,求める一般解は,$x=19 k-2,y=-47 k+5(k \text{ は整数})$
