32 と 15 の最大公約数を求めてみる。
あわせて,
不定方程式 32x - 15y = 1 の
互除法を利用した解法を説明する。
n |
a | b |
q | r |
x | y |
1 |
32 | 15 ① |
2 | 2 ② |
-7 ⑥ | 15 ⑦ |
2 |
15 ① | 2 ② |
7 | 1 ③ |
1 ⑤ | -7 ⑥ |
3 |
2 ② | 1 ③ |
2 | 0 |
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) だろうか。
アルゴリズムなので,
このような表形式にしておくとよいのかも。
不定方程式を解く部分を,逆行表と呼ぶ人もいる。