次: 演習問題 上: 一次不定方程式 前: 部屋割り論法

解の発見法

解が存在することはわかった． しかし係数が大きいと一組見つけるのは大変だ． $3x+2y=1$ なら暗算でできる． しかし$127x+52y=1$となると， 一組見つけるのも暗算というわけにはいかない． ところが，ユークリッドの互除法を用いて一組の解を構成する一般的な方法がある．

$a$ と $b$ の最大公約数が1より大きいとき， $k$ が，$a$と$b$ の最大公約数の倍数でなければ解はない． $k$ が最大公約数の倍数なら全体をその最大公約数で割って， 初めから $a$ と $b$ の最大公約数は１，つまり $a$ と $b$ は互いに素であるとしてよい． このとき $ax+by=1$ に解が見つかれば $x$ と $y$ の各々に $k$ を乗じることにより， $ax+by=k$ の解ができる． 結局 $a$ と $b$ が互いに素なときに $ax+by=1$ の解が構成できれば よいことがわかる．

1. $a>b$ とし， $a=bq+r,(0 \le r <b)$ とする．
2. $ax+by=(bq+r)x+by=rx+b(qx+y)$ であるから， $y'=qx+y$とおくと方程式$ax+by=1$ は方程式$rx+by'=1$ となる．
3. $rx+by'=1$ の解 $(x_0,y'_0)$ が構成できれば， $y_0=y'_0-qx_0$によって定めた$(x_0,\ y_0)$が$ax+by=1$の解となる．

$a$ と $b$ が互いに素なら $b$ と $r$ も互いに素であるから，こうして係数のより小さい方程式が得られ，しかもその解からもとの方程式の解が構成できる．この過程を繰り返すと，最後は係数の一方は $1$ となる．

$sx+y=1$ または $x+ty=1$ の解として $(0,1)$ か $(1,0)$ をとれる． ここから逆に戻っていけば $ax+by=1$ の解が得られる．

この方法で $127x+52y=1$ の解を構成しよう． まず互除法で方程式を変換する．

1. $127x+52y=1$
2. $127=52 \cdot 2+23 \, , \, y'=2x+y \, , \, 23x+52y'=1$
3. $52=23 \cdot 2+6 \, , \, x'=x+2y' \, , \, 23x'+6y'=1$
4. $23=6 \cdot 3+5 \, , \, y''=3x'+y' \, , \, 5x'+6y''=1$
5. $6=5 \cdot 1+1 \, , \, x''=x'+y'' \, , \, 5x''+y''=1$

ここから逆に解を構成していく．

1. $(x'',y'')=(0,1)$
2. $x''=x'+y''$ より $(x',y'')=(-1,1)$
3. $y''=3x'+y'$ より $(x',y')=(-1,4)$
4. $x'=x+2y'$ より $(x,y')=(-9,4)$
5. $y'=2x+y$ より $(x,y)=(-9,22)$

確かに, $127 \cdot (-9) + 52 \cdot 22=-1143+1144=1$ である． これは二変数の不定方程式の解を構成する一般的な方法である．

注意 1        この方法はまた，解の存在の証明にもなっている． $a$と$b$が互いに素なら，上記のようにユークリッドの互除法をくりかえすことで， $5x''+y''=1$のように一方の係数が1の不定方程式が得られる． これは0と1の組みという整数解が存在し， これからもとの方程式の整数解の存在が示される．