最大公約数と最小公倍数の関係
2つの整数 $a,b$ の最大公約数を $G$ ，最小公倍数を $L$ とすると，整数 $a’,b’$ を用いて $a=Ga’ , b=Gb’$ と表せ，
[Ⅰ] $a’$ と $b’$ は互いに素
[Ⅱ] $L=Ga’b’$
[Ⅲ] $ab=GL$
が成り立つ。
証明
[Ⅰ] $a,b$ は，最大公約数 $G$ と整数 $a’,b’$ を用いて $a=Ga’,b=Gb’$ と表せる。ここで， $a’,b’$ が共通の素因数 $p$ ( $p \geqq 2$ )を持つとすると， $a,b$ はともに $pG$ の倍数となるから，最大公約数が $G$ より大きくなり矛盾。よって， $a’,b’$ は互いに素な整数である。
[Ⅱ] $a,b$ の公倍数を $l$ とすると， $l$ は $a$ の倍数であり， $b$ の倍数でもあるから， $\displaystyle \frac{l}{a} , \frac{l}{b}$ すなわち $\displaystyle \frac{l}{Ga’} , \frac{l}{Gb’}$ は整数である。これより， $l$ は $G,a’,b’$ を因数に持つ。よって， $a,b$ の最小公倍数 $L$ は $G,a’,b’$ を因数に持つ最小の正の整数であるから， $L=Ga’b’$ である。
[Ⅲ] [Ⅱ]を用いると， $ab=Ga’ \cdot Gb’=G \cdot (Ga’b’)=GL$