まず、用語を整理しておきます。
二つ以上の整数の公倍数は最小公倍数の倍数である
$l$を$a,b,c,\cdots$の最小公倍数、$m$を$a,b,c,\cdots$の任意の公倍数とする。
$m=ql+r,\quad0\leq r< l$
と表すと、$r=m-ql$である。$m$も$ql$も$a$の倍数なので$r$は$a$の倍数。これを$b,c,\cdots$にも適用して、$r$が$a,b,c,\cdots$の公倍数であることがわかる。ここで、$0\leq r< l$だったので、$r=0$。よって、$m=ql$であり、公倍数は最小公倍数の倍数であることが分かる。
二つ以上の整数の公約数は最大公約数の約数である
$m$を$a,b,c,\cdots$の最大公約数、$d$を$a,b,c,\cdots$の任意の公約数とする。
背理法で証明する。つまり、$m$が$d$で割り切れないとする。これは$m=dq+r$と書ける($1\leq r< |d|$)。
$a=ma'=da''$
$b=mb'=db''$
$\dots$
とおく。ここで、$a',b',c',\cdots$のすべてが$\pm 1$でない$d$のある約数(これを$\alpha$と書くことにする)で割り切れるとすれば、$|m\alpha|$の方が$m$よりも大きい公約数になるので矛盾。よって$m=dq+r$は$d$の倍数。ゆえに、$r$は$d$の倍数であるが、$1\leq r < d$であることに矛盾。
よって背理法より、$d$は$m$の約数である。
$a,b$の最小公倍数を$l$、最大公約数を$m$とすれば、
$$ab=lm$$
が成り立つ($a>0,b>0$とする)
定理1より、$ab$は$l$の倍数なので$ab=dl$とかける。
$l$は$a,b$の公倍数なので、$l=ax=by$とかける。$ab=dl$に代入して、$b=dx, a=dy$である。よって$d$は$a,b$の公約数である。
よって定理2より$m=de$とかける。ここで、$m$は$a$と$b$の公約数なので、$b=dx, a=dy$より、$e$は$x$と$y$の公約数である。よって、$x=ex',y=ey'$として$l=ax=by$に代入すると、$l=eax'=eby'$。もしも$e>1$なら、$l/e< l$が$a,b$の公倍数になるが、これは矛盾。よって$e=1$。ゆえに$ab=lm$が成り立つ。
$a,b,c,\cdots$の最大公約数を$(a,b,c,\cdots)$という記号で書き表すことにします。
$(a,b)=1$のとき、$a,b$を互いに素と言います。
$a,b$が互いに素で、かつ$bc$が$a$の倍数ならば、$c$は$a$の倍数である。
定理3を使うと、$(a,b)=1$より、$a,b$の最小公倍数は$ab$である。
今、$bc$は$a$の倍数なので$bc$は$a,b$の公倍数。よって$bc$は$ab$の倍数。ゆえに$bc/ab=c/a$は整数で、$c$が$a$で割り切れることが分かった。