2013 と 250 の最大公約数を求めてみる。
あわせて，
不定方程式 2013x + 250y = 1 の
互除法を利用した解法を説明する。
| n |
a | b |
q | r |
x | y |
| 1 |
2013 | 250 ① |
8 | 13 ② |
77 ⑧ | -620 ⑨ |
| 2 |
250 ① | 13 ② |
19 | 3 ③ |
-4 ⑦ | 77 ⑧ |
| 3 |
13 ② | 3 ③ |
4 | 1 ④ |
1 ⑥ | -4 ⑦ |
| 4 |
3 ③ | 1 ④ |
3 | 0 |
0 ⑤ | 1 ⑥ |
互除法
n = 1
2013 ÷ 250 = 8 余り 13
n = 2
250 ÷ 13 = 19 余り 3
n = 3
13 ÷ 3 = 4 余り 1
n = 4
3 ÷ 1 = 3 余り 0
したがって，
2013 と 250 の最大公約数は 1 … ④
不定方程式の解
n = 4
(x, y) = (0, 1) は 3x + y = 1 を満たす。
n = 3
13x + 3y = 1 の1つの解は x = 1 として，
3y = 1 - 13 より y = -4 … ⑦
n = 2
250x + 13y = 1 の1つの解は x = -4 として，
13y = 1 + 1000 より y = 77 … ⑧
n = 1
2013x + 250y = 1 の1つの解は x = 77 として，
250y = 1 - 155001 より y = -620 … ⑨
アルゴリズムなので，
このような表形式にしておくとよいのかも。
不定方程式を解く部分を，逆行表と呼ぶ人もいる。
根拠
命題
bx' + ry' = c, r = a-bq ならば
(x, y)=(y', x'-qy') は ax + by = c を満たす。
実際
bx' + ry' = c, r = a-bq
bx' + (a-bq)y' = c
ay' + b(x'-qy') = c
bx' + ry' = c
を満たすならば，
x = y' とすると，
ax + by = c となる 整数 y がある
くらいで覚えておくとよいのかも。