ユークリッドの互助法

ユークリッドの互除法を用いて、最大公約数を求めると
$$\begin{array}{rl}33976& =3\times 10001+3973\\ 10001& =2\times 3973+2055\\ 3973& =1\times 2055+1918\\ 2055& =1\times 1918+137\\ 1918& =14\times 137\end{array}$$
となり、$a,b$ の最大公約数は 137 であることが分かる。

さらに、第4式から順に1つずつ上の式を使うことによって
$$\begin{array}{rl}137& =2055–1\times 1918\\ & =2055–1\times (3973–1\times 2055)\\ & =2\times 2055–3973\\ & =2\times (10001–2\times 3973)–3973\\ & =2\times 10001–5\times 3973\\ & =2\times 10001-5\times (33976–3\times 10001)\\ & =17\times 10001–5\times 33976\end{array}$$
となり、$17a–5b=137$ が得られる。