†[定理]整数a,bに対して、次が成り立つ。(1)a,bの公倍数は、最小公倍数の倍数である。(2)a,bの公約数は、最大公約数の約数である。[定理]自然数a,bの最大公約数をd、最小公倍数をmとすれば、ab=dmが成り立つ。例:a=12,b=18でこの定理が成り立つことを確認する。◇[定理]合成数a,bの素因数分解に現れる素数を合わせて、p1,...,pnとし、これらは互いに相異なるとする。このとき、a=Π[i=1;n]pie_i、b=Π[i=1;n]pif_iとなる整数ei≧0、fi≧0を取ると、a,bの最大公約数と最小公倍数はそれぞれ次のように与えられる。d=Π[i=1;n]pimin(e_i,f_i)m=Π[i=1;n]pimax(e_i,f_i)[証明]a,bの任意の正の公約数をdとする。このときdを素因数分解し、次のように表記できる。d=Π[i=1;n]pig_i各指数giは0≦gi≦eiかつ0≦gi≦fiを満たす。そのうちで最大のdは、この条件を満たす最大の指数giは、gi=min{ei,fi}になる。これで前半のdに対する等式を示すことはできた。次は後半のmについて示す。これも同様に議論できる。a,bの任意の正の公倍数mを素因数分解は、piたち以外の素因数の積を1つにまとめてqと書けば、次のように表される。m=qΠ[i=1;n]pih_i各指数hiはei≦hiかつfi≦hiを満たす。piたち以外の素因数が存在しない場合はq=1とする。このとき、最小のmは、最小のqおよび上の条件を満たす最小の指数hiであり、q=1、hi=max{ei,fi}になる。□[別証](最小公倍数mに関する証明)ab=mdより、m=ab/dが成り立つ(d≠0のとき)。最大公約数の結果である「d=Π[i=1;n]piSUP{min{e_i,f_i}};」と「e+f=min{e,f}+max{e,f}」が成り立つ。よって、次のように式を展開できる。例:a=60,b=42のときの最大公約数dと最小公倍数mを求める。a,bを素因数分解すると次のようになる。a=60=22・3・5b=42=2・3・7よって、次のようにも表現できる。a=60=22・31・51・70b=42=21・31・50・71ここで、上記の定理を利用する。◇この定理は最大公約数や最大公倍数を求める公式としては理論的に重要であるが、素因数分解がわからないような大きな数に対しては実用的ではない。素因数分解に時間がかかる大きな数の場合は、ユークリッドの互除法を用いて最大公約数を求めてから、[定理]「整数a,bに対して、ab=GCD(a,b)LCM(a,b)が成り立つ」を用いて最小公倍数を求めた方が効率的である。(m-r,m)=1[証明](m-r.m)≠1と仮定する。よって、(m,r)≠1となり、仮定に反する。数学講座(2365d)。