1次不定方程式 ax + by = c を解くための理論

定理
a, b, c を整数とする。
a を b で割った商を q, 余りを r とする。
bx' + ry' = c なる整数 x', y' があったとする。
このとき， 不定方程式 ax + by = c の解の1つは
x = y', y = x' - qy'である。

証明
bx' + ry' = c … ①
a = bq + r より r = a - bq … ②
① ② より bx' + (a - bq)y' = c
すなわち，ay' + b(x' - qy') = c
よって， x = y', y = x' -qy' とすれば，
x, y は整数で， ax + by = c を満たす。

45x + 32 y = 1 … ③ を満たす整数x, y を見つけたい。
45 ÷ 32 = 1 余り 13
32・(-2) + 13・5 = 1 だから
x = 5 は　③ の解で，このとき
45・5 + 32y = 1 を解いて， y = -7
③の解の1つは (x, y) = (5, -7)