整数 $a = 10001$ と $b = 33976$ の最大公約数 $d$ を求めよ。
また、$d = x a + y b$ となる $x, y \in \mathbb{Z}$ を一組求めよ。
ユークリッドの互除法を用いて、最大公約数を求めると
\begin{align}
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{align}
となり、$a, b$ の最大公約数は 137 であることが分かる。
さらに、第4式から順に1つずつ上の式を使うことによって
\begin{align}
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{align}
となり、$17 a – 5 b = 137$ が得られる。
