ユークリッドの互除法
ユークリッドの互除法は、2 つの自然数の最大公約数を求める手法の一つである。- Wikipedia
もくじ
最大公約数とは?
実際にやってみる
割り算の表し方について
なぜ互除法が機能するのか
最大公約数とは?
自然数a,bがあったときに、aとbを2つとも割り切る数字(公約数)の中でも、一番大きい数字のことを最大公約数といいます。
英語ではGreatest Common Divisorと呼ばれ、略してGCDとも呼ばれたりします。
以下、aとbの最大公約数のことを$ gcd(a,b)のように表します。
gcd(24,16)だったら、「24と16の最大公約数」、つまり8になります。
あ、あと商はa/b、あまりはa%bで表すかもです。
例
$ gcd(5,10) = 5
$ gcd(8,12) = 4
$ gcd(425,100) = 25
$ gcd(38067,88823) = 12689
$ gcd(384690276,641150460)は?と聞かれたときに、それを素早く求める方法が「ユークリッドの互除法」です。
実際にやってみる
ユークリッドの互除法のやり方は結構簡単で、割った余りで割る、割った余りで割る…を割り切れるまで繰り返していくだけです。折角なので$ gcd(384690276,641150460)を求めてみましょう。
641150460 を 384690276 で割った余りは 256460184
384690276 を 256460184 で割った余りは 128230092
256460184 を 128230092 で割った余りは 0 (割り切れた!)
ということで、$ gcd(384690276,641150460) = 128230092ということが分かります。素因数分解より楽だし早いしで良いです…(適当)
割り算の表し方について
ここから、ユークリッドの互除法がどうしてちゃんと機能するのか?みたいなのを考えていくんですが、その前に割り算の表し方について復習しておきます。
これまで、割り算では、「21 ÷ 5 = 4 … 1」みたいな表し方をしてきたかもしれません(知らんけど)。
しかし今回は、「21 = 5 × 4 + 1」のように表していきます。
それっぽく言うと、aをbで割った商をq、余りをrとして
$ a = bq + r
と表すことにします。但し、基本的に$ a > b、b > r ≧ 0です。
a = 425, b = 100 なら
$ 425=100\cdot 4+25
みたいな感じになります。慣れてない人は何個か例を自分で考えてみて慣れよう。
なぜ互除法が機能するのか
$ a = bq + r において、$ gcd(a,b) = gcd(b,r)が成り立つからです。
と言われてもよくわからないので、例を考えてみましょう。
$ 81 = 45\cdot 1 + 36
つまり$ a=81,\ b=45,\ r=36
このとき、$ gcd(81,45) = gcd(45,36) が成り立っています。どちらも9になります。
ここから証明です。隠れた前提として、「公約数≦最大公約数」を使います。
あと、
証明…
$ a = bq + r
において、aとbの公約数をmとすると、aとbはどちらもmの倍数なので、
$ a = mk,\ b=mt \ (k,tは整数)
と表せて、それを代入すると
$ mk = mtq + r
$ mk - mtq = r
$ m(k-tq) = r
となり、$ k-tqは整数なのでrがmの倍数であることが示せます。