【数学A】例題4.2.5：方程式の整数解3（One More）★★★

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 例題A4.2.5：方程式の整数解3（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

不定方程式$61x+23y=1$の整数解をすべて求めよ．

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 例題A4.2.5の解答（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

不定方程式$61x+23y=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$は不定方程式$61x+23y=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=23k$，すなわち，$x=23k-3$

これを(vii)に代入すると，$61\times 23k=23(8-y)$

$61k=8-y$より，$y=-61k+8$

よって，求める一般解は，$x=23k-3,y=-61k+8(k\text{は整数})$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 問題A4.2.5：方程式の整数解3（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

不定方程式$47x+19y=1$の整数解をすべて求めよ．

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 問題A4.2.5の解答（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

不定方程式$47x+19y=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$は不定方程式$47x+19y=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=19k$，すなわち，$x=19k-2$

これを(v)に代入すると，$47\times 19k=19(5-y)$

$47k=5-y$より，$y=-47k+5$

よって，求める一般解は，$x=19k-2,y=-47k+5(k\text{は整数})$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 例題A4.2.5の側注：方程式の整数解3（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% 側注1
$7=15-8\times 1$

% 側注2
$8=23-15\times 1$

% 側注3
$15=61-23\times 2$

% 側注4
$x=-3,y=8$が特殊解の1つである．

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 問題A4.2.5の側注：方程式の整数解3（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% 側注1
$9=47-19\times 2$

% 側注2
$x=-2,y=5$が特殊解の1つである．

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 例題A4.2.5の考え方・補足など：方程式の整数解3（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 考え方
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

特殊解を求めたいが，係数が大きいので$x,y$に値を代入して探すと手間が掛かる．そこで，方程式の係数である61と23について，ユークリッドの互除法を用いて，特殊解を見つけるとよい．