← PC用は別頁

== 最大公約数,最小公倍数,ユークリッドの互除法 ==

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

※最大公倍数は決められません．なぜなら，大きな（正の）公倍数は，次の例で分かるように限りなくあるからです．
【例】
2と3の公倍数　：　6,12,18,24,30,36,...
○　最大公約数，最小公倍数の求め方
　この頁では，求め方を３通り紹介する．[I][II]が小中学校の復習で，[III]が高校の教材になっています．
まず，最大公約数を次のいずれかの方法で求める．
　[I]　　共通に割れるだけ割っていく方法
　[II] 　素因数分解を利用して共通な指数を探す方法
　[III]　ユークリッドの互除法による方法

[I][II]では最小公倍数を求める方法も示されるが，[III]のように最大公約数だけが求まるときは，次の関係式を用いて最小公倍数も求まる．
○　２数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]　　共通に割れるだけ割っていく方法

　最大公約数を求める１つの方法は，共通な数で割れるだけ割っていく方法です．
　このとき，共通に割れる数の積が最大公約数です．
最小公倍数を求める方法は，これと同様ですが，割った数と残った数を掛けます．
例　次の例で，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

　３つ以上の数について最大公約数と最小公倍数を求めるときは，「共通に割れる」という言葉の意味が変わります．最大公約数を求めるときには，「全部に共通」に割り切れなければ進んではいけませんが，最小公倍数を求めるときには，「一部でも割れたら割り」，他はそのまま残します．
例
【問題３】
　次の計算をもとにして，３数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の最大公約数を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を最大公約数とする方法」とされている．上記の説明は，これを分かりやすく書き換えたもの．
【練習用】　次の２数の最大公約数を筆算で求めてください．次に上のプログラムで確かめてください．（各々数回の引き算［または割り算］でできます．）
(1) 296, 185 (2) 371, 265 (3) 553, 237

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

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

○　最大公約数 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

［話題］　ユークリッドの互除法の”天敵”- -フィボナッチ数列
　幾つか試してみるとわかるように，ユークリッドの互除法を使えば最大公約数が数回の割り算で求められます．しかし，商が１（A=B+R）となる組ばかりになる場合には，なかなか数字が減っていかないので，長〜い計算を要することとなります．
　すなわち，a1=a2=1, an+2=an+1+anによって作られる数列（フィボナッチ数列と呼ばれ，次の数を前２つの数の和で決めていく）
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
から２つ（例えば55と89）を選べばなかなか割り算が進まないので，２桁の数字なのに最大公約数が求まるまでに割り算を９回も行う必要があります．
= = 練習用 = =
　500以下の２つの自然数で，ユークリッドの互除法を使って最大公約数を求めるときに，割り算を10回以上行わなければならないものを幾つかあげてください．
（解答例）
（フィボナッチ数列の続きでは）377と233
（a1=1, a2=3, an+2=an+1+anとすれば，322と199）
（a1=1, a2=4, an+2=an+1+anとすれば，411と254）

〇 gcd( )関数の使い方
　２つの正の整数a, bの最大公約数を表す関数gcd(a, b)を使うと，ユークリッドの互除法をうまく使うことができます．
　最大公約数の英語の略語がgcdなので，そのまんまの名前でキザな感じもしますが，数学Ａの教科書（Ｋ社）にも掲載されているちゃんとした関数です．
【例】
　36と27の最大公約数は9だから
gcd(36, 27)=9
ですが，ユークリッドの互除法を使って途中経過を書くと，次のようになります．
gcd(36, 27)
=gcd(9, 27)
=gcd(9, 0)
=9
←求めたいもの
←大きい方を余りに替える
←大きい方を余りに替える
←０でない最後の余りがgcd

【例題３】
　17と19の最大公約数をユークリッドの互除法を使って求めてください．
（解答）
gcd(17, 19)
=gcd(17, 2)
=gcd(1, 2)
=gcd(1,0)
=1
←問題をgcd関数で書く
←19÷17=1余り2
←17÷2=8余り1
←2÷1=2余り0
←０でない最後の余りがgcd


【問題７】
(1)
　123と117の最大公約数をユークリッドの互除法を使って求めてください．
解答を見る

(2)
　323と187の最大公約数をユークリッドの互除法を使って求めてください．
解答を見る

(3)

が既約分数であるかどうか調べてください.
解答を見る

(4)

が約分できるかどうか調べてください.
解答を見る

〇 文字式にgcd( )関数を使う場合
【例】
　右の例のように，文字式の割り算では，余りの次数は割る式の次数よりも小さくしなければならないので，商や余りに分数や負の係数が登場することがあります．
　ユークリッドの互除法を使って正の整数の最大公約数を求める計算では，「分数の係数は使わない」と決めるとよいでしょう．
　負の整数が登場する場合，一般には，7で割って-5余るとは、7で割って2余ることと読み替えることもできますが，ユークリッドの互除法では，a−bq=rのとき，a, bの最大公約数はb, rの最大公約数に等しいということを使っているだけだから，商qが整数であればa−bq=−rすなわちbq−a=rであっても事情は同じになります．そこで，負の整数−rが登場したら，正の整数rに戻せばよいでしょう．
　次のような問題で整数を表す文字nが含まれている場合，「通常の文字式の割り算とは異なり，整数の係数だけを使い，余りが負の整数になるときは符号を変えて正の整数に直す」とよいでしょう．
【例題４】
nを正の整数とするとき，
　
が既約分数であるかどうか調べてください.
（解答）
gcd(4n+3,7n+5)
=gcd(4n+3,3n+2)←文字式の除法と違い商を7/4にしない
=gcd(n+1, 3n+2)
=gcd(n+1, −1)
=gcd(n+1, 1) ←正の数に直す
=gcd(0,1)
=1
最大公約数が1だから既約分数…（答）
※途中経過を次のように行うこともできます
gcd(n+1, 3n+2)
=gcd(n+1, n)←商に2を立てた
=gcd(1, n)
=gcd(1,0)
=1
【例題５】
　nを正の整数とするとき，
　
が既約分数であるかどうか調べてください.
（解答）
gcd(4n+3,n+2)
=gcd(−5,n+2)
=gcd(5, n+2)
n+2が5の倍数である場合，すなわちn=5k−2=5m+3であるとき（n=3,8,13,...のとき），5で約分できます．それ以外の場合は既約分数になります．…（答）

【問題８】
(1)
　任意の自然数nに対して，
　
が既約分数になることを示してください.
解答を見る

(2)
　任意の自然数nに対して，
　
が既約分数になるかどうか調べてください.
解答を見る

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

...（PC版）メニューに戻る

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