最大公約数 – 求め方 | ２つの整数や３つの整数について具体例を用いて解説

2023年4月3日

" 最大公約数 – 求め方 “について解説をしています。

具体的な整数を例に使って、求める方法を２つ述べています。

はじめに表紙に記している18と24の最大公約数を求めた方法を解説し、それから３つのときの求め方を説明します。

最大公約数の求め方を理解するためには、公約数というものの定義を押さえておくと良いかと思います。

整数 a と b について、a と b の両方を割り切る自然数を「整数 a と b の公約数」と定義します。

3 つ以上についても、それら全てを割り切る自然数が公約数です。

最大公約数 – 求め方: 2つのときについて

18と24を例に、
最大公約数を求める方法を解説。

表紙の図で、
2) 18 24 とすだれ算を開始しました。

18 と 24 の公約数を１つもってきて、その公約数で割ってできた商を下に書きます。

2 という 18, 24 の公約数で割ったときの商は、
9 と 12 です。

今度は、9 と 12 の公約数をもってきます。

3) 9 12 というすだれ算の続きです。

再び公約数である 3 で割ったときの商を下に書きます。

3 と 4 となります。

また公約数を考えるのですが、3 と 4 の公約数は 1 しかありません。

このすだれ算ですが、公約数が 1 しかないという状況になったら、操作を終了します。

この終了のところまでくると、割る数として横に書いた公約数たちが拾い上げられたことになります。

2) 18 24
3) 9 12
だったので、拾い上げた公約数は 2 と 3 です。

最後に、これらの拾い上げた公約数たちを全て掛け合わせます。

その掛け算の値が求める最大公約数となります。

すなわち、
2 × 3 = 6 が、18 と 24 の最大公約数です。

このすだれ算が表している内容について説明をしておきます。

求め方の操作が表す内容

18 = 2×3²,
24 = 2³×3 と素数の積の形になっています。

自然数は素数ばかりの積の形で表すことができます。

18 と 24 のどちらにも使われている素数は公約数となっています。

先ほど、公約数の 2 で割りました。

すると、
9 = 3², 12 = 2²×3 となります。

そうすると、次の公約数として、もう 2 は使えないことに気づきます。

そこで、次に、どちらにも使われている 3 を公約数として考えたわけです。

9 と 12 を 3 で割ると、
3, 4 = 2² となりました。

そして、公約数が 1 しかないことから操作を終了したわけです。

このように、素数の積の形を思い描きながら、公約数たちを割る数として拾い上げていたわけです。

さらに、
90, 210, 390 という３つの整数の最大公約数を求める手順について説明をします。

3つの最大公約数の求め方

90, 210, 390 の公約数である 2 で割った商を下に書きます。

45, 105, 195 となるので、次の公約数として 3 を考えます。

3 で割ると、
15, 35, 65 なので、公約数として 5 を取れます。

5 で割ると、
3, 7, 13 となります。

これらの公約数は 1 しかありません。

公約数が 1 しかないという終了の合図となったので、ここまでで拾い上げた公約数をすべて掛け合わせます。

2×3×5 = 30 が求める最大公約数です。

90 = 30×3,
210 = 30×7,
390 = 30×13 となっているわけです。

ここまで、すだれ算を使った最大公約数の求め方について述べてきました。

ただ、この方法には問題点があります。

それは、「公約数が見つからないときに、すだれ算が開始できない」ということです。

この問題点が出てきたときのために、もう１つの最大公約数の求め方について、これから解説をします。

「228 と 817」の最大公約数を求めるということを考えます。

このときの方法の根本となる命題を１つ述べ、それを利用して求め方を説明します。

もう１つの最大公約数の求め方

【正しい命題】

自然数 b を a で割ったときの商を q, 余りを r とする。

すなわち、b = aq+r
(ただし、0≦ r < a)とする。

このとき、
a と b の最大公約数は、a と r の最大公約数に等しい。

つまり、割られる数と割る数の最大公約数は、割る数と余りの最大公約数に等しい。

この割られる数と割る数の最大公約数は、割る数と余りの最大公約数に等しいということを使い続ける方法になります。

「228 と 817」の最大公約数を例に、求め方を説明します。

大きい方の 817 を割られる数 b、228 を割る数 a として命題を使い続けます。

命題を使うためには、割り算を計算して、商と余りを求めます。

このときに、割り算を計算すれば良いので、公約数が見つからないという問題点に出くわすことがないので、気分が楽です。

その代わりに、計算が長くなってしまうこともあるので、「公約数がすぐに見つかったときは、すだれ算を使う」と、使い分けを日頃から意識しておくと良いかと思います。

操作を実行する

817÷228を計算して商と余りを確定します。

