約数と倍数の基本的な定理
約数や倍数は小学生の頃から親しんできた概念です．本記事で紹介する定理の中には，当たり前に使われる定理もあります．しかし，いざ証明するとなると意外と難しいものもありますので，じっくりと取り組んでみましょう．可能であれば，自力で証明を考えてみるのも良いでしょう．
約数と倍数の定義
整数a，b，qが以下の等式，
a = bq (b \neq 0)
を満たすとき，aはbで割り切れるといい，また，aをbの倍数，bをaの約数といいます．
公倍数と公約数
二つ以上の整数に共通な倍数を公倍数といいます．また，正の公倍数のうち最小のものを最小公倍数(Least Common Multiple)といいます．
二つ以上の整数に共通な約数を公約数といいます．また，公約数のうち最大のものを最大公約数(Greatest Common Divisor)といいます．
二つの整数a，bの最大公約数を(a,b)と表すこともあります．例えば，(12,18) = 6といった表記です．
二つの整数の最大公約数が1であるとき，互いに素であるといいます．
これ以降の節では，公倍数や公約数に関する重要な定理を証明します．
公倍数は最小公倍数の倍数である
定理1．
二つ以上の整数の任意の公倍数は，最小公倍数の倍数である．
証明．
整数a, b, c, \cdots \cdots の最小公倍数をl，公倍数をmとする．
定理を証明するためには，m=lq+r (0 \leqq r < l)に関してr=0となることを示せば良い．m=lq+rを変形して，
r = m - lq
右辺m - lqはm，lどちらも，a,b,c, \cdots \cdots倍数なので，左辺のr もa,b,c, \cdots \cdotsの倍数，つまりrはa,b,c, \cdots \cdotsの公倍数である．lは最小公倍数であり，rの範囲は0 \leqq r < lであることから，r = 0である．
よって，二つ以上の整数の任意の公倍数は，最小公倍数の倍数である．
公約数は最大公約数の約数である
定理2．
二つ以上の整数の任意の公約数は，最大公約数の約数である．
証明．
整数a, b, c, \cdots \cdots の公約数dが最大公約数mの約数であることを示すために，dとmの最小公倍数がmであることを示す1dがmの約数である
\Leftrightarrow m=dqと表すことができる
\Leftrightarrow dとmの最小公倍数がmである．
dとmの最小公倍数をlとおく．
aはdの倍数であり，同時にmの倍数であるため，aはdとm公倍数である．lは最小公倍数なので，定理1より，aはlの倍数である2逆にいうとlはaの約数である．．同様に， b, c, \cdots \cdots はlの倍数なので，lはa, b, c, \cdots \cdots の公約数である．よって，
l \leqq m
一方で，lはdとmの公倍数なので，
l \geqq m
よって，l = mとなり，dとmの最小公倍数がmであることが示された．
その他の重要な定理
定理3．
自然数a，bの最小公倍数lを最大公約数mをとすると，以下の等式が成り立つ．
ab = lm
証明．
lは，aとbの公倍数より，
l = ab^{\prime} = a^{\prime}b
abはaとbの公倍数より，abはlの倍数である(定理1)ことから，
ab = dl
この式のlにl = ab^{\prime}とl = a^{\prime}bを代入して，
ab = dab^{\prime}
つまり，
b = db^{\prime}
また，ab = da^{\prime}bから
a = da^{\prime}
dはa，bの公約数であるから，
m=deとする．
a，bはmで割り切れるため，a^{\prime}，b^{\prime}はeで割り切れる3a = da^{\prime}の左辺をm，つまりdeで割り切れるので，右辺も割り切れる．b = db^{\prime}も同様．．
a^{\prime} = ea^{\prime \prime}，b^{\prime} = eb^{\prime \prime}とおいて，l = ab^{\prime} = a^{\prime}bに代入すると，
l = aeb^{\prime \prime} = ea^{\prime \prime}b
\frac{l}{e} = ab^{\prime \prime} = a^{\prime \prime}b
\frac{l}{e}はaとbの公倍数となるが，lはaとbの最小公倍数より，
e = 1
m=deより，m=d
また，ab = dlより，ab = lm
定理4．
互いに素である整数a，bに関して，bcがaで割り切れるなら，cはaで割り切れる．
証明．
定理3より，最大公約数が1なので，最小公倍数はabである．
また，bcはaの倍数なので，bcはaとbの公倍数である．したがって，定理1より，bcはabの倍数であることが分かる．
故に，\frac{bc}{ab} = \frac{c}{a}が整数になり，cはaで割り切れることが示された．
公約数に関する演習問題
演習問題．
(a,b) = (a-bq,b)であることを示せ．
（aとbの最大公約数とa-bqとbの最大公約数が等しいことを示せ）
余談
この記事は，高木貞治著『初等整数論講義 第2版』で学習した内容の再構築も兼ねています．
（定理の並びがほぼそのままかと思います）
また，最後の演習問題はユークリッドの互除法に繋がります．もちろん，ユークリッドの互除法の記事も書きます．間違いなく拡張ユークリッドの互除法もやりますし，当然プログラムも書きます．プログラミングにも繋がるなんて，令和7年度大学入試から必須となる「情報Ⅰ」の勉強もできてお得ですね．
