# 一次不定方程式の整数解　拡張されたユークリッドの互除法

1. （#）が整数解をもつ. $$\, \Longleftrightarrow \,$$ $$c$$ は $$d$$ の倍数である.
2. （#） が整数解をもつとき, その整数解が１つ得られれば, 全ての整数解が得られる.
したがって, （#）の整数解について知りたい場合, 以下のことを行います.
1. $$a$$ と $$b$$ の最大公約数 $$d$$ を求める. （これにより, 整数解をもつかどうか分かる.）
2. 整数解をもつときには, $ax + by = d$ の整数解を１つ見付ける. （これにより, （#）の整数解も１つ見付かり, それ故, 全ての整数解が見付かる.）

この２つのステップを同時に行う方法があり, それは, 「拡張されたユークリッドの互除法」と呼ばれています. １つ例を計算してみます:

$73 x + 54 y = 2. \tag{##}$

１．ここから始めます.

 $$73 \,x$$ $$+$$ $$54 \, y$$ $$1$$ $$0$$ $$0$$ $$1$$ $$\quad 73 \div 54$$ $$=$$ $$1$$ $$\cdots \, 19$$

２．最下段の 0, 1 に対して, 右側の商を掛け, 上側の数を足すという計算を行います.

 $$73 \, x$$ $$+$$ $$54 \, y$$ $$1$$ $$0$$ $$0$$ $$1$$ $$\quad 73 \div 54$$ $$=$$ $$1$$ $$\cdots \, 19$$ $$1$$ $$1$$ $$\quad 54 \div 19$$ $$=$$ $$2$$ $$\cdots \, 16$$

３．同様の計算を繰り返して, 互除法の余りが 0 になったら, 終了します.

 $$73 \, x$$ $$+$$ $$54 \, y$$ $$1$$ $$0$$ $$0$$ $$1$$ $$\quad 73 \div 54$$ $$=$$ $$1$$ $$\cdots \, 19$$ $$1$$ $$1$$ $$\quad 54 \div 19$$ $$=$$ $$2$$ $$\cdots \, 16$$ $$2$$ $$3$$ $$\quad 19 \div 16$$ $$=$$ $$1$$ $$\cdots \, 3$$ $$3$$ $$4$$ $$\quad 16 \div 3$$ $$=$$ $$5$$ $$\cdots \,$$$$\, 1$$ $$17$$ $$23$$ $$\quad 3 \div 1$$ $$=$$ $$3$$ $$\cdots \, 0$$

４．符号を次のように交互に入れます.

 $$73 \, x$$ $$+$$ $$54 \, y$$ $$+$$ $$1$$ $$0$$ $$-$$ $$0$$ $$1$$ $$\quad 73 \div 54$$ $$=$$ $$1$$ $$\cdots \, 19$$ $$+$$ $$1$$ $$1$$ $$\quad 54 \div 19$$ $$=$$ $$2$$ $$\cdots \, 16$$ $$-$$ $$2$$ $$3$$ $$\quad 19 \div 16$$ $$=$$ $$1$$ $$\cdots \, 3$$ $$+$$ $$3$$ $$4$$ $$\quad 16 \div 3$$ $$=$$ $$5$$ $$\cdots \, 1$$ $$-$$ $$17$$ $$+$$ $$23$$ $$\quad 3 \div 1$$ $$=$$ $$3$$ $$\cdots \, 0$$

これで, 方程式

$73 x + 54 y = 1$

の整数解 (-17, 23) が得られました. 2 倍すると (##) の整数解 (-34, 46) が得られます.

 $$23$$ $$+$$ $$1$$ $$17$$ $$-$$ $$2$$ $$6$$ $$+$$ $$1$$ $$5$$ $$-$$ $$5$$ $$1$$ $$+$$ $$0$$