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

\((a_1, b_1)=(a,b)\) は \(a > b >0\) で互いに素とする。
\(a_{n}\)を\(b_{n}\)で割った商を\(q_n\), 余りを\(r_n\)として， \(a_{n+1}=b_n\),  \(b_{n+1}=r_n\) とおいて，
方程式の系列 \(a_{n}x_{n}-b_{n}y_{n}=1\) (n=1,2,3,…) をつくる。

定理
\(a_{n+1}x_{n+1}-b_{n+1}y_{n+1}=1\) なる \((x_{n+1},y_{n+1})\) があったとき，
\((x_n, y_n)=\left(-y_{n+1}, -(x_{n+1}+y_{n+1}q_n)\right)\) は， \(a_{n}x_{n}-b_{n}y_{n}=1\) を満たす。

a, b は互いに素だから， \(r_{n-1}=1\)となる n が存在する。
最後の方程式， \(a_{n}x_{n}-b_{n}y_{n}=1\) は \(b_{n-1}x_{n}-y_{n}=1\) だから，
\(x_n=0\), \(y_n=-1\) とおいて，逆算すればよい。