最大公約数の求め方(ユークリッドの互除法)

POINT

  • 整数の最大公約数の求め方.
  • 繰り返し2数の割り算を計算することで,最大公約数がわかる.

整数$a$と$b$の最大公約数を求める方法に「ユークリッドの互除法」と呼ばれる方法があります.

名前は難しそうですが,やっていることはとても簡単です.実際,英語では "Euclidean algorithm" (ユークリッドの方法くらいの意味)です.


次のような応用ができます:

  • 分母・分子が大きい数の分数の約分を行う.
  • これ以上分数の約分ができないこと(=分母と分子の最大公約数が1であること)を示す.


まずは図で理解するとわかりやすいでしょう:

手順

整数$a_1$と$a_2$を考えます.マイナスの整数の約数の場合は符号を除いて考えるので,$a_1 \geq a_2 > 0$の場合を考察すれば十分です.

このとき
\begin{align}
& a_1\text{と}a_2\text{の最大公約数} \\
=&\, a_2\text{と「} a_1\div a_2 \text{の余り}a_3\text{」の最大公約数} \\
=&\, a_3\text{と「} a_2\div a_3 \text{の余り}a_4\text{」の最大公約数} \\
=&\, \cdots
\end{align}であることが示せます(次節).割り算において,(割る数)>(余り)であることに注意すれば
\begin{align}
a_1 \geq a_2 > a_3 > \cdots \geq 0
\end{align}ですが,$a_1,a_2,a_3,...$は全て整数なので,ある$N$で$a_N=0$となります.


これは「$a_{N-2}$と$a_{N-1}$の最大公約数」が$a_{N-1}$であることを意味しています($a_{N-2}\div a_{N-1}$の余り=$a_N=0$).したがって
\begin{align}
& a_1\text{と}a_2\text{の最大公約数} \\
=&\, \cdots \\
=&\, a_{N-2}\text{と「} a_{N-3}\div a_{N-2} \text{の余り}a_{N-1}\text{」の最大公約数} \\
=&\, a_{N-1}
\end{align}となり,$a_1$と$a_2$の最大公約数を求めることができます.

証明

整数$a$と$b$を考えます($a \geq b>0$).以下を示せば,上の手順が示されたことになります:
示したい性質
[$a,b$の最大公約数] = [$b$と「$a\div b$の余り」の最大公約数]

【証明】
$a\div b$を考えてみましょう.商を$q$,余りを$r$とすると
\begin{align}
a=bq+r \qquad(0\leq r < b )
\end{align}と表すことができます.



この式は,「$b,r$の公約数は$a$の約数である」ことを意味しています(右辺を割り切る数は,左辺も割り切る).特に,「$b,r$の公約数は$a,b$の公約数である」ということがわかるので,
(1) $b,r$の最大公約数≦$a,b$の最大公約数
です($b,r$の最大公約数は$a,b$の公約数であるため).



ここで,
\begin{align}
r=a-bq
\end{align}と書き直してみると,全く同様に「$a,b$の公約数は$r$の約数」となり「$a,b$の公約数は$b,r$の公約数である」ことがわかります.したがって,
(2) $a,b$の最大公約数≦$b,r$の最大公約数
です.



以上(1), (2)から
$a,b$の最大公約数=$b,r$の最大公約数
であることがわかりました.//