← PC用は別頁

■最大公約数と最小公倍数

○　最大公約数，最小公倍数とは

　２つ以上の正の整数に共通な約数（公約数）のうち最大のものを最大公約数といいます．
　　例　12 と 18 の公約数は，1,2,3,6 で， 6 が最大公約数

※最小公約数という言葉は使う値打ちがありません．なぜなら，公約数のうち一番小さい（正の）数は 1 に決まっているからです．

　２つ以上の正の整数の共通な倍数（公倍数）のうち最小のものを最小公倍数といいます．
　　例　2 と 3 の公倍数は，6,12,18,24,... で， 6 が最小公倍数
※最大公倍数は決められません．なぜなら，大きな（正の）公倍数は，次の例で分かるように限りなくあるからです．
例　2 と 3 の公倍数　：　6 , 12 , 18 , 24 , 30 , 36 , ...

○　最大公約数，最小公倍数の求め方

　この頁では，以下の３通りの求め方を紹介する．（中学校では，[III]は扱わない ）
まず，最大公約数を次のいずれかの方法で求める．
　[I]　　共通に割れるだけ割っていく方法
　[II] 　素因数分解を利用して共通な指数を探す方法
　[III]　ユークリッド互除法による方法

[I][II]では最小公倍数を求める方法も示されるが，[III]のように最大公約数だけが求まるときは，次の関係式AB=GLを用いて最小公倍数も求まる．
○　２数 A , B の最大公約数を G 最小公倍数を L とおくと，
AB=GL
が成り立つ．
（証明）
A=A’G , B=B’G とおく．
（ A’ , B’ は互いに素）
右の例から分かるように，12と18の最小公倍数を求めるときに，最大公約数6は2回も掛けずに1回だけ掛ける．
L=A’B’G だから AB=GL 		例
12=2×6
18=3×6
のとき
2 , 3 は互いに素
[１以外の公約数がない]
6 は最大公約数


このとき，
L=2×3×6=36
AB=2×6×3×6=GL

[I]　　共通に割れるだけ割っていく方法

　最大公約数を求める１つの方法は，共通な数で割れるだけ割っていく方法です．
　このとき，共通に割れる数の積が最大公約数です．
最小公倍数を求める方法は，これと同様ですが，割った数と残った数を掛けます．
例　次の例で，12 , 18 の最大公約数は 6，18 , 27 の最大公約数は 9 です．
　また，12 , 18 の最小公倍数は 36，18 , 27 の最小公倍数は 54 です．


【問題１】
　２数42, 28の最大公約数G，最小公倍数Lを求めてください．（正しい組合せを選んでください．）

1G=2, L=1176 2G=7, L=70


3G=14,L=84 4G=14,L=168



【問題２】
　２数60, 72の最大公約数G，最小公倍数Lを求めてください．（正しい組合せを選んでください．）

1G=12, L=60 2G=12, L=360


3G=60, L=360 4G=60, L=4320

.
※３つ以上の数について最大公約数と最小公倍数を求めるときは，「共通に割れる」という言葉の意味が変わります．最大公約数を求めるときには，「全部に共通」に割り切れなければ進んではいけませんが，最小公倍数を求めるときには，「一部でも割れたら割り」，他はそのまま残します．
例
（参考）
〇次のプログラムは，３つの数A,B,Cの最大公約数Gと最小公倍数Lを求めるものです．３つの空欄（各々７桁以下の整数とします．）を埋めてボタンを押してください．
A=，B=，C=
の最大公約数，最小公倍数を

[求める]．[消去]
【問題３】
　次の計算をもとにして，３数24, 36, 54の最大公約数を求めてください．
2
) 24 , 36 , 54

3
) 12 , 18 , 27

4
6
9


12 23 36 412 436



【問題４】
　次の計算は，３数4, 6, 9の最小公倍数を求める計算の途中経過を示したものです．x, yに当てはまる数を答えてください．
3
) 4 , 6 , 9

2
) x , 2 , 3

2
1
y


1x=4/3, y=3/2 2x=1, y=1


3x=2, y=3 4x=4, y=3




[II] 　素因数分解を利用して共通な指数を探す方法

