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

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

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

参考までに、大学の初等整数論へ踏み込んでおきます。

最大公約元からの整数論

【素数の定義】
2 以上の自然数で、正の約数が 1 と、その数自身の 2 個しかないものを素数という。

【合成数の定義】
2 以上の自然数で、1 と、その数以外の正の約数をもつものを合成数という。
※ 2 以上の自然数で、素数でないものが合成数ということです。

合成数の定義は難しそうですが、具体例で見てみます。

6 は、2 以上の自然数です。 6 の正の約数として、2 と 3 が考えられます。1 と 6 以外に正の約数が存在しているので、6 は素数ではありません。

そのため、2 以上の自然数である 6 は合成数ということになります。

まず、合成数についての命題を証明します。この命題には、大学の数学で学習する内容が根本に使われます。

それは、自然数全体の任意の空ではない部分集合には、必ず最小値（最小元）が存在するということです。これは、自然数全体が整列集合となっているということです。

※ 超限帰納法というブログ記事で、自然数全体が整列集合であることを証明しています。クリックすると、リンク先の記事に移動します。

それでは、この自然数全体がもつ性質を使って、次の命題を証明します。
自然数全体を N, 整数全体を Z と表すことにします。

合成数は素数を約数にもつ

【命題】

a を合成数とする。
このとき、a は必ず素数を正の約数としてもつ。

＜証明＞

{x ∈ N | x は合成数だが素数を約数にもたない} という自然数全体 N の部分集合を S と置きます。

この S が空集合であるということを示せば、どの合成数も必ず素数を約数としてもつということになります。そのため、S が空集合ではないと仮定して、矛盾を導きます。

S が空集合でないとすると、S は自然数全体 N の部分集合なので、S には最小値が存在することになります。その最小値を u と置きます。

u ∈ S なので、u は合成数です。

よって、1 < c < u である自然数 c で、u の約数となっているものが存在します。

u を c で割ったときの商を k とすると、
u = ck …★

u と c が自然数なので、k も自然数となっています。

そして、1 < c < u より、1 < k < u

ここで、c は素数か、素数でない（合成数）かのいずれかです。

もし、c が素数だとすると、
1 < k < u なので、素数 c が u の正の約数ということになります。

これは u が素数を約数にもつ合成数ということです。しかし、u は S の元なので、素数を約数としてもたないことに反します。

よって、c は素数ではないということになります。

1 < c だったので、c は合成数です。

ここで、c は素数を約数にもつか、素数を約数にもたないかのいずれかになります。

c が素数を約数にもたないとすると、c は合成数なので、c ∈ S です。

すると、c < u だったので、u が S の最小値だということに反してしまいます。そのため、c は素数を約数にもつことになります。

これより、ある素数 p が存在して、
c = pt (t は自然数) と表すことができます。

これを★に代入すると、
u = (pt)k = p(tk)

これは、素数 p が u の約数であることを示しています。

ところが、u は S の元なので、素数を約数にもちません。そのため、矛盾となります。

以上より、背理法から、S は空集合ということになります。

すなわち、どんな合成数も、素数を必ず約数にもつということが示せました。【証明完了】

この命題によって、合成数というものが、はっきりとしました。

合成数は、2 以上の自然数で、素数を約数にもつものです。

※ 合成数の約数となっている素数のことを、その合成数の素因数といいます。

2 以上の自然数 n について、n が素数か、n が素数ではない合成数かという二択です。

合成数のときには、約数として素数をもつということです。

ここからは、素因数分解の証明を参考までに述べておきます。

素因数分解の注意点ですが、素数 p 自身は、何もせずとも素因数分解が既に完了しているもの（素数ばかりの積の形）と考えます。

素因数分解の証明

【定理１】

n を 2 以上の自然数とすると、n は素数ばかりの積の形で表すことができる。

＜証明＞

定理が偽だと仮定します。

すると、2 以上の自然数で、素数ばかりの積の形で表すことができない自然数が存在することになります。

S を 2 以上の自然数で、素数ばかりの積の形で表すことができないもの全体だとします。

今、S が空集合ではないということなので、S には最小元が存在します。

x ∈ S を S の最小元とします。

素数は、素数ばかりの積の形に既になっていると考えることになっています。そのため、x は素数ではありません。

すると、x は 2 以上の自然数で素数ではないことから、合成数ということになります。

x は合成数なので、【命題】から、x は素数を約数としてもちます。その x の約数となっている素数を p と置きます。

x を p で割った商を y とすると、
x = py (2 ≦ y < x)

素数 p は 2 以上の自然数なので、y は x よりも小さい自然数です。

そのため、y が素数ばかりの積の形で表せないとすると、2 ≦ y なので、y ∈ S となります。

これは、y < x なので、x が S の最小元であったことに反します。

よって、y は素数ばかりの積の形で表せるということになります。

p₂, … , p_k を y を表す素数たちだとすると、
y = p₂×…×p_k です。

