倍数と約数

$(1)$ まず $n\geq 0$ の場合に、上記の2つの条件が成立するような整数 $q, r$ が存在することを数学的帰納法により証明する。

$n=0$ のとき、$q=r=0$ ととることができる。

$n\geq 1$ について $n-1=q_0 a+r_0, 0\leq r_0\leq a-1$ となる整数 $q_0, r_0$ が存在すると仮定する。
$0\leq r_0\leq a-2$ のとき $n=q_0 a+(r_0+1)$ より $q=q_0, r=r_0+1$ ととれる。
$r_0=a-1$ のとき $n=q_0 a+(a-1)+1=(q_0+1)a$ より $q=q_0+1, r=0$ ととれる。

$(2)$ $n\leq 0$ の場合、$(1)$ より $-n=q_0 a+r_0, 0\leq r_0\leq a-1$ となる整数 $q_0, r_0$ がとれる。
$r_0=0$ のとき $n=-q_0 a$ なので $q=q_0, r=0$ ととれる。
$1\leq r_0\leq a-1$ のとき $n=-q_0 a-r_0=(-q_0+1) a_0+q_0-r_0$ なので $q=-q_0+1, r=q_0-0$ ととれる。

$(3)$ 一意性を示す。$n=q_1 a+r_1=q_2 a+r_2$ かつ $0\leq r_1, r_2\leq a-1$ となる整数 $q_1, q_2, r_1, r_2$ が存在すると仮定する。
$q_1\neq q_2$ のとき
$$ \abs{(q_2 a+r_2)-(q_1 a+r_1)}=\abs{(q_2-q_1) a+(r_2-r_1)}\geq a\abs{q_2-q_1}-\abs{r_2-r_1}\geq a-(a-1)\geq 1$$
となって、$q_1 a+r_1 =q_2 a+r_2=n$ に矛盾する。よって $q_1=q_2$ である。
よって $r_1=n-q_1 a=n-q_2 a=r_2$ より $r_1=r_2$ である。したがって $q, r$ は一意的に定まる。

1. $n=\pm 1\times \pm n, -n=\mp 1\times \pm n$ （複号同順）、および $0=0n$.
2. $b=ma, c=na$ となる整数 $m, n$ をとると $kb+\ell c=kma+\ell na=(km+\ell n)a$ は $a$ の倍数。
3. $b=ma$ となる整数 $m$ をとると $bn=m(an)$ は $an$ の倍数。さらに $d$ が $a$ の約数ならば $b/d=m(a/d)$ は整数で $a/d$ の倍数。
4. $c=kb$ となる整数 $k$ がとれるので $(2)$ より $c$ も $a$ の倍数。
5. $b=ma\Longleftrightarrow -b=-ma\Longleftrightarrow -b=m\times (-a) \Longleftrightarrow b=(-m)\times (-a)$.
6. $(3)$ より $an\mid bn$ となるが、 $d\mid an$ なので再び $(3)$ より $(an/d)\mid (bn/d)$.
7. $b=am$ とおくと $n/a=nm/b$ は $n/b$ の倍数。
8. $b=am$ とおくと $b\neq 0$ より $m\neq 0$. よって $\abs{m}\geq 1$ なので $\abs{b}=\abs{a}\abs{m}\geq \abs{a}$.
9. $n\mid 1$ ならば $n\neq 0$ で、$(8)$ より $\abs{n}\leq 1$ だから $n=\pm 1$. また、$a\mid b, b\mid a$ ならば $(8)$ より $\abs{a}\leq \abs{b}\leq \abs{a}$ だから $\abs{a}=\abs{b}$.

$S$ に含まれる $0$ でない整数 $n$ をとる。$n<0$ ならば $-n\in S$ だから、$S$ は正の整数を少なくとも$1$つ含む。よって $S$ に含まれる最小の正の整数 $a$ がとれる。$a$ の倍数が $S$ に含まれることは仮定からすぐにわかる。

$n\in S$ ならば 除法の原理 より、$n=qa+r, 0\leq r\leq a-1$ となる整数 $q, r$ が存在する。
仮定より $r=n-qa$ も $S$ に含まれるが、$a$ のとり方より、$1\leq r\leq a-1$ のとき $r$ は $S$ に含まれない。
よって $r=0$ となり、$n$ は $a$ の倍数でなければならないことがわかる。

$m$ が $a/d, b/d$ の公約数ならば 定理2 より $dm$ は $a, b$ をともに割り切るから、 定理2 より $\abs{dm}$ も $a, b$ を割り切る。よって $\abs{dm}\leq \gcd(a, b)$ つまり $\abs{m}\leq \gcd(a, b)/\abs{d}$ となる。

さらに、$\gcd(a, b)/\abs{d}$ が $a/d, b/d$ を割り切ることは明らかだから、$\gcd(a/d, b/d)=\gcd(a, b)/\abs{d}$.

$n\mid b$ ならば $n\mid ab$ となることは 定理2 (4) からすぐにわかる。また、$n=0$ のとき $a=0$ または $b=0$ であるが、 $a, n$ が互いに素なので $a=\pm 1$ でなければならないから $b=0$ となって、定理は正しい。よって、以下 $n\neq 0$ かつ $a, n$ が互いに素で、$n\mid ab$ のとき $n\mid b$ となることを示す。

定理2 (2) から $e, f, s, t$ が整数で $as, at$ が $n$ の倍数ならば $a(es+ft)$ も $n$ の倍数となる。
よって $ab$ が $n$ の倍数である整数 $b$ 全体の集合は 定理3 の条件を満足するから、$ab$ が $n$ の倍数である整数 $b$ のなかで最小の正のもの $b_0$ をとると、$ab$ が $n$ の倍数であるとき $b$ は $b_0$ の倍数である。

$an$ は $n$ の倍数だから $b_0\mid n$ となる。$n=sb_0$ とおくと $sb_0=n$ は $ab_0$ を割り切るから $s$ は $a$ を割り切る。よって $s$ は $a, n$ をともに割り切るから $a, n$ の公約数である。しかし $\gcd(a, n)=1$ であるから $s=\pm 1$ つまり $b_0=\pm n$ である。

よって $n\mid ab$ ならば $\pm n=b_0\mid b$ であるから、$n\mid b$ となる。

定理4 より $\gcd(a/\gcd(a, n), n/\gcd(a, n))=1$ なので
初等整数論の基本定理 より $n/\gcd(a, n)\mid ab/\gcd(a, n)\Longleftrightarrow n/\gcd(a, n)\mid b$.
定理2 (3) より $n\mid ab\Longleftrightarrow n/\gcd(a, n)\mid b$.