→ 携帯版は別頁 → 印刷用PDF版は別頁
■最大公約数,最小公倍数,ユークリッドの互除法

○ 最大公約数,最小公倍数とは
 2つ以上の正の整数に共通な約数(公約数)のうち最大のものを最大公約数といいます.
【例】
1218の公約数は,1,2,3,6 で,6が最大公約数
 2つ以上の正の整数の共通な倍数(公倍数)のうち最小のものを最小公倍数といいます.
【例】
23の公倍数は,6,12,18,24,... で,6が最小公倍数
.
最小公約数という言葉は使う値打ちがありません.なぜなら,公約数のうち一番小さい(正の)数は 1 に決まっているからです.

最大公倍数は決められません.なぜなら,大きな(正の)公倍数は,次の例で分かるように限りなくあるからです.
【例】
23の公倍数 : 6,12,18,24,30,36,...
○ 最大公約数,最小公倍数の求め方

 この頁では,求め方を3通り紹介する.[I][II]が小中学校の復習で,[III]が高校の教材になっています.
まず,最大公約数を次のいずれかの方法で求める.
 [I]  共通に割れるだけ割っていく方法
 [II]  素因数分解を利用して共通な指数を探す方法
 [III] ユークリッドの互除法による方法

[I][II]では最小公倍数を求める方法も示されるが,[III]のように最大公約数だけが求まるときは,右の関係式を用いて最小公倍数も求まる.
○ 2数A,Bの最大公約数をG,最小公倍数をLとおくと,
AB=GL
が成り立つ.
(証明)
A=A’G, B=B’Gとおく.
A’, B’は互いに素)
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]  共通に割れるだけ割っていく方法
 最大公約数を求める1つの方法は,共通な数で割れるだけ割っていく方法です.
 このとき,共通に割れる数の積が最大公約数です.
最小公倍数を求める方法は,これと同様ですが,割った数と残った数を掛けます.
 次の例で,12 , 18 の最大公約数は 618 , 27 の最大公約数は 9 です.
 また,12 , 18 の最小公倍数は 3618 , 27 の最小公倍数は 54 です.
【問題1】
 2数42, 28の最大公約数G,最小公倍数Lを求めてください.(正しい組合せを選んでください.)

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

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



【問題2】
 2数60, 72の最大公約数G,最小公倍数Lを求めてください.(正しい組合せを選んでください.)

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

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



 3つ以上の数について最大公約数と最小公倍数を求めるときは,「共通に割れる」という言葉の意味が変わります.最大公約数を求めるときには,「全部に共通」に割り切れなければ進んではいけませんが,最小公倍数を求めるときには,「一部でも割れたら割り」,他はそのまま残します.
【問題3】
 次の計算をもとにして,3数24, 36, 54の最大公約数を求めてください.
2
) 24 , 36 , 54

3
) 12 , 18 , 27

4
6
9


12 23 36 412 436



【問題4】
 次の計算は,3数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]  素因数分解を利用して共通な指数を探す方法
 最大公約数,最小公倍数を求めるもう1つの方法は,素因数分解を利用する方法です.高校では通常この方法が用いられます.
○ 最大公約数を求めるには,
「共通な素因数に」「一番小さい指数」をつけます.
(指数とは,522のように累乗を表わす数字のことです.)
(解説)
 例えば,a=216, b=324の最大公約数を求めるには,
 最初に,a, bを素因数分解して,
a=2333, b=2234
の形にします.
◇ 素因数2について,2322
「公約数」は,1, 2, 22
「最大公約数」は,22
このように,公約数の中で最大のものは,2322のうちの,小さい方の指数2を付けたものになります!

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

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

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

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

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

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

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

このように,公倍数の中で最小のものは,
2322のうちで大きい方の指数3を付けたもの
3334のうちで大きい方の指数4を付けたもの
◇素因数5については,ないもの50と1つあるもの51のうちで大きい方の指数1を付けたもの
となります.

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

「最小公倍数」⇒「すべての素因数に最大の指数」を付けます
【例題1】
 a=75b=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
【例題2】
 a=72b=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
【問題5】
 2数20, 98の最大公約数Gと最小公倍数Lを求めてください.

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

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



