ユークリッドの互除法と1次不定方程式

32 と 15 の最大公約数を求めてみる。
あわせて, 不定方程式 32x - 15y = 1 の 互除法を利用した解法を説明する。
n ab qr xy
1 3215 ① 22 ② -7 ⑥ 15 ⑦
2 15 ①2 ② 71 ③ 1 ⑤-7 ⑥
3 2 ②1 ③ 20 0 ④1 ⑤

互除法

n = 1  32 ÷ 15 = 2 余り 2
n = 2  15 ÷ 2 = 7 余り 1
n = 3  2 ÷ 1 = 2 余り 0
したがって,
32 と 15 の最大公約数は 1 … ③

不定方程式の解
n = 3

(x, y) = (0, 1) は 2x + y = 1 を満たす。
n = 2
15x + 2y = 1 の1つの解は x = 1 として,
2y = 1 - 15 より y = -7 … ⑥
n = 1
32x + 15y = 1 の1つの解は x = -7 として,
15y = 1 + 224 より y = 15 … ⑦

32x - 15y = 1 の1つの解は (x, y) = (-7, -15)
自然数なら代表は (x, y) = (8, 17) だろうか。

アルゴリズムなので,
このような表形式にしておくとよいのかも。
不定方程式を解く部分を,逆行表と呼ぶ人もいる。