不定方程式のときかた

不定方程式を解く
$31x+22y=3$を満たす整数$(x,y)$を一般の整数$k$で表せ.

$(1)31x+22y=1$の解を求め, 両辺を$3$倍する

ユークリッドの互除法を使うと,
$33\cdot 5+22\cdot (-7)=1$ 両辺を$3$倍すると,
$33\cdot 15+22\cdot (-21)=1$
よって, $(x,y)=(22k+15,-31k-21)$

$(2)$ 連立方程式を立てる

$31x+22y=3$ $22$で括る
$9x+22\cdot (x+y)=3$ $9$で括る
$9\cdot (3x+2y)+4\cdot (x+y)=3$ $4$で括る
$1\cdot (3x+2y)+4\cdot (7x+5y)=3$
$m+4n=3$を満たす整数の組$(m,n)$を見つける(今回は$(-1,1)$)
$\{\begin{array}{l}3x+2y=-1\\ 7x+5y=1\end{array}$を解くと, $(x,y)=(-7,10)$
よって, 解は$(x,y)=(22k-7,-31k+10)$

$(3)$ 片方の係数を法として考える.

$31x+22y=3$ $22$を法とする.
$9x\equiv 3(\mathrm{mod}22)$
$9x\equiv 3+2\cdot 3\cdot 22(\mathrm{mod}22)$
$x\equiv 15(\mathrm{mod}22)$ あとは代入して整理して,
$(x,y)=(22k+15,-31k-21)$

今のところ, 実用的なものはこの$3$個です.
また新しく見つかったら更新します.