【問題6】
 2数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つの方法は,「共通な約数が分かる場合」「素因数分解できる場合」に使えますが,そもそも何で割れるか分からないような場合には,次に示す第3の方法(ユークリッドの互除法)で最大公約数を求めることができます.(最小公倍数は最大公約数を用いて, AB=GL から求められます.)
簡単な例  36と27の最大公約数を求めるとき(何で割り切れるか分からないものとして考える)
36, 27, 9, 18, , 
(大きい方から小さい方を引き,小さい方の数と引いてできた数で同様に引いていく.同じ数字が並んだら答.)
(簡単な説明)
 大きい順に並べて A, Bとする.
 (ア) A=Bのときは,その値が最大公約数です.
 (イ) A>Bのとき,A−B=Rとおくと,A, Bの最大公約数はB, Rの最大公約数と等しくなります.(*)
 これを用いて,A, Bの替わりにB, R を考えると,常に小さな数字の組となります.等しくなったら減りませんが,そのときは(ア)により,その数が最大公約数です.
 (*)の理由
A, Bの最大公約数をG とすると,A=A’G, B=B’G だから,GR=A−B=A’G−B’G=(A’−B’)Gの約数.
 もし,B, RGよりも大きな約数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を最大公約数とする方法」とされている.上記の説明は,これを分かりやすく書き換えたもの.


※ 素因数分解の結果が分かる次のような2数を用いて,ユークリッド互除法による最大公約数,最小公倍数の計算結果を確かめることができる.
例  1763=41×43 , 1927=41×47G=41
例  152963=1013×151 , 783049=1013×773G=1013
例  6171373=532×133 , 1513733=53×134
    → G=53×133=116441
【練習用】 次の2数の最大公約数を筆算で求めてください.次に上のプログラムで確かめてください.(各々数回の引き算[または割り算]でできます.)
(1) 296, 185 (2) 371, 265 (3) 553, 237
■ 次のプログラムは,左で説明したユークリッド互除法を用いて最大公約数と最小公倍数を求めるものです.正の整数(半角数字で!)を2つ入力して[求める]ボタンを押してください.(各々7桁以下の整数とします.)


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

○ 最大公約数 G=_ 途中経過 ↓
(途中経過の表示は10000個まで)
○ 最小公倍数( AB=GL から求める)↓
L=_
○ 高校の教科書のやり方で,最大公約数を求めるときに,次の数を「割り算の余り」で求める場合の途中経過(Internet Explorer, Safari以外では,はみ出した部分はスクロールバーで見ます)
[話題] ユークリッドの互除法の”天敵”- -フィボナッチ数列
 幾つか試してみるとわかるように,ユークリッドの互除法を使えば最大公約数が数回の割り算で求められます.しかし,商が1(A=B+R)となる組ばかりになる場合には,なかなか数字が減っていかないので,長〜い計算を要することとなります.
 すなわち,a1=a2=1, an+2=an+1+anによって作られる数列(フィボナッチ数列と呼ばれ,次の数を前2つの数の和で決めていく)
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
から2つ(例えば5589)を選べばなかなか割り算が進まないので,2桁の数字なのに最大公約数が求まるまでに割り算を9回も行う必要があります.
= = 練習用 = =
 500以下の2つの自然数で,ユークリッドの互除法を使って最大公約数を求めるときに,割り算を10回以上行わなければならないものを幾つかあげてください.
(解答例)
(フィボナッチ数列の続きでは)377233
a1=1, a2=3, an+2=an+1+anとすれば,322199
a1=1, a2=4, an+2=an+1+anとすれば,411254

■[個別の頁からの質問に対する回答][最大公約数,最小公倍数について/17.5.17]
特に問題ないと思います、でも今の教科書にあまりあっていない気がします
=>[作者]:連絡ありがとう.最大公約数,最小公倍数については,小学校で1回習って,中学校ではもう習わず,高校1年生前半ではまだ習っていないはずなので,「今の教科書にあまりあっていない」というのは正常な感覚だと思います.・・・教科書ではこの項目は冷遇されているようです.
■[個別の頁からの質問に対する回答][最大公約数,最小公倍数について/16.12.5]
不定方程式をのせてほしいです
=>[作者]:連絡ありがとう.今は別のことで手がいっぱいですが,そのうち不定方程式の頁を作らなければならないと考えています.
(追伸)2017.1月 1次不定方程式の整数解ペル方程式を追加しました.

.