ユークリッドの互除法 | 整数でも多項式でも使えるので、シンプルな例で使い方を習得！
" 互除法 " は、整数でも多項式でも使えます。
二つの整数、もしくは二つの多項式について、最大公約数を求める方法になります。
具体例を通して使い方を押さえておくと良いかと思います。
また、どうして最大公約数を求めたことになるのかという証明は、大学数学の可換環論を勉強していくときの良い入口になってくれます。
それでは、最大公約数を表す記号から説明を始めます。
ユークリッドの互除法 :整数について
このブログ記事では、二つの非負整数 a と b について、a または b が 0 でないときに、a と b の最大公約数を gcd(a, b) と表すことにします。
負の整数が来たときは、符号を外したプラスのときで最大公約数を求めておいて、後から －1 を適宜つけるということで、非負整数のときを考えることにします。
※ 非負整数とは、0 以上の整数のことです。
a と b のうち、片方が 0 で、もう片方が 0 でないときは、0 でない方の非負整数自身が最大公約数となります。
例えば、a ≠ 0 で、b = 0 のときは、b が a で割り切れるので、a と b = 0 の最大公約数は a となります。
互除法を支えているのが、整数について成立する除法の原理というものです。
非負整数 a と b （ただし、割る数 b ≠ 0）が与えられたとします。
このとき、a を b で割ったときの商を q、余りを r とすると、
a = bq + r … ★
(ただし、0 ≦ r < b) となります。
この余り r が割る数 b よりも小さくなるということが、互除法を用いて最大公約数が求められるということの根拠になります。
この等式 ★ から、最大公約数について考察をしてみます。
割られる数と割る数のgcd
自然数 a と b の最大公約数を gcd(a, b) とすると、この gcd(a, b) も自然数です。
そして、最大公約数なので、a と b の公約数の中で最大の自然数となっています。
特に、公約数なので、gcd(a, b) は、a と b の両方ともを割り切ります。
そこで、★の右辺から bq を左辺へと移項した式を考えます。
つまり、a － bq = r
gcd(a, b) は、左辺の a と b をどちらも割り切ることから、左辺全体を割り切ることになります。
すると、左辺と右辺は同じ値なので、
gcd(a, b) は右辺の r も割り切ることになります。
よって、gcd(a, b) は、b も r も割り切ってので、b と r の公約数ということになります。
b と r の最大公約数を gcd(b, r) と表すと、最大公約数は公約数の中で最大なので、
gcd(a, b) ≦ gcd(b, r) となります。
一方、今度は ★ の右辺を見てみてみます。
a = bq + r の右辺の b も r も gcd(b, r) で割り切れるので、右辺全体が gcd(b, r) で割り切れることになります。
すると、左辺は右辺と同じ値なので、
gcd(b, r) は a も割り切ることになります。
よって、gcd(b, r) は b と a を両方とも割り切るので、a と b の公約数ということになります。
最大公約数は公約数の中で最大なので、
gcd(b, r) ≦ gcd(a, b) となります。
gcd(a, b) ≦ gcd(b, r) かつ
gcd(b, r) ≦ gcd(a, b) が成立したので、等号となります。
よって、gcd(a, b) = gcd(b, r) です。
これは、割られる数と割る数の最大公約数が、割る数と余りの最大公約数に等しいということを表しています。
求めやすい方で求める
a と b の最大公約数を求めるということを考えたときに、gcd(a, b) と gcd(b, r) が同じということが分かっています。
除法の原理から、r は b よりも小さい値なので、小さい方が、最大公約数を求めやすい気がしてきます。
そこで、先ほど導いた「割られる数と割る数の最大公約数が、割る数と余りの最大公約数に等しい」ということを再び考えます。
gcd(b, r) を求めるときに、b を r で割ると、また「割られる数と割る数の最大公約数が、割る数と余りの最大公約数に等しい」ということが使えます。
どんどん繰り返していくと、余りが確実に小さくなっていくことから、そのうち余りが 0 になります。
文章だけだと分かりにくいので、記号を使って表します。
【命題 1】
a を非負整数、b を 1 以上の整数とする。
また、a を b で割った商を q1、余りを r1 とする。
r1 = 0 ならば、gcd(a, b) = gcd(b, r1) である。
r1 ≠ 0 ならば、b を r1 で割った商を q2、余りを r2 とする。
そして、割る数を余りで割るということを繰り返し、qk を rk を割ったときに割り切れたとする。ただし、k は 2 以上の整数。
このとき、
gcd(a, b) = gcd(rk-1, rk) となる。
＜証明＞
割る数 b についての帰納法で示します。
【b = 1 のとき】
a は b = 1 で割り切れるので、r1 = 0 です。
このとき、gcd(a, b) = gcd(a, 1) = 1 となっています。
そして、gcd(b, r1) = gcd(1, 0) = 1 です。
よって、gcd(a, b) = 1 = gcd(b, r1) より、
b = 1 のときに命題は成立しています。
【b ≧ 2 のとき】
(b － 1) 以下の任意の自然数について、命題が成立しているとして、b についての命題が真であることを示します。
a が b で割り切れていたとすると、
r1 = 0 であり、gcd(a, b) = b です。
gcd(b, r1) = gcd(b, 0) = b より、
gcd(a, b) = gcd(b, r1) より、命題が成立しています。
a が b で割り切れなかったとします。
このとき、
a = bq1 + r1 … (1)
(ただし、1 ≦ r1 < b)
ここで、非負整数 b を 1 以上の整数 r1 が割り切るときを考えます。
r1 ≦ b － 1 なので、帰納法より、
gcd(b, r1) = gcd(r1, r2)
(ただし、r2 = 0)
または gcd(b, r1) = gcd(rk-1, rk)
よって、b が r1 で割り切れていたときは、
gcd(a, b) = gcd(b, r1) = gcd(r1, r2) となり、命題が成立しています。
※ これは、k = 2 のときになります。
b が r1 で割り切れていないときは、
gcd(a, b) = gcd(b, r1) = gcd(rk-1, rk) となり、命題が成立しています。
以上より、割る数が 1 以上の任意の整数 b であるとき、命題が成立しています。【証明完了】
証明を見ると、難しそうですが、割る数を余りで割るということを割り切れるまで繰り返すということが述べられている命題です。
実際に、シンプルな具体例で、この命題や、証明の内容を確認してみます。
シンプルな例で確認
80 と 12 の最大公約数 gcd(80, 12) を、互除法を使って求めます。
割る数を余りで割るということを割り切れるまで実行します。まずは、大きい方の 80 を小さい方の 12 で割り、除法の原理の形にします。
※ a = 80, b = 12 という設定です。
80 = 12 × 6 + 8 です。
gcd(80, 12) = gcd(12, 8) となっています。
※ 割られる数と割る数の gcd は、割る数と余りの gcd でした。
割り切れていなかったので、
b = 12 を余り r1 = 8 で割ります。
12 = 8 × 1 + 4 より、割り切れなかったので、余り r2 = 4 が出てきました。
割る数を余りで割るということを割り切れるまで繰り返します。
r1 = 8 を r2 = 4 で割ります。
8 = 4 × 2 + 0 より、余りが 0 になったので、割り切れました。
r3 = 0 です。
よって、gcd(8, 4) = 4 です。
割り切れたので、4 自身が最大公約数です。ここまでの内容をまとめてみます。
gcd(80, 12) = gcd(12, 8) = gcd(8, 4) = 4 です。
求めたかった gcd(80, 12) が 4 だと分かりました。
先ほどの【命題 1】で設定した文字を使うと次のようになっています。
gcd(a, b) = gcd(b, r1) =
gcd(r1, r2) = gcd(r2, r3) です。
r3 = 0、つまり、割り切れたので、割る数を余りで割るということの操作が、ここで終了です。
ちなみに、r3 = 0 なので、gcd(r2, r3) = r2 です。上で書いたように、この r2 が 4 でした。
それでは、ここから、多項式についても応用していきます。
ユークリッドの互除法 :多項式で！
多項式についても、除法の定理（剰余の定理）が成立します。
記号ですが、多項式 f(x) の次数を deg f(x) と表すようにします。
また、片方の多項式が 0 でないときに、f(x) と g(x) の最大公約多項式を
gcd(f(x), g(x)) と表すことにします。
そうすると、先ほどの整数のときと同じ状況になっています。
多項式でも互除法
f(x) を割られる多項式、g(x) ≠ 0 を割る多項式とします。
そして、商を q(x) とし、余りを r(x) とします。このときに、次のようになっています。
f(x) = g(x)q(x) + r(x)
r(x) = 0 または
deg r(x) < deg g(x)
余りの次数ですが、割る多項式の次数よりも小さくなります。
このことから、多項式の次数について、帰納的に、割る多項式を余りで割るということを繰り返していくと、有限回の操作で割り切れます。
また、多項式についても、最大公約多項式のことを gcd で表すと、
gcd(f(x), g(x)) = gcd(g(x), r(x)) となっています。
これらのことから、整数のときと同じく、多項式についても互除法が使えます。命題の形で述べると煩雑になるのですが、同じく帰納法で示せます。
除法を行うと、次数が小さくなることから、同じ証明手順で互除法の証明ができます。この証明は、省略して、実際に互除法を使ってみます。
円分多項式という大学の数学で扱う多項式に関連する二項多項式の最大公約多項式を、互除法で導きます。そのときに、役立つ内容を以下で証明します。
内容が発展的ですが、帰納法の練習に眺めて頂けると幸いです。
実践練習
【命題 2】
自然数 s, t について、s > t ≧ 1 とする。
多項式 xs － 1 と xt － 1 について、
gcd(xs － 1, xt － 1)
= xgcd(s, t) － 1
※ ここで、指数の gcd(s, t) は非負整数 s, t についての最大公約数です。
＜証明＞
次数 t についての帰納法で示します。
【t = 1 のとき】
(x － 1)(xs-1 + xs-2 + … + x + 1)
= xs － 1 より、
x － 1 は xs － 1 を割り切ります。
※ これは、初項 1、公比 x、項数 s の等比数列の和の公式の分母を払ったものになります。
よって、xs － 1 が x － 1 で割り切れています。
そのため、
gcd(xs － 1, xt － 1) = x － 1 です。
また、gcd(s, t) = gcd(s, 1) = 1 となので、
gcd(xs － 1, xt － 1)
= x － 1 = xgcd(s, t) － 1
よって、t = 1 のときに、成立しています。
【t ≧ 2 のとき】
(t － 1) 以下の任意の自然数について、命題が成立していると仮定し、t のときにも命題が成立することを示します。
非負整数 s と t (≠ 0) について、s を t で割ったときの商を a、余りを r とすると、
除法の原理から、s = ta + r
(ただし、0 ≦ r < t)
ここで、r = 0 とすると、s = at であり、
gcd(s, t) = t となります。
そして、次が成立します。
よって、xs － 1 は xt － 1 で割り切られています。
そのため、
gcd(xs － 1, xt － 1)
= xt － 1 = xgcd(s, t) － 1
ゆえに、r = 0 のときは、成立しています。
よって、以下では、r ≧ 1 として、議論を進めます。
今、s = ta + r より、
xs － 1 = xta+r － 1
= xta+r －xr + xr － 1
= (xta － 1)xr + xr － 1
ここで、先ほど示したように、
xta － 1 は、xt － 1 で割り切れるので、整数係数の多項式 q(x) が存在して、
(xta － 1)xr = (xt － 1)q(x) と表すことができます。
よって、
xs － 1 = (xt － 1)q(x) + xr － 1 かつ
deg(xr － 1) < deg(xt － 1)
r ≧ 1 より、除法の原理より、
xs － 1 を xt － 1 で割った商が q(x) で、
余りが xr － 1 ということを表しています。
よって、割られる多項式と割る多項式の最大公約多項式は、割る多項式と余りの最大公約多項式に等しいため、
gcd(xs － 1, xt － 1)
= gcd(xt － 1, xr － 1)
r < t より、帰納法から、
gcd(xt － 1, xr － 1) = xgcd(t, r) － 1
一方、s = ta + r だから、
gcd(s, t) = gcd(t, r) でした。
そのため、これらをまとめると、
gcd(xs － 1, xt － 1)
= xgcd(t, r) － 1 = xgcd(s, t) － 1 です。
以上より、自然数 t についての命題が証明できました。【証明完了】
この証明では、互除法でいうところの繰り返しを、帰納法で乗り越えています。
難しそうな形の最大公約数を求める問題でしたが、等比数列の和の公式を変形した式や互除法を成立させていた「割られる数（多項式）と割る数（多項式）の gcd」 が、「割る数（多項式）と余りの gcd」に等しいということから、示せました。
関連する高校数学の内容、そして大学の数学へ向けて、一次不定方程式というブログ記事を書いています。
整数環についてのイデアルをシンプルな例を用いて解説しています。
さらに、z1, … , zn の最大公約数が d であるときに、a1z1+ … anzn = d
と、整数 a1, … , an を用いて表すことができることをねじれ群という記事で解説しています。
それでは、これで今回のブログ記事を終了します。
読んで頂き、ありがとうございました。