次: ユークリッドの互除法 上: 約数と倍数 前: 約数と倍数

最大公約数と最小公倍数

定義 2
     整数$a$が$b$の倍数であるとは， $a=bq$となる整数$q$が存在することと定める． このとき$b$は$a$の約数という. 除法の定理によって，$a$が$b$の倍数であることは， $a$を$b$で割った余りが0であることと同値である．■

さらに，公約数，公倍数が定義される．

定義 3
     二つ以上の整数 $a,\ b,\ c,\ \cdots$ に共通な倍数をそれらの整数の公倍数という． 0は常に公倍数である． それを除けば公倍数の絶対値は $a,\ b,\ c,\ \cdots$ のいずれの絶対値よりも小さくはないので， 公倍数の中に正で最小のものがある． それを最小公倍数(least common multiple 略して L.C.M.)という．

二つ以上の整数 $a,\ b,\ c,\ \cdots$ に共通な約数をそれらの整数の公約数という． 1は常に公約数である． 公約数の絶対値は $a,\ b,\ c,\ \cdots$ のいずれの絶対値よりも大きくはないので， 公約数の中に最大のものがある． それを最大公約数(greatest common measure 略して G.C.M.)という．■

最大公約数が1であるとき，その2数は互いに素であるという． また整数$a$と$b$の最大公約数を座標などと混同する恐れのないときは $(a,\ b)$と書く．$(12,\ 32)=4$のように用いる．

定理 2

(1)

二つ以上の整数の公倍数は，最小公倍数の倍数である．

(2)

二つ以上の整数の公約数は，最大公約数の約数である．

(3)

$a,\ b$ の最小公倍数を $l$ ，最大公約数を $d$ とすれば $ab=dl$ ．

(4)

$a,\ b$ が互いに素で，他の整数 $c$ と $b$ との積 $bc$ が $a$ で 割りきれるなら，実は $c$ が $a$ で割りきれる．■

証明
(1)     $a,\ b,\ c,\ \cdots$ の最小公倍数を $l$ とし, $m$ を任意の公倍数とする． $m$ を $l$ で割った商を $q$ ，余りを $r$ とすると

$$m=ql+r,\ \quad 0 \le r<l$$

となる． $l$ も $m$ も $a$ の倍数であるから $l=al',\ m=am'$ とおくと

$$r=m-ql=a(m'-ql')$$

より, $r$ は $a$ の倍数である．同様に $b,\ c,\ \cdots$の倍数でもあり， $r$ は $a,\ b,\ c,\ \cdots$ の公倍数となる．ところが $l$ は正で最小の公倍数 であったから，もし $r$ が0でないとすると, $l$ より小さい正の公倍数がある ことになり, $l$ の最小性に反する．

$$∴\quad r=0$$

つまり $m$ は $l$ の倍数である．
(2)     $a,\ b,\ c,\ \cdots$ の最大公約数を $d$ とし, $m$ を任意の公約数とする． $l$ を $d$ と $m$ の最小公倍数とする． $a$ は $m$ の倍数であり， $d$ の倍数である．つまり $m$ と $d$ の公倍数であるから(1)より $a$ は $l$ の 倍数である．同様に $b,\ c,\ \cdots$も $l$ の倍数である． つまり $l$ は $a,\ b,\ c,\ \cdots$ の公約数である． $d$ が最大の公約数なので，

$$l\le d$$

一方, $l$ は$d$ と $m$ の最小公倍数なので $d\le l$

$$∴\quad l=d$$

$d$ と $m$ の最小公倍数 $l$ が $d$ に一致した．$d$ は $m$ の倍数， つまり任意の公約数 $m$ は最大公約数 $d$ の約数である．
(3)    $l$ は $a,\ b$ の最小公倍数であるから適当な整数$a'$と$b'$を用いて，

$$l=ab'=ba'$$

とおける． $ab$ は $a,\ b$ の公倍数だから(1)から $ab$ は $l$ の倍数である．

$$ab=ml$$

とする．よって

$$ab=ml=ma'b,\ \quad ab=ml=mab'$$

$$∴\quad a=ma',\ b=mb'$$

つまり $m$ は $a,\ b$ の公約数である．(2)より最大公約数$d$の約数なので， $d=me$とおける．

一方 $d$ は $a,\ b$ の最大公約数なので $a=da'',\ b=db''$ とおける．よって

$$a=da''=mea'',\ b=db''=meb''$$

一方，$a=ma',\ b=mb'$であるから$ma'=mea''$，$mb'=meb''$が成り立つ．

$$∴\quad a'=ea'',\ b'=eb''$$

その結果，

$$l=ab'=aeb'',\ l=a'b=ea''b$$

$$∴\quad \dfrac{l}{e}=ab''=a''b$$

ところがこれは $\dfrac{l}{e}$ が $a,\ b$ の公倍数であることを示している． $l$ が最小の公倍数なのでその最小性により $e=1$ ．

$$∴\quad m=d\quad つまり\quad ab=dl$$

(4)    $a,\ b$ の最大公約数が 1 なので $a,\ b$ の最小公倍数は $ab$ である． 仮定から $bc$ は $a$ の倍数であり，したがって $a$ と $b$ の公倍数である． よって $bc$ は $ab$ の倍数であり，

$$\dfrac{bc}{ab}=\dfrac{c}{a}\quad が整数$$

つまり$c$ は $a$ の倍数である．□

この定理の証明において，前節の「除法の定理」が基本定理として用いられてることが わかる．日頃当然のように論証で使っていることが,「除法の定理」を基礎に厳密に示される．

整数 $a,\ b,\ c,\ \cdots$ の最大公約数を，座標と混同する恐れのないときは $(a,\ b,\ c,\ \cdots)$ と書く．

整数 $a,\ b,\ c,\ \cdots$ の最大公約数が1であることを簡単に「公約数をもたない」という． この場合， $(a,\ b,\ c,\ \cdots)=1$ ． 特に二つの整数 $a,\ b$ が公約数をもたないとき，つまり $(a,\ b)=1$のとき， $a,\ b$ は互いに素であるという．

次: ユークリッドの互除法 上: 約数と倍数 前: 約数と倍数