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

今回は、ユークリッドの互除法を利用した、最大公約数の求め方を解説します。

非常に有名なものなので、名前は聞いたことあるかも！という方も多いはず。

ただ、具体的にどのようなものかはよくわからないという方や、内容はわかるけど証明までは知らない、という方も多いのではないでしょうか。

実は、最大公約数は、コンピュータの世界の暗号化技術（RSA暗号）に使われる、私たちにとって非常に身近なものです。

ユークリッドの互除法についての証明を見ていくことで、身近な数学に対する知識・理解を深めていきましょう！

解説

割り算と、最大公約数の関係

まずは、ユークリッドの互除法の背景にある定理について、その証明から見ていきます。

ユークリッドの互除法を利用した最大公約数の求め方

今までで、\(gcd\ (a，b)=gcd\ (b，r)\ \)という関係式が得られました。

ここからは、この関係を利用して、実際にどのように最大公約数を求めるのか、その操作方法を見ていきましょう。

具体例（\(1517\) と \(1073\) の最大公約数）

まずは次の式をご覧ください。

\[\begin{alignat*}{3}
1517 &=1073\cdot 1&&+444\quad&&・・・① \\
1073 &=444\cdot 2&&+185&&・・・② \\
444 &=185\cdot 2&&+74&&・・・③ \\
185 &=74\cdot 2&&+37&&・・・④ \\
74 &=37\cdot 2&&+0&&・・・⑤
\end{alignat*}\]

こちらでは、以下の操作を行っています。

• 操作 1
  与えられた数 \(a，b\ (a\geqq b)\) の関係を、\(a=b\cdot{q}_{0}+{r}_{1}\) の形で表す（等式①）
• 操作 2
  この \(b，{r}_{1}\) の関係を、改めて、\(b={r}_{1}\cdot{q}_{1}+{r}_{2}\) の形で表す（等式②）
• 操作 3
  この \({r}_{1}，{r}_{2}\) の関係を、改めて、\({r}_{1}={r}_{2}\cdot{q}_{2}+{r}_{3}\) の形で表す（等式③）
• 操作 4
  操作 3の操作 \(({r}_{k-2}={r}_{k-1}\cdot{q}_{k-1}+{r}_{k})\) を、余り \({r}_{k}\) が \(0\) になるまで繰り返す（等式④⑤）
• 操作 5
  操作 4の等式の、1つ前の等式で得られた余り \(R\)（等式④の余り37）が、\(a，b\) の最大公約数
  \(({r}_{n-2}={r}_{n-1}\cdot{q}_{n-1}+{r}_{n}\) まで繰り返して、\({r}_{n}=0\) となった場合、\(R={r}_{n-1})\)

これを踏まえて、改めて先ほどの等式を見てみると、⑤で余りが \(0\) になっています。

\[\begin{alignat*}{3}
1517 &=1073\cdot 1&&+444\quad&&・・・① \\
1073 &=444\cdot 2&&+185&&・・・② \\
444 &=185\cdot 2&&+74&&・・・③ \\
185 &=74\cdot 2&&+37&&・・・④ \\
74 &=37\cdot 2&&+0&&・・・⑤
\end{alignat*}\]

したがって、\(1517\) と \(1073\) の最大公約数 \(gcd(1517，1073)\) は、1つ前の等式④で得られた余り「\(37\)」と求めることができました！

ちなみに、それぞれの数を実際に \(37\) で割り算してみると、\(1517=37\times 41，\)\(1073=37\times 29\) で、正しいことが確認できます。
どちらも、それなりに大きめの素数でできた合成数であり、これを1から素因数分解すると考えると、ゾッとしますね。。

こうしてみると、ユークリッドの互除法の威力を強く感じていただけたのではないでしょうか。

余りが \(0\) となる、1つ前の等式の余り \(R\) が、なぜ最大公約数になるのか？

先ほどの具体例で、ユークリッドの互除法を用いた最大公約数の流れや、非常に有能なテクニックであることは、なんとなく掴んでいただけたのではないかと思いますが、そもそもなぜ、この方法で最大公約数を求めることができるのか。

その理由は、ズバリ、
「余りが \(0\) なら、（割られる数）と（割る数）の最大公約数は、（割る数）になる」から、です。

もう一度、こちらの等式をご覧ください。

\[\begin{alignat*}{3}
1517 &=1073\cdot 1&&+444\quad&&・・・① \\
1073 &=444\cdot 2&&+185&&・・・② \\
444 &=185\cdot 2&&+74&&・・・③ \\
185 &=74\cdot 2&&+37&&・・・④ \\
74 &=37\cdot 2&&+0&&・・・⑤
\end{alignat*}\]

⑤の式について、余りが \(0\) になっている、ということは、\(74\) は、\(37\) で割り切れる、ということになります。
そして、（割られる数）が（割る数）で割り切れるとき、2つの数の最大公約数は、（割る数）です。⑤でいえば、\(gcd(74，37)=37\) です。

ここで、前半で証明した、\(gcd\ (a，b)=gcd\ (b，r)\ \)という関係式を、等式④に適用してみると、

\[gcd(185，74)=gcd(74，37)=37\]

となります。さらにこれを等式③に適用すると、

\[gcd(444，185)=gcd(185，74)=gcd(74，37)=37\]

となり、余りが \(0\) になった等式から順に、上に見ていくと、

\[gcd(1517，1073)=・・・=gcd(74，37)=37\]

となります。

そのため、余りが \(0\) になったときの、1つ前の等式の余り \(R\) が最大公約数になる、ということがわかりました。

おわりに

お疲れさまでした！
今回は、「割り算と、最大公約数の関係」と、それを利用した「ユークリッドの互除法による最大公約数の求め方」を解説しました。

今回のポイントは、【行った操作は、割り算だけ】ということです。

2つの数の最大公約数を求める場合、もし、定義通りにやろうとすると、以下の操作が必要です。

• 素因数分解をして、各々の数の素因数を見つける
• 得られた素因数の内、2つの数に共通のもの（共通因数）を見つける
• 共通因数を全て掛け合わした数を、最大公約数とする

このうち、1つ目の「素因数を見つける」という手順が非常にネックでして、小さい数ならなんとかなりますが、100桁、1千桁、1万桁、、、と桁数が大きくなるにつれて、「素因数を見つける」のは本当に一苦労です。
（つい最近も、新たな素数が発見されたことがニュースになっていましたが、それくらい、ある数がどんな素因数を持っているか（あるいは、素因数を一切持っていないか）を確認するのは難しい！ということです）

一方で、今回見てきた、「2つの自然数に対して、割り算を繰り返す」という方法は、どれだけ値が大きくなっても計算できます。（多少、根性は必要ですが、、、）

こんな、非常に強力な武器である「ユークリッドの互除法」について、少しでも興味を持っていただけるとうれしいです！