a, b は整数で，互いに素であるとする。
a > b > 0 とする。
1次不定方程式 ax+by=1 を互除法を活用して解いてみる。

(a₁, b₁) = (a, b) とおく。
a_n を b_n で割った商を q_n, 余りを r_n とする。
(a_n+1, b_n+1) = (b_n, r_n) とおいて，
逐次的に割り算を実行する。(互除法)
互いに素だから，r_n-1 = 1 となる n が存在する。
方程式の系列 a_nx_n + b_ny_n = 1 (n=1,2,3,…) をつくる。

定理
a_k+1x_k+1 + b_k+1y_k+1 = 1 を満たす (x_k+1, y_k+1) があったとき
(x_k, y_k) = (y_k+1, x_k+1 - q_ky_k+1) は
a_kx_k + b_ky_k = 1 を満たす。

a, b は互いに素だから， r_n-1 = 1 となる n が存在する。
最後の方程式， a_nx_n + b_ny_n = 1 は
b_n-1x_n + y_n = 1 だから，
自明な解 (x_n, y_n) = (0, 1) から，逆算すればよい。