　最大公約数，最小公倍数を求めるもう１つの方法は，素因数分解を利用する方法です．高校では通常この方法が用いられます．
○　最大公約数を求めるには，
「共通な素因数に」「一番小さい指数」をつけます．
（指数とは，52の2のように累乗を表わす数字のことです．）
（解説）
　例えば，a=216, b=324の最大公約数を求めるには，
　最初に，a, bを素因数分解して，
a=2333, b=2234
の形にします．
◇　素因数2について，23と22の
「公約数」は，1, 2, 22
「最大公約数」は，22
このように，公約数の中で最大のものは，23と22のうちの，小さい方の指数2を付けたものになります！

「最大公約数」
⇒「共通な素因数に最小の指数」を付けます

◇　同様にして，素因数3について，33と34の
「公約数」は，1, 3, 32, 33
「最大公約数」は，33

◇　結局，a=2333, b=2234の最大公約数は2233=108

○　最小公倍数を求めるには，
「全部の素因数に」「一番大きな指数」をつけます．
（解説）
　例えば，a=216, b=1620の最小公倍数を求めるには，
　最初に，a, bを素因数分解して，
a=2333, b=22345
の形にします．
◇　素因数2について，23と22の
「公倍数」は両方の倍数になっている数だから，23が入るものでなければなりません．
「公倍数」は23, 24, 25,　26, ...
「最小公倍数」は23

◇　同様にして，素因数3について，33と34の
「公倍数」は，34, 35, 36, 37, ...
「最小公倍数」は，34

◇　ところが，素因数5については，aには入っていなくてbには入っています．この場合に，両方の倍数になるためには，5の倍数でなければなりません．
「公倍数」は5, 52, 53, ...
「最小公倍数」は5

◇　結局，a=2333, b=22345の最小公倍数は23345=3240

このように，公倍数の中で最小のものは，
◇23と22のうちで大きい方の指数3を付けたもの
◇33と34のうちで大きい方の指数4を付けたもの
◇素因数5については，ないもの50と１つあるもの51のうちで大きい方の指数1を付けたもの
となります．

⇒素因数5の場合を考えてみると，「最小公倍数」を作るためには，「すべての素因数」を並べなければならないことがわかります．

「最小公倍数」⇒「すべての素因数に最大の指数」を付けます
【例題１】
　a=75とb=315の最大公約数G，最小公倍数Lを求めてください．
（解答）
　はじめに，a, bを素因数分解します．
a=3×52
b=32×5×7
　最大公約数を求めるためには，「共通な素因数」3, 5に「最小の指数」1, 1を付けます．
G=31×51=15
　最小公倍数を求めるためには，「すべての素因数」3, 5, 7に「最大の指数」2, 2, 1を付けます．
L=32×52×7=1575
【例題２】
　a=72とb=294の最大公約数G，最小公倍数Lを求めてください．
（解答）
　はじめに，a, bを素因数分解します．
a=23×32
b=21×31×72
　最大公約数を求めるためには，「共通な素因数」2, 3に「最小の指数」1, 1を付けます．
G=21×31=6
　最小公倍数を求めるためには，「すべての素因数」2, 3, 7に「最大の指数」3, 2, 2を付けます．
L=23×32×72=3528
【問題５】
　２数20, 98の最大公約数Gと最小公倍数Lを求めてください．

1G=2, L=490 2G=2, L=980


3G=4, L=49 4G=4, L=70 5G=4, L=490



【問題６】
　２数a=22×33×52, b=22×32×7の最大公約数Gと最小公倍数Lを求めてください．（指数表示のままで答えてください）

1G=22×32, L=24×35


2G=22×33, L=24×35


3G=22×32, L=22×33×52×7


4G=22×32×52×7, L=24×35×52×7




[III]　ユークリッドの互除法による方法　（発展学習）

