第 $1$ 章 初 等 整 数 論
$\S\ 2.$ 最大公約数，最小公倍数
$\boldsymbol{1.}$ 二つ以上の整数 $a$，$b$，$\cdots$ に共通な倍数（例えば積 $ab\cdots$ など）をそれらの整数の公倍数という．$0$ は公倍数ではあるが，それを除けば，公倍数の中に最も小さい（絶対値において）ものがある．それを最小公倍数という．二つ以上の整数 $a$，$b$，$\cdots\cdots$ に共通な約数（例えば $1$ など）をそれらの整数の公約数という．公約数は絶対値において $a$，$b$，$\cdots\cdots$ よりも大きいことはありえないから（$a$，$b$，$\cdots\cdots$ がすべて $0$ である場合を除けば），その中に最も大きなものがある．それを最大公約数という．
本節では最大公約数および最小公倍数に関する基本的の定理を述べる．事実としては周知であろうが，ときには無証明で受け入れられているようでもあるから，この際反省をして見るのも無用ではあるまい．理論上では，最小公倍数を先にする方が簡明である．
〔定理 $\boldsymbol{1.\ 3}$〕 二つ以上の整数の公倍数は最小公倍数の倍数である．
〔証〕 $a$，$b$，$c$，$\cdots\cdots$ の最小公倍数を$l$とし（ $l\gt0$ ），$m$ を任意の公倍数とする．さて
| $\hphantom{\left(定理\ 1.\ 2\right)}$ | \[m=ql+r,\hspace{1cm}0\leqq r\lt l\] | $\left(定理\ 1.\ 2\right)$ |
〔定理 $\boldsymbol{1.\ 4}$〕 二つ以上の整数の公約数は最大公約数の約数である．
〔証〕 $a$，$b$，$c$，$\cdots\cdots$ の最大公約数を $m$ とし，$d$ を任意の公約数とする．しからば $d$ が $m$ の約数であるというのは，$m$ と $d$ との最小公倍数が $m$ であるというのと同じである．いま $l$ を $m$ と $d$ との最小公倍数とする．さて仮定によって $a$ は $m$ の倍数であり，また $d$ の倍数であるから，$a$ は $m$，$d$ の公倍数，したがって $l$ の倍数である（定理 $1.\ 3$）．同様に $b$，$c$，$\cdots\cdots$ も $l$ の倍数である．故に $l$ は $a$，$b$，$c$，$\cdots\cdots$ の公約数である．故に $l\leqq m$．しかるに $l$ は $m$ の倍数であるから $l\geqq m$，故に $l=m$．
次の定理は二つの整数 $a$，$b$ に関するものである．
〔定理 $\boldsymbol{1.\ 5}$〕 $a$，$b$ の最小公倍数を $l$，最大公約数を $m$ とすれば，\[ab=lm.\]（ただし $a\gt0$，$b\gt0$，$l\gt0$，$m\gt0$ とする．）
〔証〕 $l$ は $a$，$b$ の公倍数であるから\[l=ab^\prime=ba^\prime\tag{$\ 1\ $}\]とする．さて $ab$ はもちろん $a$，$b$ の公倍数であるから，$ab$ は $l$ の倍数である（定理 $1.\ 3$）．よって\[ab=dl\tag{$\ 2\ $}\]とする．$\left(\ 1\ \right)$ から $l$ に代入して\[a=da^\prime,\hspace{5mm}b=db^\prime\tag{$\ 3\ $}\]を得る．故に $d$ は $a$，$b$ の公約数である．
よって $m=de$ とする（定理 $1.\ 4$）．しかるに $a$，$b$ は $m$ で割り切れるから，$\left(\ 3\ \right)$ において $a^\prime$，$b^\prime$ は $e$ で割り切れる．よって $a^\prime=ea^{\prime\prime}$，$b^\prime=eb^{\prime\prime}$ として $\left(\ 1\ \right)$ に代入すれば\[l=ab^{\prime\prime}e=ba^{\prime\prime}e.\]もしも $e\gt1$ ならば，$l/e\lt l$ が $a$，$b$ の公倍数になる．これは不合理である．故に $e=1$，したがって $m=d$．ゆえに $\left(\ 2\ \right)$ から $ab=lm$．
$a$，$b$，$c$，$\cdots\cdots$ の最大公約数を $\left(a,\ b,\ c,\ \cdots\cdots\right)$ なる記号で表わすことにする．
$a$，$b$，$c$，$\cdots\cdots$ が $\pm1$ 以外の公約数を有しないときには，略して $a$，$b$，$c$，$\cdots\cdots$ は公約数を有しないという．この場合には $\left(a,\ b,\ c,\ \cdots\cdots\right)=1$
特に二つの整数 $a$，$b$ が公約数を有しないときには，$a$，$b$ を互いに素ともいう．
次の定理はしばしば引用されるものであるから特に大切である．
〔定理 $\boldsymbol{1.\ 6}$〕 $\boldsymbol{\left(a,\ b\right)=1}$ で，かつ $\boldsymbol{bc}$ は $\boldsymbol{a}$ で割り切れるならば，$\boldsymbol{c}$ が $\boldsymbol{a}$ で割り切れる．
〔証〕 仮定によって $\left(a,\ b\right)=1$ であるから，$a$，$b$ の最小公倍数は $ab$ である（定理 $1.\ 5$）．
しかるに仮定によって $bc$ は $a$ の倍数，したがって $a$，$b$ の公倍数であるから $bc$ は $ab$ の倍数である（定理 $1.\ 3$）．
故に $bc/ab=c/a$ は整数，すなわち $c$ は $a$ で割り切れる．
実際に与えられた（正の）整数の最大公約数，または最小公倍数を求める方法は周知であるが，この際，念のためにその理論的の根拠をたたいておくのも無用であるまい．
〔問題 $\boldsymbol{1}$〕 $\left(a,\ b\right)=\left(a-qb,\ b\right)$
〔解〕 $m$ を $a$，$b$ の最大公約数とすれば，$m$ は $a-qb$ の約数，したがって $a-qb$，$b$ の公約数，したがって $\left(a-qb,\ b\right)$ の約数である（定理 $1.\ 4$）．
また $a-qb=a^\prime$ とすれば，$a=a^\prime+qb$ であるから，同様に $\left(a^\prime,\ b\right)$ は $\left(a,\ b\right)$ の約数である．
このように $\left(a,\ b\right)$ と $\left(a^\prime,\ b\right)$ とは，おのおのが他方の約数であるから，相等しい．
特に $a$ を $b$ で割った剰余を $c$ とすれば，$\left(a,\ b\right)=\left(b,\ c\right)$．また $b$ を $c$ で割った剰余を $d$ とすれば，$\left(b,\ c\right)=\left(c,\ d\right)$．このように進んで行けば $a\gt b\gt c\gt d\gt\cdots\cdots$ であるから，ついには剰余が $0$ になる．いま $c$ が $d$ で割り切れるとすれば，$\left(c,\ d\right)=\left(d,\ 0\right)=d$，すなわち $d=\left(a,\ b\right)$．これが Euclid の互除法である．
三つ以上の整数 $a$，$b$，$c$，$\cdots\cdots$，$l$ の最大公約数を求めるにも互除法を応用することができる．いまこれらの数のうち $a$ が最も小さいときは，$a$ で $b$，$c$，$\cdots\cdots l$ を割って，剰余を $b^\prime$，$c^\prime$，$\cdots\cdots$，$l^\prime$ とする．しからば問題 $1$ と同様に\[\left(a,\ b,\ c,\ \cdots\cdots,\ l\right)=\left(a,\ b^\prime,\ c^\prime,\ \cdots\cdots,\ l^\prime\right)\]剰余の中に $0$ があれば，それを $($ $)$ 内から省いてよい．さて $\left(a,\ b^\prime,\ c^\prime,\ \cdots,\ l^\prime\right)$ に同様の操作を行なう．そのとき除数にする最小数は $b^\prime$，$c^\prime\cdots$，$l^\prime$ の中の数で，それは $a$ よりも小である．この操作を継続すれば，毎回 $($ $)$ 内の最大数が減少するから，次第に剰余 $0$ が出てきて，ついには $($ $)$ 内にただ一つの数が残る．それがすなわち $\left(a,\ b,\ c,\ \cdots\cdots,\ l\right)$ である．剰余は絶対的最小剰余をとるのがよい．
〔例〕 $\left(629,\ 391,\ 255\right)=\left(119,\ -119,\ 255\right)=\left(119,\ 17\right)=17$．
〔問題 $\boldsymbol{2}$〕 三つ以上の整数の最小公倍数を求めるとき，それらの整数の一部分をその最小公倍数でおき換えてよい．例えば $a$，$b$，$c$，$\cdots\cdots$，$k$ の最小公倍数は $a$，$b$ の最小公倍数 $m$ と $c$，$\cdots\cdots$，$k$ との最小公倍数に等しい．
〔解〕 $a$，$b$，$c$，$\cdots\cdots$，$k$ の最小公倍数を $l$ とし，$m$，$c$，$\cdots\cdots$，$k$ の最小公倍数を $l^\prime$ とすれば，$l$ は $a$，$b$ の公倍数であるから，$m$ の倍数である（定理 $1.\ 3$）．$l$ はもとより $c$，$\cdots\cdots$，$k$ の倍数であるから $l$ は $m$，$c$，$\cdots\cdots$，$k$ の公倍数，したがって $l^\prime$ の倍数である．また $l^\prime$ は $m$ の倍数，したがって，$a$，$b$ の倍数，したがって $a$，$b$，$c$，$\cdots\cdots$，$k$ の公倍数，したがって $l$ の倍数である．このように $l$ は $l^\prime$ の倍数，$l^\prime$ は $l$ の倍数であるから $l=l^\prime$．二つの整数の最小公倍数は定理 $1.\ 5$ によって最大公約数から求められる．よって上記問題の定理を応用して任意数の整数の最小公倍数が求められる．