x = py だったので、
x = p×p₂×…×p_k となります。

これは、x が素数ばかりの積で表すことができないということに矛盾しています。

以上より、背理法から、【定理１】の反例が存在しないということが示せたので、定理が示されました。【証明完了】

これで、2 以上の自然数は、必ず素数ばかりの積の形となっていることが示せました。

後は、その素数ばかりの積の表し方が、素因数の順番を適切に並び替えると同じものになっているということを示すことが残っています。

このことを示すために、素数についての重要な性質を証明する必要があります。ここで、除法の定理を使います。

【除法の定理】

x を自然数とし、y を整数とする。

このとき、ある整数 q と r が存在して、
y = xq + r (0 ≦ r < x) と表すことができる。

しかも、この表し方は、ただ一通りである。

ユークリッド整域より

余りが割る数よりも小さくなることを利用して、結論を導きます。

素数の性質

【補題】

p を素数とし、a, b を自然数とする。

このとき、p が ab の約数であるならば、「p は a の約数」または「p は b の約数」である。

＜証明＞

p が a の約数だとすると、補題の結論が示せたことになるので、p が a の約数ではない場合について議論を進めます。

{k ∈ N | p は ak の約数} という集合を S と置きます。

p, b ∈ S なので、S は空集合ではない N の部分集合です。そのため、S には最小元 e が存在します。

今、p が a の約数ではないので、e は 2 以上の自然数です。（e = 1 とすると、p が ae = a の約数となってしまうためです。）

t ∈ S を任意に取ると、e と t について、除法の原理から、ある整数 q と r が存在して、
t = eq + r (0 ≦ r < e)

両辺に a を掛けると、at = (ae)q + ar

t, e ∈ S なので、p は at と ae の約数です。
そのため、p は ar の約数になります。

1 ≦ r < e だとすると、 r ∈ S となり、e が S の最小元であることに反してしまいます。そのため、r は 0 でなければなりません。

r = 0 より、
at = (ae)q = a(eq)

無辺を左辺に移項すると、
a(t－eq) = 0 です。

自然数 a ≠ 0 であり、
整数環は整域なので、
t－eq = 0 です。

つまり、t = eq で、e は t の約数となっています。

このため、t として p と b を考えると、e は p と b の約数となっています。

2 ≦ e だったので、e が素数 p の約数であることから、e = p

e は b の約数なので、素数 p が b の約数ということが示せました。【証明完了】

この補題から、素数 p が自然数 a と b の積 ab の約数であれば、p は a または b の約数ということになります。

この補題を使って、素因数分解の素数の積としての表し方が、「素因数の積の順序を除けば、ただ一通りであること」を示します。

積の順序を除けば一通り

【定理２】

n を 2 以上の自然数とする。また、n は素数ばかりの積の形で表したとき、
p₁×…p_k と q₁×…×q_l だったとする。ただし、p_i や q_j は n の素因数。

このとき、k と l は等しく、p₁, … , p_k を並び替えると、q₁, … , q_l となる。

＜証明＞

この定理を成立しない反例が存在したとします。そのような 2 以上の自然数の中で、最小のものを m と置きます。

この m が
p₁×…×p_k と q₁×…×q_l と素因数の積に分解されているとします。

すると、p₁ は n の素因数なので、
q₁×(q₂×…×q_l) の約数となります。

【補題】より、p₁ は、
「q₁ の約数 または q₂×…×q_l の約数」となります。

p₁ が q₁ の約数である場合は、q₁ が素数であることから、p₁ = q₁ となっています。

n を p₁ で割ったときの商は、
p₂×…×p_k = q₂×…×q_l

p₂×…p_k < m なので、m が最小の反例であったことから、p₂×…p_k について定理が成立しています。

そのため、p₂, … , p_k を並び替えると、q₂, … , q_l となり、k と l は等しく、p₁, … , p_k を並び替えると、q₁, … , q_l となります。

これは、m が反例であったことに矛盾します。

よって、p₁ は、q₂×…×q_l の約数ということになります。

【補題】より、p₁ は、q₂, … , q_l のどれかの約数 ということになります。

p₁ が q_i の約数だとすると、
m ÷ p₁ は割り切れるので、
p₂×…×p_k = m ÷ p₁ = m ÷ q_i

m ÷ q_i は、
q₁×…×q_i-1×q_i+1×…×q_l です。

m ÷ q_i < m より、m が最小の反例であったことから、m ÷ q_i について定理の結論が成立します。

そのため、k と l は等しく、p₂, … , p_k を並び替えると、q₁, … , q_i-1, q_i+1 , … , q_l となります。

つまり、p₁, … , p_k を並び替えると、
q₁, … , q_l です。【証明完了】

これで、素因数分解と、その一意性も証明できました。

関連する記事として、高校の情報と整数についての内容として、n進法の小数という記事も投稿しています。

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

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