817
= 228×3+133 なので、
余りが133と分かりました。

ここで、「割られる数817と割る数228の最大公約数が、割る数228と余り133の最大公約数に等しい」という命題を使います。

817 と 228 で最大公約数を求めるよりも、より小さい数のペアで最大公約数を求めることができるわけです。

228と133の最大公約数を求めれば良いということが、命題によって分かりました。

そこで、今度は大きい方の228を b、133を割る数 a として、再び割り算を計算し、商と余りを確定させます。

228
= 133×1+95 です。

228と133の最大公約数が求める最大公約数ということでしたが、再び命題によって、割る数133と余り95の最大公約数に等しいということになります。

より小さいペヤの方が計算しやすいので、
133を b、割る数 a を 95 として、また割り算を計算して商と余りを確定させます。

133
= 95×1+38 です。

再び「割られる数と割る数の最大公約数は、割る数と余りの最大公約数に等しい」という命題を使います。

これで、95と38の最大公約数が求める最大公約数と分かりました。

そこで、また割り算を計算します。

95 = 38×2+19 となります。

さらに命題を使い、割る数38と余り19の最大公約数が求める最大公約数と分かります。

終了する合図を認識

割られる数38と割る数19で割り算を計算します。

38 = 19×2+0 となります。

余りが 0 になるときが、操作を終了するときの合図となります。

38と19の最大公約数ですが、割り切れたので、割る数19自身が最大公約数ということです。

「228 と 817」の最大公約数を言い換えて、38と19の最大公約数というところまで来ました。

そして、38と19の最大公約数が19と分かりました。

以上より、19が「228 と 817」の最大公約数です。

実際、
228 = 19×12,
817 = 19×43 となっています。

12と43の公約数は 1 しかないので、確かに最大公約数となっています。

19が公約数と気づければ、すだれ算で１回の割り算で最大公約数を求めることができたわけですが、なかなか公約数が見つからないときのための求め方になります。

この論法はユークリッドの互除法というもので、大学の数学科で扱われる内容にもなります。

参考までに、大学の数学科で扱う内容を述べます。

大学の数学の内容

【命題１】

巡回群 G = <x> の部分群 H も巡回群である。

＜証明＞

H が単位群 {0} のときは、H = <0> なので定理が成立します。
そのため、以下で、H ≠ {0} とします。

<x> = G ⊃ H なので、ある正の整数が存在して、
nx ∈ H となります。

そのような整数 n の中で最小の正整数を m と置くと、
mx ∈ H です。

H の各元は ax (a は整数) という形で表されます。

ax ∈ H という状況で、a と m で除法の定理の形で表すと、
a = mq + r（ここで 0 ≦ r < m）

この整数 q と r は、a を m で割ったときの商が q で、余りが r ということです。

今、
ax = (mq + r)x
= mqx + rx = q(mx) + rx

さらに、ax と mx は部分群 H の元なので、
rx = ax – q(mx) ∈ H

m の最小性から、r = 0 でなければなりません。

よって、a = qm となり、a は m の倍数となります。

以上より、H のどの元も mx もしくは mx の逆元を有限個の和ということになり、H が mx の一元で生成されているということになります。

つまり、H = <mx>【証明完了】

ここから、環論でもよく使う最大公約数が 1 となっているときの等式について証明をします。

記号ですが、z₁, … , z_n ∈ Z の最大公約数を
gcd(z₁, … , z_n) と表すことにします。
※ Z は整数環です。

よく使う等式

【命題２】

z₁, … , z_n ∈ Z について、
gcd(z₁, … , z_n) = d であるとき、
ある整数 m₁, … , m_n が存在して、
m₁z₁ + … + m_nz_n = d

＜証明＞

H = <z₁, … , z_n> という Z の部分群に対して、【命題１】を適用すると、
ある d’ ∈ Z が存在して、H = <d’>

よって、d’ ∈ H なので、
ある整数 m₁, … , m_n が存在して、
m₁z₁ + … + m_nz_n = d’

ここで、この d’ が z₁, … , z_n の最大公約数となっていることが次のようにして確かめられます。

1 ≦ i ≦ n について、z_i ∈ H = <d’> より、
ある整数 k_i が存在し、z_i = k_id’

よって、d’ は z_i の約数ということになります。

そのため、d’ ≦ d = gcd(z₁, … , z_n)

また、m₁z₁ + … + m_nz_n = d’

の左辺は d で割り切れるので、d は 右辺の d’ の約数となっています。

そのため、d ≦ d’ でもあるので、d = d’【証明完了】

【関連する記事】

■ 素数判定法

■ 5進数の小数

それでは、これで今回の記事を終了します。

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