倍数と約数
$\newcommand{\NN}{\mathbb{N}}$ $\newcommand{\ZZ}{\mathbb{Z}}$ $\newcommand{\QQ}{\mathbb{Q}}$ $\newcommand{\RR}{\mathbb{R}}$ $\newcommand{\CC}{\mathbb{C}}$ $\newcommand{\LCM}{\mathrm{LCM}}$ $\newcommand{\abs}[1]{\left\lvert#1\right\rvert}$ $\newcommand{\wenvert}[1]{\left\lvert\left\lvert#1\right\rvert\right\rvert}$ $\newcommand{\mathmod}[1]{\ \left(\mathrm{mod}\ #1\right)}$
本稿においては初等整数論のうち、除法の原理について述べ、倍数と約数およびそれらに関連する概念について述べる。
商と剰余
定理1.1（除法の原理）
任意の整数 $n$ と、任意の正の整数 $a$ に対して、次の$2$つの条件が成立するような整数 $q, r$ が一意的に存在する。
- $n=qa+r.$
- $0\leq r\leq a-1.$
$q, r$ をそれぞれ $n$ を $a$ で割った商、剰余（または余り）という。
これは $\ZZ$ がEuclid整域であることをいっている。
Proof.
- $(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$ は一意的に定まる。
□倍数と約数
定義2.1（倍数と約数）
$2$つの整数 $m, n$ に対して、 $n=dm$ となる整数 $m$ が存在するとき、
- $n$ は $m$ の倍数、
- $m$ は $n$ の約数、
- $m$ は $n$ を割り切るあるいは整除する、
- $n$ は $m$ で割り切れる
といい、$m\mid n$ であらわす。
定理2.2
- $(1)$ 任意の整数 $n$ に対して $\pm n\mid \pm n, \pm 1\mid n$ かつ $n\mid 0$.
- $(2)$ $a, b, c$ が整数で $a\mid b, a\mid c$ のとき任意の整数 $k, \ell$ に対して $a\mid (kb+\ell c)$.
- $(3)$ $a, b$ が整数で $a\mid b$ のとき任意の整数 $n$ に対して $an\mid bn$. さらに $d$ が $a$ の約数ならば $a/d\mid b/d$.
- $(4)$ $a, b, c$ が整数で $a\mid b, b\mid c$ のとき $a\mid c$.
- $(5)$ $a, b$ が整数ならば $a\mid b \Longleftrightarrow a\mid -b \Longleftrightarrow -a\mid b \Longleftrightarrow -a\mid b$.
- $(6)$ $a, b$ が整数で $a\mid b$ のとき $d\mid an$ となる任意の整数 $n, d$ に対して $(an/d)\mid (bn/d)$.
- $(7)$ $a\mid b\mid n$ のとき $(n/b)\mid (n/a)$.
- $(8)$ $a\mid b, b\neq 0$ のとき $\abs{a}\leq \abs{b}$.
- $(9)$ $n\mid 1$ のとき $n=\pm 1$, また $a\mid b, b\mid a$ のとき $b=\pm a$.
Proof.
- $(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}$.
定理2.3
$S$ が $0$ でない整数を少なくとも$1$つ含む整数の集合で、$n\in S$ ならば $n$ の倍数も $S$ に含まれ、 $m, n\in S$ ならば $m+n$ も $S$ に含まれているとする。 このとき $S$ に含まれる最小の正の整数を $a$ とすると、$S$ は $a$ の倍数全体の集合と一致する。
このことは、$\ZZ$ が単項イデアル整域であることをいっている。 より一般に、単項イデアル整域の条件より、Euclid整域は単項イデアル整域である。
Proof.
$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$ の倍数でなければならないことがわかる。
□定義2.4（公倍数と公約数）
$a_1, a_2, \ldots, a_n$ を整数とする。すべての $a_i$ の倍数である数を $a_1, a_2, \ldots, a_n$ の公倍数、すべての $a_i$ の約数である数を $a_1, a_2, \ldots, a_n$ の公約数という。 $a_1, a_2, \ldots, a_n$ の最小の正の公倍数を $a_1, a_2, \ldots, a_n$ の最小公倍数といい $\LCM[a_1, a_2, \ldots, a_n]$ であらわす。$a_1, a_2, \ldots, a_n$ の最大の公約数を $a_1, a_2, \ldots, a_n$ の最大公約数といい $\gcd[a_1, a_2, \ldots, a_n]$ であらわす。
$\gcd(a_1, a_2, \ldots, a_n)=1$ のとき $a_1, a_2, \ldots, a_n$ は互いに素であるといい、どのような $i, j (1\leq i<j\leq n)$ をとっても $\gcd(a_i, a_j)=1$ であるとき $a_1, a_2, \ldots, a_n$ はどの$2$つも互いに素、あるいは対ごとに互いに素であるという。
定理2.5
$d\neq 0$ が $a, b$ の公約数であるとき $\gcd(a/d, b/d)=\gcd(a, b)/\abs{d}$. とくに $\gcd(a/\gcd(a, b), b/\gcd(a, b))=1$.
Proof.
定理2.6（初等整数論の基本定理）
$a, b, n$ を整数とする。 $a, n$ が互いに素なとき、$n\mid ab \Longleftrightarrow n\mid b$.
Proof.
$n\mid b$ ならば $n\mid ab$ となることは定理2.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 (2)から $e, f, s, t$ が整数で $as, at$ が $n$ の倍数ならば $a(es+ft)$ も $n$ の倍数となる。 よって $ab$ が $n$ の倍数である整数 $b$ 全体の集合は定理2.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$ となる。
□定理2.7
$n\mid ab\Longleftrightarrow n/\gcd(a, n)\mid b$.
Proof.
公倍数と公約数に関するその他の事実
以下の命題は、定理2.6から導かれる素因数分解の一意性からすぐにわかるが、 素因数分解を用いなくても、定理2.6および定理2.7から直接導くことができる。
命題3.1
$\LCM[a, b]\gcd(a, b)=ab$.
Proof.
$\LCM[a, b]=ak$ とおくと 定理2.7より $b\mid ak\Longleftrightarrow b/\gcd(a, b)\mid k$ であるから $k=b/\gcd(a, b)$ つまり $\LCM[a, b]=ab/\gcd(a, b)$.
□命題3.2
$a, b$ が $n$ を割り切るとき $\LCM[a, b]$ も $n$ を割り切る。
Proof.
$n=ak$ とおくと、$b\mid n=ak$ なので定理2.7より $b/\gcd(a, b)\mid k$ つまり $$\LCM[a, b]=\frac{ab}{\gcd(a, b)}\mid (ak)=n$$ となる。
□命題3.3
$a, b$ の公約数は $\gcd(a, b)$ を割り切る。
Proof.
$d$ が $a, b$ の公約数ならば $ab/d=a(b/d)=b(a/d)$ は $a, b$ の公倍数なので $\LCM[a, b]$ は $ab/d$ を割り切る。よって定理2.2 (7)より $\gcd(a, b)=ab/\LCM[a, b]$ は $d$ で割り切れる。
□命題3.4
$\gcd(a, N)=\gcd(b, N)=1$ ならば $\gcd(ab, N)=1$.
Proof.
$d=\gcd(ab, N)$ とおく。$\gcd(a, N)=1$ かつ $d\mid N$ だから $\gcd(a, d)=1$ となる。 一方 $d\mid ab$ だから $d\mid b$ となる。 しかし $\gcd(b, N)=1$ かつ $d\mid N$ だから $\gcd(b, d)=1$ となる。よって $\gcd(ab, N)=d=1$ である。
□
定理3.5
$N, k, a, b$ が整数で $k\geq 0, N^k=ab$ かつ $\gcd(a, b)=1$ ならば $a=\pm M^k, b=\pm L^k$ となる整数 $M, L$ が存在する。
Proof.
$d=\gcd(a, N), a=da_1, N=dN_1$ とおく。定理2.5より $\gcd(a_1, N_1)=1$ である。 $ab=N^k$ より $a_1 b=N^k/d=d^{k-1} N_1^k$ となるが $d\mid a, \gcd(a, b)=1$ だから $\gcd(d, b)=1$ である。 $b\mid d^{k-1} N_1^k$ であるから、定理2.6を繰り返し用いて $b$ は $N_1^k$ を割り切ることがわかる。
一方 $\gcd(a_1, N_1)=1$ かつ $N_1^k\mid a_1 b$ より $N_1^k$ は $b$ を割り切る。よって定理2.2 (9)より $b=\pm N_1^k$. $N=dN_1$ より $a=N^k/(\pm N_1^k)=\pm d^k$.
□
Euclidの互除法とBezoutの補題
与えられた$2$つの数の最大公約数を実際に求めるには、Euclidの互除法という高速な計算方法がある。 命題3.1より与えられた$2$つの数の最小公倍数は最大公約数を用いてあらわすことができるから、 与えられた$2$つの数の最小公倍数を求める実用的な計算方法も得られたことになる。
Euclidの互除法
与えられた2つの整数 $a\geq b>0$ について $a_0=a, a_1=b$ とし $$\begin{split} a_0= & q_1 a_1+a_2 (0\leq a_2<a_1), \\ a_1= & q_2 a_2+a_3 (0\leq a_3<a_2), \\ \ldots \\ a_{k-1}= & q_k a_k+a_{k+1} (0\leq a_{k+1}<a_k), \\ \ldots \end{split}$$ となる整数 $q_1, a_2, q_2, a_3, \ldots$ を $a_{s+1}=0$ となるまで繰り返しとっていくと、 $a_{s-1}=q_s a_s$, $a_{s+1}=0$ となる $s$ が必ず存在する、さらにその場合 $a_s=\gcd(a, b)$ となる。
Proof.
$a_{n+1}=0$ となる $n$ が存在しないと仮定すると $b=a_1>a_2>\cdots \geq 0$ より、$0\leq a_{b+2}\leq b+1-(b+2)<0$ となり、矛盾するから、 $a_{n+1}=0$ となる $n$ は必ず存在する。
そこでそのような最小の $n$ を $s$ とおくと $a_{s-1}=q_s a_s$ より $a_s\mid a_{s-1}$ となる。 $1\leq k\leq s$ かつ $a_s\mid a_k, a_{k+1}, \ldots, a_s$ とすると $a_{k-1}=q_k a_k+a_{k+1}$ も $a_s$ の倍数だから 数学的帰納法より $a=a_0, b=a_1, \ldots, a_s$ はすべて $a_s$ の倍数となる。とくに $a_s$ は $a, b$ の公約数である。
一方、$a_0=a, a_1=b$ は $\gcd(a_0, a_1)=\gcd(a, b)$ で割り切れる。 $a_0, a_1, \ldots, a_k$ が $\gcd(a, b)$ で割り切れるとき $a_{k+1}=a_{k-1}-q_k a_k$ も $\gcd(a, b)$ で割り切れる。 よって 数学的帰納法より $a=a_0, b=a_1, \ldots, a_s$ はすべて $\gcd(a, b)$ の倍数となる。 とくに $a_s$ は $\gcd(a, b)$ の倍数である。
以上のことより $a_s=\gcd(a, b)$ となる。
□Euclidの互除法にあらわれる各 $a_i (0\leq i\leq s)$ は $m_i a+n_i b (m_i, n_i\in\ZZ)$ の形にあらわすことができる。 さらに $m_k, n_k$ は $q_1, q_2, \ldots, q_{k-1}$ から計算できる。 実際 $a_0=a, a_1=b$ で、かつ $a_0, a_1, \ldots, a_k$ が $m_i a+n_i b (m_i, n_i\in\ZZ)$ の形にあらわすことができたとき $$a_{k+1}=a_{k-1}-q_k a_k=(m_{k-1} a+n_{k-1} b)-q_k(m_k a+n_k b)=(m_{k-1}-q_k m_k) a+(n_{k-1}-q_k n_k)b$$ となる。とくに $\gcd(a, b)=ma+nb$ となる整数 $m, n$ がとれる。 より一般に、次のBezoutの補題（代数曲線の交点に関するBezoutの定理とは別の定理である）が成り立つ。
Bezoutの補題
$a_1, a_2, \ldots, a_k$ を任意の $k$ 個の整数 とする。このとき $$a_1 x_1+a_2 x_2+\cdots +a_k x_k=n$$ となる整数 $x_1, x_2, \ldots, x_k$ が存在する $\Longleftrightarrow \gcd(a_1, a_2, \ldots, a_k)\mid n$.
Proof.
$d=\gcd(a_1, a_2, \ldots, a_k), a_i=d b_i$ とおく。 $$a_1 x_1+a_2 x_2+\cdots +a_k x_k=n$$ となる整数 $x_1, x_2, \ldots, x_k$ が存在するとき、 $$n=d(b_1 x_1+b_2 x_2+\cdots +b_k x_k)$$ より $n$ は $d=\gcd(a_1, a_2, \ldots, a_k)$ の倍数である。
$$a_1 x_1+a_2 x_2+\cdots +a_k x_k=m, a_1 y_1+a_2 y_2+\cdots +a_k y_k=n$$ となる整数 $x_1, x_2, \ldots, x_k, y_1, y_2, \ldots, y_k$ が存在するとき、任意の整数 $s, t$ について $$a_1 (sx_1+ty_1)+a_2 (sx_2+ty_2)+\cdots +a_k (sx_k+ty_k)=sm+tn$$ となるから、 $$a_1 z_1+a_2 z_2+\cdots a_k z_k=sm+tn$$ となる $z_1, z_2, \ldots, z_k$ がとれる。よって定理2.3より $$a_1 x_1+a_2 x_2+\cdots +a_k x_k=n$$ となる整数 $x_1, x_2, \ldots, x_k$ が存在するような最小の正の $n$ を $n_0$ とおくと $$\exists x_1, x_2, \ldots, x_k \in \ZZ [a_1 x_1+a_2 x_2+\cdots +a_k x_k=n]\Longleftrightarrow n_0 \mid n$$ となる。 $x_i=1, x_j=0 (j\neq i)$ のとき $a_1 x_1+a_2 x_2+\cdots +a_k x_k=a_i$ となるから、 $n_0$ は $a_1, a_2, \ldots, a_k$ の公約数である。しかし先に示したことから $n_0$ は $\gcd(a_1, a_2, \ldots, a_k)$ の倍数なので $n_0=\gcd(a_1, a_2, \ldots, a_k)$.
□なお、Bezoutの補題から定理2.7を示すこともできる。 実際 $d=\gcd(a, n)$ とおくと $sa+tn=d$ となる整数 $s, t$ がとれる。 $n\mid ab$ のとき $ab=kn$ とおくと $$kd=k(sa+tn)=ska+tkn=ska+tab=a(sk+tb)$$ より $k$ は $a/d=a/\gcd(a, n)$ の倍数であるから 定理2.2 (6)より $b=kn/a$ は $(na/d)/a=n/d$ の倍数である（逆に $b$ が $n/d$ の倍数ならば $ab=(a/d)n$ は $n$ の倍数である）。
参考文献
定理2.6およびBezoutの補題に関する議論は Trygve Nagell, Introduction to Number Theory, John Wiler & Sons, Inc. New York, 1951, Section 1.4, p.p.14--15 を、 定理3.5の証明は W. Sierpi\'{n}ski, Elementary Theory of Numbers, North-Holland, 2nd. Ed. edited by A. Schinzel, 1988, Section 1.6, p. 13 を参考とした。
