不定方程式のときかた

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

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

ユークリッドの互除法を使うと,
$33\cdot5+22\cdot(-7)=1$ 両辺を$3$倍すると,
$33\cdot15+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{cases} 3x+2y=-1 \\ 7x+5y=1 \end{cases}$を解くと, $(x{,}y)=(-7{,}10)$
よって, 解は$(x{,}y)=(22k-7{,}-31k+10)$

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

$31x+22y=3$ $22$を法とする.
$9x\equiv3\pmod{22}$
$9x\equiv3+2\cdot3\cdot22\pmod{22}$
$x\equiv15\pmod{22}$ あとは代入して整理して,
$(x{,}y)=(22k+15,-31k-21)$

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