　上に示した2つの方法は，「共通な約数が分かる場合」「素因数分解できる場合」に使えますが，そもそも何で割り切れるかが分からないような場合には，次に示す第３の方法（ユークリッドの互除法）で行うことができます．（高校では平成２５年度新教育課程から習うようになりました．最小公倍数は最大公約数を用いて， AB=GL から求められます．）
簡単な例 　３６と２７の最大公約数を求めるとき（何で割り切れるか分からないものとして考える）
３６，　２７，　９，　１８，　９，　９
（大きい方から小さい方を引き，小さい方の数と引いてできた数で同様に引いていく．同じ数字が並んだら答．）
（簡単な説明）
　大きい順に並べて A , B とする．
　（ア） A=B のときは，その値が最大公約数です．
　（イ） A>B のとき，A−B=R とおくと，A , B の最大公約数はB , R の最大公約数と等しくなります．(*)
　これを用いて，A , B の替わりに B , R を考えると，常に小さな数字の組となります．
A , Bが与えられた有限の整数である限り，この引き算は必ず有限回で終わります．
等しくなったら減りませんが，そのときは（ア）により，その数が最大公約数です．
　(*)の理由
A , B の最大公約数を G とすると，A=A’G , B=B’G だから，G は R=A−B=A’G−B’G=(A’−B’)G の約数．
　もし，B , R に G よりも大きな約数 G’ があるとすると，A=B+R=B”G’ + R”G’=(B”+ R”)G’ となって，A , B の最大公約数が G という仮定に反する．
　よって，A , B の最大公約数はB , R の最大公約数と等しくなる．
※　実際に使うときは，同じ数を何回も引くことは「割り算」をして「余り」を求めることと同じなので，「小さい方の数」と「余り」で次の組を作っていくと速く求められる．
　数学の教科書では，この余りを利用する方法で解説されている．（互いに割り算をしていくのだから「互除法」と呼ばれる）
「A を B で割った余りを R とするとき，A , B の組の替わりに B , R の組を考え，R=0 となったときの B が最大公約数」とされている．上記の説明は，これを分かりやすく書き換えたもの．（この意味では，次のプラグラムは筆者独自のいわば「互減法」で説明していることになります）

■　次のプログラムは，上で説明したユークリッド互除法を用いて最大公約数と最小公倍数を求めるものです．正の整数を２つ入力して［求める］ボタンを押してください．（各々７桁以下の整数とします．）

と
の最大公約数，最小公倍数を [求める]．[消去]

○　最大公約数 G=_　途中経過 ↓
（途中経過の表示は10000個まで）
○　最小公倍数（ AB=GL から求める）↓
L=_
○　高校の教科書のやり方で，最大公約数を求めるときに，次の数を「割り算の余り」で求める場合の途中経過（Internet Explorer, Safari以外では，はみ出した部分はスクロールバーで見ます）

※　素因数分解の結果が分かる次のような２数を用いて，ユークリッド互除法による最大公約数，最小公倍数の計算結果を確かめることができる．
例　 1763=41×43 , 1927=41×47 → G=41
例　 152963=1013×151 , 783049=1013×773 → G=1013
例　 6171373=532×133 , 1513733=53×134
　　　 → G=53×133=116441
【練習用】
１．次の２数の最大公約数を筆算で求めてください．次に上のプログラムで確かめてください．（各々数回の引き算でできます．）
(1) 296, 185 (2) 371, 265 (3) 553, 237

２．次の分数を約分してください．（分母と分子の最大公約数をユークリッドの互除法で求めて，それで約分するとよい）
(1)　　[ ? ]

(2)　　[ ? ]

(3)　　[ ? ]

...（携帯版）メニューに戻る

...メニューに戻る

■［個別の頁からの質問に対する回答］[最大公約数と最小公倍数について／17.4.19］
素因数分解なんて、高校生は、出来ていて当然な物なのに私は、忘れていました。問題集の解説を見ても出来るのが当たり前。という進め方でずっと悩んでいたのですが、これでスッキリ出来ました！ 有難うございました
＝＞［作者］：連絡ありがとう．筆者もつい最近まで，中学校の教科書での最大公約数と最小公倍数に関する取り扱いは薄過ぎるのではないか感じていました．この項目に弱いのはあなただけの問題ではないかもしれません．
■［個別の頁からの質問に対する回答］[最大公約数と最小公倍数について／17.3.21］
三と4の最小公倍数は0ですか？
＝＞［作者］：連絡ありがとう．その頁の下端に最大公約数と最小公倍数を求めるプログラムがありますので，それを使ってください．ただし，トンチ問答をしているのではないので，三やⅢではなく，半角数字の3と4を使わなければなりません．→12