初等整数論 (3)公約数と公倍数
$A~$を可換環、$a_1,\dots,a_n\in A~$とする。
$a_1,\dots,a_n~$すべての約元となる元を$~a_1,\dots,a_n~$の公約元という。
また、$a_1,\dots,a_n~$すべての倍元となる元を$~a_1,\dots,a_n~$の公倍元という。
$a_1,\dots,a_n~$のすべての約元の倍元となる公約元、つまり \[ {}^{\forall}d:a_1,\dots,a_nの約元,d\mid g \] を満たす公約元$~g\in A~$を$~a_1,\dots,a_n~$の最大公約元という。
また、$a_1,\dots,a_n~$のすべての倍元の約元となる公倍元を$~a_1,\dots,a_n~$の最小公倍元という。
$A~$が$~\mathbb{Z}~$のときこれらは特に公約数・公倍数・最大公約数・最小公倍数という。
ただし、$\mathbb{Z}~$において最大公約数・最小公倍数というときそれは正のものとする。
$g,g'~$が$~a_1,\dots,a_n~$の最大公約元ならば$~g\sim g'~$である。
最小公倍元についても同様のことが言える。
$g~$は$~a_1,\dots,a_n~$の公約元であり、$g'~$が$~a_1,\dots,a_n~$の最大公約元なので \[ g\mid g' \] が成り立つ。
同様にして、$g'\mid g~$となる。
よって、$g\sim g'~$である。
最小公約元についても全く同じ議論ができる。
$(1)~$ $a_1\cdots a_n=0~$でなければ$~a_1,\dots,a_n~$の最小公倍数が存在する。
$(2)~$ $a_1=\cdots=a_n=0~$でなければ$~a_1,\dots,a_n~$の最大公約数が存在する。
$(3)~$ $a_1,\dots,a_n~$の最大公約数・最小公倍数はそれぞれ存在すればただ一つである。
$(1)~$
$M~$を$~a_1,\dots,a_n~$の正の公倍数全体とする。
明らかに$~|a_1\cdots a_n|\in M~$なので、$M~$は空でない。
また、$M~$の元はすべて正である($0~$より大きい)ので、$M~$は下に有界である。
整数.定理20(8)(b)より、$M~$の最小元$~l~$がとれる。
$m~$を$~a_1,\dots,a_n~$の公倍数とする。
このとき、
\[
\begin{array}{ll}
m=ql+r & (0\le r\lt l)
\end{array}
\]
となる$~q,r~$がただ1つ存在する。
$m,l~$は$~a_1,\dots,a_n~$の公倍数なので、$m-ql=r~$も$~a_1,\dots,a_n~$の公倍数である。
$l~$は$~a_1,\dots,a_n~$の正の公倍数のうち最小のものなので、$r\lt l~$より$~r~$は正の公倍数ではない。
よって、$0\le r~$より$~r=0~$である。
したがって、$m=ql~$となり、$l\mid m~$である。
$(2)~$
仮定より$~a_i\neq0~$となる$~i\in\{1,\dots,n\}~$がとれる。
$D~$を$~a_1,\dots,a_n~$の正の公約数全体とする。
明らかに$~1\in D~$なので$~D~$は空でない。
任意に$~d\in D~$をとる。
このとき、$d\mid a_i~$であるので、$db=a_i~$となる$~b\in\mathbb{Z}~$がある。
$|b|\ge1~$なので、$d=d\cdot1\le d|b|=|a_i|~$となる。
したがって、$D~$は上に有界となる。
整数.定理20(8)(a)より、$D~$の最大元$~g~$がとれる。
$d~$を$~a_1,\dots,a_n~$の公約数であるとする。
$d=0~$のときは明らかなので、$d\neq0~$とする。
$l~$を$~g,d~$の最小公倍数とする。
$a_1,\dots,a_n~$はすべて$~g,d~$の公倍数になっているので、各$~i=1,\dots,n~$に対して$~l\mid a_i~$となる。
つまり、$l~$は$~a_1,\dots,a_n~$の公約数であり、$g\le l~$となる。
$g~$は$~a_1,\dots,a_n~$の公約数のうち最大のものなので$~g=l~$となる。
$l~$は$~d~$の倍数なので、$d\mid g~$となる。
$(3)~$
$g,g'~$を$~a_1,\dots,a_n~$の最大公約数とする。
命題8より$~g\sim g'~$なので、$g'=g~$または$~g'=-g~$である。
$\mathbb{Z}~$における最大公約数は正のもののみを考えるので$~g'=g~$でなければならない。
最小公倍数についても同様の議論で示される。
つまり、任意の$~c\in\mathbb{Z}~$に対して、次は同値である。 \begin{align} (1)~& {}^{\exists}x_1,\dots,x_n\in\mathbb{Z}~\mathrm{s.t.}~a_1x_1+\cdots+a_nx_n=c\\ (2)~& g\mid c \end{align}
$(-g')\mathbb{Z}=g'\mathbb{Z}~$なので、うまくとり$~g'\ge0~$であるとする。
$a_1,\dots,a_n~$の公約数$~d~$を任意にとる。
このとき、各$~i=1,\dots,n~$に対して$~db_i=a_i~$となる$~b_i\in\mathbb{Z}~$がある。
\[ a_1\mathbb{Z}+\cdots+a_n\mathbb{Z}\ni a_1x_1+\cdots+a_nx_n=d(b_1x_1+\cdots+b_nx_n)\in d\mathbb{Z} \] となるので、$g'\mathbb{Z}=a_1\mathbb{Z}+\cdots+a_n\mathbb{Z}\subset d\mathbb{Z}~$となる。
$g'\in g'\mathbb{Z}\subset d\mathbb{Z}~$なので、$d\mid g'~$である。
よって、$g'~$は$~a_1,\dots,a_n~$の最大公約数なので$~g'=g~$である。