37x+10y = 1 を拡張されたユークリッドの互除法で解いてみる

37と10は違いに素なので、 $37x_0 + 10y_0 = 1$ は整数解(x, y)を持ちます。
この解を求める方法を拡張されたユークリッドの互除法と呼ぶようです。
具体的には、 $ax + by = 1$ の形でaをbで割った余りをaに置き換える操作を余りが0になるまで繰り返します。
$37x_0 + 10y_0 = 1$
$x_0 ( 3 \cdot 10 + 7) + 10 y_0 = 1$
$10 (3 x_0 + y_0) + 7 x_0 = 1$
$x_1 = 3 x_0 + y_0, y_1 = x_0$ とおきます。
$10 x_1 + 7 y_1 = 1$
$x_1 (7 + 3) + 7 y_1 = 1$
$7 (x_1 + y_1) + 3 x_1 = 1$
$x_2 = x_1 + y_1, y_2 = x_1$ とおきます。
$7 x_2 + 3 y_2 = 1$
$x_2 (3 \cdot 2 + 1) + 3 y_2 = 1$
$3 ( 2 x_2 + y_2) + x_2 = 1$
$x_3 = 2 x_2 + y_2, y_3 = x_2$ とおきます。
$3 x_3 + y_3 = 1$
$y_2$ 側の係数が1になったらこの繰り返しは終了します。
なぜなら、解の一つが $x_3 = 0, y_3 = 1$ と簡単に分かるからです。
これを逆に辿っていって $x_0, y_0$ が求まります。
$x_2 = 1, y_2 = x_3 - 2 x_2 = -2$
$x_1 = y_2 = -2, y_1 = x_2 - x_1 = 3$
$x_0 = y_1 = 3, y_0 = x_1 - 3 x_0 = -11$