数学の力

京大生が数学の定理・公式の証明や入試問題の解説をするブログ.

ユークリッドの互除法


スポンサードリンク

ユークリッドの互除法

最大公約数の計算

ユークリッドの互除法とは, 2つの整数に対して, その最大公約数を計算するときに使う方法です.

 

最大公約数は, 通常は素因数分解を用いて次のように求めます.

 

例として, 2016 と 210 の最大公約数を考えます.

\begin{align*}
2016 &= 2^5 \times 3^2\times 7\\
210 &= 2\times 3\times5\times 7
\end{align*}

なので, 素因数の共通している部分を選んで, 最大公約数は  2\times 3\times 7 = 42 となります.

 

ところが, 大きな数については, 素因数分解をすることが容易ではないため, この方法は使えません.

 

互除法 を使うと素因数分解の必要はありません.プログラムで計算する際にも,最大公約数を求めるのにユークリッドの互除法を使うことが多いです.(Project Euler No.5)

 

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

例として, 上と同じ 2016 と 210 の最大公約数を求めてみます.

 

まず, 大きい方 (2016) を小さい方 (210) で割った余りを求めます.

\begin{align*}
2016 \div 210 = 9\cdots 126
\end{align*}

 

この計算の割る数を余りとして求まった数で割った余りを繰り返し求めていきます.

 

\begin{align*}
210 \div 126 &= 1\cdots 84\\
126 \div 84 &= 1\cdots 42\\
84 \div 42 &= 2\cdots 0
\end{align*}

 

余りが 0 になったときの割る数 (42) が最大公約数になっています.

 

互除法は正しいか

整数  M, N\, (M > N) の最大公約数が  G であったとすると, もちろん M, N G の倍数なので,  M-N G の倍数になります.

 

逆に,  M-N N の公約数は  M = (M-N) + N の約数にもなります.

 

このことから,  M, N の最大公約数は  N, M-N の最大公約数に一致します.

ユークリッドの互除法では, この操作をくり返しているだけなので, 正しいといえます.