1次不定方程式

31x + 22y = 1 を満たす整数x, y の組を１つ求めます。

31x = 22・(-y) + 1 と変形します。
左辺は31の倍数です。右辺は22で割って余り1 の数です。
31の倍数のうち，22で割って1余る数を見つけます。
31・1 の余りは 9
31・2 の余りは 18
31・3 の余りは 5
31・4 の余りは 14
31・5 の余りは 1
したがって，x の １つは 5
また，y = (1 - 31×5) / 22 = -7
よって，(x, y) = (5, -7) が答えの1つです。

31x = 22・(-y) + 1 と変形します。
31x ≡ 1 (mod 22) を満たす 整数x を見つけます。
31・1 ≡ 9 (mod 22)
31・2 ≡ 18 (mod 22)
31・3 ≡ 5 (mod 22)
31・4 ≡ 14 (mod 22)
31・5 ≡ 1 (mod 22)
以下同じです。

定理
整数a, b, q, r で a = bq + r を満たしているとします。
bx' + ry' = 1を満たす整数 x', y' が見つかったら，
ax + by = 1 を満たす整数 x, y は
x = y', y= (1 - ax) / b

証明
整数 x', y' は bx' + ry' = 1を満たすとします。
bx' + (a - bq) y' = 1
すなわち，ay' + b(x' -qy') = 1
したがって，x = y', y= (1 - ax) / b とすれば，
ax + by = 1

例
互除法の表 a = bq + r

a	b	q	r	ax + by = 1	y = (1 - ax)/b
31	22	1	9	31×5 + 22×(-7) = 1	(1 - 31×5) / 22 = -7
22	9	2	4	22×(-2) + 9×5 = 1	(1 + 22×2) / 9 = 5
9	4	2	1	9×1 + 4×(-2) = 1	(1 - 9×1) / 4 = (-2)
4	1	4	0

同じことですが (ディオファントス計算器)
9 = 31 - 22×1 … ①
4 = 22 - 9×2 … ②
1 = 9 - 4×2 … ③
③ と ② より
1 = 9 - (22 - 9×2)×2 = 22×(-2) + 9×5
これと ① より
1 = 22×(-2) + (31 - 22×1)×5 = 31×5 + 22×(-7)