このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ
  • 追加された行はこの色です。
  • 削除された行はこの色です。
  • 最大公約数 へ行く。

*目次 [#o89d9819]

#contents

*最大公約数と最小公倍数 [#sb703453]

[定理]整数a,bに対して、次が成り立つ。~
(1)a,bの公倍数は、最小公倍数の倍数である。~
(2)a,bの公約数は、最大公約数の約数である。

[定理]自然数a,bの最大公約数をd、最小公倍数をmとすれば、ab=dmが成り立つ。

例:a=12,b=18でこの定理が成り立つことを確認する。

-d=GCD(12,18)=6
-m=LCM(12,18)=36

-左辺=ab=12・18
-右辺=dm=6・36 ◇

[定理]~
合成数a,bの素因数分解に現れる素数を合わせて、pSUB{1};,…,pSUB{n};とし、これらは互いに相異なるとする。~
このとき、a=Π[i=1;n]pSUB{i};SUP{e_i};、b=Π[i=1;n]pSUB{i};SUP{f_i};となる整数eSUB{i};≧0、fSUB{i};≧0を取ると、a,bの最大公約数と最小公倍数はそれぞれ次のように与えられる。

-d=Π[i=1;n]pSUB{i};SUP{min{e_i,f_i}};
-m=Π[i=1;n]pSUB{i};SUP{max{e_i,f_i}};
-d=Π[i=1;n]pSUB{i};SUP{min(e_i,f_i)};
-m=Π[i=1;n]pSUB{i};SUP{max(e_i,f_i)};

[証明]a,bの任意の正の公約数をdとする。

 このときdを素因数分解し、次のように表記できる。

d=Π[i=1;n]pSUB{i};SUP{g_i};

 各指数gSUB{i};は0≦gSUB{i};≦eSUB{i};かつ0≦gSUB{i};≦fSUB{i};を満たす。

 そのうちで最大のdは、この条件を満たす最大の指数gSUB{i};は、gSUB{i};=min{eSUB{i};,fSUB{i};}になる。これで前半のdに対する等式を示すことはできた。

 次は後半のmについて示す。これも同様に議論できる。

 a,bの任意の正の公倍数mを素因数分解は、pSUB{i};たち以外の素因数の積を1つにまとめてqと書けば、次のように表される。

m=qΠ[i=1;n]pSUB{i};SUP{h_i};

 各指数hSUB{i};はeSUB{i};≦hSUB{i};かつfSUB{i};≦hSUB{i};を満たす。ただし、pSUB{i};たち以外の素因数が存在しない場合はq=1とする。

 このとき、最小のmは、最小のqおよび上の条件を満たす最小の指数hSUB{i};であり、q=1、hSUB{i};=max{eSUB{i};,fSUB{i};}になる。 □

[別証](最小公倍数mに関する証明)

 ab=mdより、m=ab/dが成り立つ(d≠0のとき)。

 また、最大公約数の結果である「d=Π[i=1;n]pSUB{i};SUP{min{e_i,f_i}};」と「e+f=min{e,f}+max{e,f}」が成り立つ。

 よって、次のように式を展開できる。

m
=ab/d
=ab/Π[i=1;n]pSUB{i};SUP{min{e_i,f_i}};
=ab/Π[i=1;n]pSUB{i};SUP{e+f-max{e_i,f_i}};
=((Π[i=1;n]pSUB{i};SUP{e_i}・Π[i=1;n]pSUB{i};SUP{f_i};}/Π[i=1;n]pSUB{i};SUP{e+f};)×Π[i=1;n]pSUB{i};SUP{max{e_i,f_i}};
=1×Π[i=1;n]pSUB{i};SUP{max{e_i,f_i}};
=Π[i=1;n]pSUB{i};SUP{max{e_i,f_i}}; □

例:a=60,b=42のときの最大公約数dと最小公倍数mを求める。

 a,bを素因数分解すると次のようになる。

-a=60=2SUP{2};・3・5
-b=42=2・3・7

 よって、次のようにも表現できる。

-a=60=2SUP{2};・3SUP{1};・5SUP{1};・7SUP{0};
-b=42=2SUP{1};・3SUP{1};・5SUP{0};・7SUP{1};

 ここで、上記の定理を利用する。

-d=2SUP{min{2,1}};・3SUP{min{1,1}};・5SUP{min{1,0}};・7SUP{min{0,1}};=2SUP{1};・3SUP{1};・5SUP{0};・7SUP{0};=6
-m=2SUP{max{2,1}};・3SUP{max{1,1}};・5SUP{max{1,0}};・7SUP{max{0,1}};=2SUP{2};・3SUP{1};・5SUP{1};・7SUP{1};=420 ◇

 この定理は最大公約数や最大公倍数を求める公式としては理論的に重要であるが、素因数分解がわからないような大きな数に対しては実用的ではない。素因数分解に時間がかかる大きな数の場合は、ユークリッドの互除法を用いて最大公約数を求めてから、[定理]「整数a,bに対して、ab=GCD(a,b)LCM(a,b)が成り立つ」を用いて最小公倍数を求めた方が効率的である。


*最大公約数と整数 [#lcc50b4d]

[定理]2つの正整数r,m(ただし、r<m)について、~
(r,m)=1 ⇒ (m-r,m)=1

[証明](m-r.m)≠1と仮定する。

このとき、1以外の公約数dを持つので、&mimetex("m-r=dp, m=dq");(ただし、p,qはある整数)

第1式のmに第2式を代入すると、

&mimetex("dp-r=dp");~
&mimetex("d(q-p)=r");

一方、&mimetex("m=dq");

よって、(m,r)≠1となり、仮定に反する。

ゆえに、(m-r,m)=1 □

*参考文献 [#e16d601e]

-『工科系のための初等整数論入門 公開鍵暗号をめざして』