数a　最大公約数、最小公倍数について(整数の性質)

1　最大公約数と最小公倍数の定義

最大公約数:複数の共通の約数(公約数)の中で最大のもの

最大公約数:複数の共通の倍数(公倍数)の中で最小のもの

例えば以下の例題について考えてみよう。

例題)　72,126,180の最大公約数、最小公倍数を求めよ。

解説)　まず与えられた数を素因数分解する。

すると、72=2^3×3^2, 126=2×3^2×7, 180=2^2×3^2×5より、

72は2を3個,3を2個持ち

126は2を1個,3を2個,7を1個持ち、

また、180は2を2個,3を2個,5を1個持つ。

この3数に共通する素因数を最大分取り出すことで、最大公約数が得られる。よって、2を1個と3を2個取り出せば、それ以外に共通する素因数はない。よって2×3^2=18が最大公約数となる。

最小公倍数は、72の倍数かつ126の倍数かつ180の倍数となる最小の数

である。よってまず、この3数の公倍数となる条件を考える。

72の倍数になるには、最低でも2を3個,3を2個必要である。

126の倍数になるには、最低でも2を1個,3を2個, 7を1個必要である。

180の倍数になるには、最低でも2を2個,3を2個,5を1個必要である。

この3数の倍数になるには、最低でも2を3個,3を2個,5を1個,7を1個が必要。よって最小公倍数は2^3×3^2×5×7=2520である。

2　互いに素とは

互いに素:n個の整数の最大公約数が1であるとき、そのn個の整数は互いに素であるという。

例えば、4と10は、最大公約数が2のため互いに素ではないが、

3,6,8は互いに素である。

3　最大公約数、最小公倍数の数式化

2整数a,bの最大公約数をG、最小公倍数をLとすると、以下の式が成り立つ。

a=Ga', b=Gb'(a', b'は互いに素)

L=Ga'b'=ab'=a'b

ab=LG

a'b'=L/G

これらは、3つ以上の整数については必ずしも成り立つわけではないので注意しよう。