ユークリッドの互除法

ユークリッドの互除法とは？

ユークリッドの互除法は、2つの数の最大公約数を求めるときに使います。まずは実際のどんな方法で最大公約数を求めるか、試してみましょう。ここで、\( 3355 \) と \( 2379 \) の最大公約数を求めてみます。

\begin{array}{lllllll}
割られる数 & \div & 法 & = & 商 & \cdots & 余り \\
3355 & \div & 2378 & = & 1 & \cdots & 976 \\
2378 & \div & 976 & = & 2 & \cdots & 427 \\
976 & \div & 427 & = & 2 & \cdots & 122 \\
427 & \div & 122 & = & 3 & \cdots & 61 \\
122 & \div & 61 & = & 2
\end{array}
よって最大公約数は\( 61 \) です。

このように、2つの数のうち、
①　大きい数字を小さい数字で割る
②　①の法（割る数）を余りで割る
③　②の法（割る数）を余りで割る
…
と割り切れるまで続けます。最後に割り切れた時の割る数が最大公約数となります。これが「ユークリッドの互除法」です。

ユークリッドの互除法を整数問題で利用

ユークリッドの互除法は最大公約数を求めるだけでなく、整数問題で解を見つける手段としても利用されます。例えば、以下の問を考えます。

上記であれば、すぐに \( x=-1, \ y= 1 \) など思いつきます。次はどうでしょうか？

すぐには思いつきません。互除法を使うと求めることができます。
\begin{array}{lll}
11 \div 8 = 1 \cdots 3 & \to & 3 = 11 – 8 \times 1 \cdots ① \\
8 \div 3 = 2 \cdots 2 & \to & 2 = 8 – 3 \times 2 \cdots ② \\
3 \div 2 = 1 \cdots 1 & \to & 1 = 3 – 2 \times 1 \cdots ③
\end{array}
割られる数（法）を余りで割った式を、余りについて整理した右の式を順に代入していくと、
\begin{array}{lll}
1 & = & 3 – 2 \times 1 \\
& = & 3 – ( 8 – 3 \times 2 ) \times 1 & （∵②を代入） \\
& = & 3 \times 3 – 1 \times 8 \\
& = & 3 \times ( 11 – 8 \times 1 ) – 1 \times 8 & （∵①を代入） \\
& = & 3 \times 11 – 4 \times 8
\end{array}
となり、\( 11 \cdot 3 + 8 \cdot (-4) = 1 \) となるため、\(x=3, \ y=-4 \) が答えとなる。

このように

といった問題では、ユークリッドの互除法で計算できます。闇雲に数字を当てはめる必要がありません。とても便利です。