■最大公約数と最小公倍数
○ 最大公約数,最小公倍数とは

 2つ以上の正の整数に共通な約数(公約数)のうち最大のものを最大公約数といいます.
  例 1218 の公約数は,1,2,3,6 で, 6 が最大公約数

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

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

 この頁では,求め方を3通り紹介する.(中学校では,[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数の最大公約数 G,最小公倍数 L を求めなさい.
(1)  42 , 28
G= , L=

[採点する] [やり直す] [help]
(2)  60 , 72
G= , L=

[採点する] [やり直す] [help]
.
 3つ以上の数について最大公約数と最小公倍数を求めるときは,「共通に割れる」という言葉の意味が変わります.最大公約数を求めるときには,「全部に共通」に割り切れなければ進んではいけませんが,最小公倍数を求めるときには,「一部でも割れたら割り」,他はそのまま残します.
問題2
次の計算において,ア〜オに入る数を求めなさい.
ア=
 
イ=
ウ=
エ=
オ=
 

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

 最大公約数を求めるもう1つの方法は,素因数分解を利用する方法です.高校ではこの方法が用いられます.

 このとき,「共通な素因数に」「一番小さい指数」をつけたものが最大公約数です.(指数とは,522 のように累乗を表わす数字のことです.)

 最小公倍数を求めるには,「全部の素因数に」「一番大きな指数」をつけます.  
問題3
次の計算において,ア〜イに入る数を求めなさい.
ア=
イ=
 

問題4 次の各組の数について最大公約数 G と最小公倍数 L を求めよ.(空欄を埋めよ.計算結果は1つの数字に直さなくてよい.指数が1になるときは,通常の答案では書かなくてもよいが,ここでは1と書くものとする.) [採点する] [やり直す]
(1) 233758 , 223552
G=235 , L=235
      

(2) 2358 , 2235
G=2 , L=235
    

(3) 233254 , 223·53 , 223252

G=235 , L=235
      

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

 上に示した2つの方法は,「共通な約数が分かる場合」「素因数分解できる場合」に使えますが,そもそも何で割れるか分からないような場合には,次に示す第3の方法(ユークリッドの互除法)で行うことができます.(高校では平成25年度新教育課程から習うようになりました.最小公倍数は最大公約数を用いて, 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 の最大公約数と等しくなる.

※ 実際に使うときは,同じ数を何回も引くことは「余り」を求めることと同じなので,「小さい方の数」と「余り」で次の組を作っていくと速く求められる.
 数学の教科書では,この余りを利用する方法で解説されている.「AB で割った余りを R とするとき,A , B の組の替わりに B , R の組を考え,R=0 となったときの B が最大公約数」とされている.上記の説明は,これを分かりやすく書き換えたもの.
■ 次のプログラムは,左で説明したユークリッド互除法を用いて最大公約数と最小公倍数を求めるものです.正の整数を2つ入力して[求める]ボタンを押してください.(各々7桁以下の整数とします.)


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

○ 最大公約数 G=_ 途中経過 ↓
(途中経過の表示は10000個まで)
○ 最小公倍数( AB=GL から求める)↓
L=_

※ 素因数分解の結果が分かる次のような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
.