【最大公約数】ユークリッドの互除法を知ろう

ユークリッドの互除法をご存知ですか？

2つの整数の最大公約数を求める方法のことで、現在は高校数学の数Aで習うようです。

(私が高校生の頃は、まだ「数C」という科目がある時代でしたね)

20代後半以降の方だと、ユークリッドの互除法を学校で習っていないかもしれません。

そこで今回は、ユークリッドの互除法のやり方を紹介します。ひたすら『わりざん』を続けていくのですが、そんなに難しくありません。ぜひとも、計算練習がてらやってみてください。

尚、わりざんに関しては以下のnoteで書いたルールに従います。余りは0以上割る数未満です。

それではご覧ください！

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

A, Bという2つの数の最大公約数を求めるときは、以下のようにわりざんを繰り返し行います。

まずA÷Bを行う。「わりざん」の性質より、以下の式を満たす整数 q1, r1 が存在します。

A = q1 × B + r1　(0≦r1＜B)

r1がA÷Bの余りになりますね。次に、割る数に使っていたBと余りのr1を使って『B÷r1』をします。「わりざん」の性質より、以下の式を満たす整数 q2, r2 が存在します。

B = q2 × r1 + r2　(0≦r2＜r1)

r1がA÷Bの余りになりますね。さらに、割る数に使っていたr1と余りのr2を使って『r1÷r2』をします。「わりざん」の性質より、以下の式を満たす整数 q3, r3 が存在します。

r1 = q3 × r2 + r3　(0≦r3＜r2)

このような操作を、余りが0になるまで続けます。

ここでは余りを正の整数としており、

0≦…r4＜r3＜r2＜r1＜B

となっているので、いずれ必ず余りは0になることが約束されています。

もし、n回目のわりざんで余りが0になったとしましょう。このとき、『r_(n-2) ÷
r_(n-1)』をしているので、以下のような整数 q_nが存在します。

r_(n-2) = q_n × r_(n-1)

このとき、r_(n-1)がAとBの最大公約数になるのです。

これだけだとわかりにくいと思うので、以下で具体例を書きます。『わりざんを繰り返しやってるんだな〜』程度で大丈夫です。

最大公約数の記号： GCD

具体例に行く前に、一つだけ記号を紹介しておきます。

最大公約数は、英語で「Greatest Common Divisor」といいます。

よって、『AとBの最大公約数』を記号で

GCD(A, B)

と表します(英語の頭文字になっているのです)。小文字でgcd(A, B)と書く場合もありますが、このnoteでは大文字で表記します。

9と15の最大公約数は3なので、

GCD(9, 15) = 3

と書きます。

具体例

では、具体例でユークリッドの互除法のやり方を理解していきましょう。やり方がわかったら、色々な数で試してみてください。

①GCD(119, 49)

さっそく記号を使いましたが、119と49の最大公約数を求めていきます。

まずは119÷49を考えます。そうすると、以下のような式で表すことができます。暗算でもいいですし、わりざんの筆算を行うことで求めることもできます。

119 = 2×49 + 21

余りが21となります。次に、49÷21を考えます。同じように計算することで、以下のように表せますね。

49 = 2×21 + 7

今度は余りが7です。さらに、21÷7を考えると、以下のようになります。

21 = 3×7

余りはなく、ちょうど割り切れました。このとき、最後に割る数として登場した7が最大公約数になるのです。

よって、

GCD(119, 49) = 7

となります。

②GCD(242, 222)

こちらも同じようにわりざんをしていきます。

242 = 1×222 + 20

222 = 11×20 + 2

20 = 10×2

よって、GCD(242, 222)=2となる。

互いに素とは

最大公約数に関して、『互いに素』という言葉があります。

整数 A, Bが『互いに素』であるとは、

GCD(A, B) = 1

であることである。

最大公約数が1のとき、2つの数は互いに素と言うのです。言い換えるなら、素因数分解したときに共通する素因子がないということですね。

GCD(233, 144)を求めるとき、長いですが以下のようにわりざんを続けていきます。
(実は2つの数はフィボナッチ数のため、商が1のわりざんが続いています)

233 = 1×144 + 89
144 = 1×89 + 55
89 = 1×55 + 34
55 = 1×34 + 21
34 = 1×21 + 13
21 = 1×13 + 8
13 = 1×8 + 5
8 = 1×5 + 3
5 = 1×3 + 2
3 = 1×2 + 1
2= 2×1

よって、GCD(233, 144) = 1となる。

このとき、233と144は互いに素であると言います。

注意してほしいのは、『互いに素』が『2つの数がどちらも素数である』ということではないということです。素数同士でなくても、互いに素になることもあります。

例えば、GCD(16, 27) = 1です。しかし、16と27はどちらも素数ではありませんよね。

16 = 2×2×2×2
27 = 3×3×3

最後に

ここまで、ユークリッド互除法を用いた最大公約数の求め方について説明しました。

とはいえ、そもそも素因数分解ができてしまえば最大公約数は求まります。

119と49を

119 = 7×17
49 = 7×7

と素因数分解できれば、共通する素因子である7が最大公約数であることがわかります。

しかし、数が大きくなると素因数分解は難しくなります。4桁や5桁になると、途端に手つかずになることが多いですね。

(素因数分解を語っているnoteを見ればわかるはずです笑)

わりざんであれば、筆算を使えば比較的楽に求めることができるので、大きい数の場合には役立ちます。

日常生活で最大公約数を求める機会はあまりないと思いますが、今回の方法はぜひ覚えておいてくださると嬉しいです！

素数はいつも、あなたのそばに。
Let's enjoy SOSU !

最後まで読んでいただき、ありがとうございました。