初等整数論/整除性

倍数・約数

定義

整数$a,b$ について $a=bq$ なる 整数

$q$ が存在するとき、これを、「a は b の倍数」、「b は a の約数」、「a は b で割り切れる」という。記号で、$b|a$。

定理 1.1

この定理は基本的である。

$b|a_0,a_1,a_2,\cdots ,a_n$ のとき、$b|a_{0}x+a_{1}x+a_{2}x+\cdots +a_{n}x$

証明
$b|a_0,a_1,a_2,\cdots ,a_n$ より、 $b{q}_0=a_0,b{q}_1=a_1,\cdots$ とおく。すると、

$\begin{array}{cc}{a}_{0}x+a_{1}x+a_{2}x+\cdots +a_{n}x& =b{q}_{0}x+b{q}_{1}x+b{q}_{2}x+\cdots +b{q}_{n}x\\ & =bx(q_0+q_1+q_2+\cdots +q_n)\end{array}$

より、b の倍数であることから、$b|a_{0}x+a_{1}x+a_{2}x+\cdots +a_{n}x.$

除法の原理

これも整数論の根幹の部分を成す基本的かつ大事な定理である。

定理 1.2 (除法の原理)

任意の整数 $a,b>0$ が与えられたとき、$a=bq+r(0\leqq r<b)$ なる $q,r$ がただ一組に限って存在する。

証明
まずは存在することを証明する。そのために、まずは自然数についてを証明し、それを利用して負の数と 0 の場合を証明すれば整数全てを網羅できる。

$a$ についての数学的帰納法で証明する。

(i) $a=1$ のとき

$b=1$ ならば、$a=b1+0$ とすることで定理の主張を満たす。
$b>1$ ならば、$a=b0+1$ とすることで定理の主張を満たす。

(ii) $a=n$ のとき成り立つと仮定する

すなわち、$n=bq+r(0\leqq r<b)$ なる $q,r$ が存在する。

$0\leqq r<b-1$ ならば、$n+1=bq+(r+1)(0\leqq r+1<b)$ より n+1 でも正しい。
$r=b-1$ ならば、
$\begin{array}{ccc}n+1& =bq+r+1& =b(q+1)+0\end{array}$
となって、結局 n+1 の場合も正しい。

(i) (ii) によって数学的帰納法から、自然数について成り立つことが分かった。

次に、負数の場合である。

$a<0\Rightarrow -a>0$ であるので、先ほど証明したことから $-a=bq+r(0\leqq r<b)\cdots (1)$ なる $q,r$ が存在する。

$\begin{array}{cc}(1)& ⟺a=b(-q)+(-r)(-b<-r\leqq 0)\\ & ⟺a=b(-q)-b+(-r+b)(0<-r+b\leqq b)\end{array}$

よって、$0<-r+b<b$ ならば定理は正しい。そうではなく、$-r+b=b$ のときも、$-r+b=b⟺r=0$ であることから定理の主張を満たす。

最後に 0 の場合であるが、これは自明。

以上より全ての整数において除法の原理を満たす q, r が存在することが証明された。

次に、その唯一性を証明する。仮にとある整数 $a,b>0$ でこれが成り立たず、

$\begin{array}{cc}a& =bq+r(0\leqq r<b)\\ a& =b{q}^{\prime }+r^{\prime }(0\leqq r^{\prime }<b)\\ q& \ne q^{\prime }\vee r\ne r^{\prime }\end{array}$

だったとする。すると、

$\begin{array}{cc}(bq+r)-(b{q}^{\prime }+r^{\prime })=a-a& ⟺b(q-q^{\prime })+(r-r^{\prime })=0\\ & ⟺b(q-q^{\prime })=r^{\prime }-r\end{array}$

$\therefore b|r^{\prime }-r\cdots (2)$

$\begin{array}{cc}0\leqq r^{\prime }\wedge r<b& \Rightarrow r<r^{\prime }+b\\ & ⟺r-r^{\prime }<b\\ & ⟺r^{\prime }-r>-b\cdots (3)\\ \end{array}$

$\begin{array}{cc}0\leqq r\wedge r^{\prime }<b& \Rightarrow r^{\prime }<r+b\\ & ⟺r^{\prime }-r<b\cdots (4)\end{array}$

(2), (3), (4) より $r^{\prime }-r=0⟺r=r^{\prime }\cdots (5)$

したがって、再び $(bq+r)-(b{q}^{\prime }+r^{\prime })=a-a⟺b(q-q^{\prime })=0⟺b=0\vee q-q^{\prime }=0$

ここで、$b>0$ より、$q-q^{\prime }=0⟺q=q^{\prime }\cdots (6)$

(5), (6) は仮定に矛盾。したがって、唯一性が証明された。以上により除法の原理が証明された。

定義

先ほどの定理をそのまま用いると、q を 「a を b で割った商」、r を 「a を b で割った余り」という。またこれを、「b を法とした a の最小正剰余」ともいう。

例

$19=7\cdot 2+5$
$97=24\cdot 4+1$
$186=38\cdot 4+32$

なお、余りの範囲を $0\leqq r<b$ とせず、$-\frac{b}{2}\leqq r\leqq \frac{b}{2}(⟺r\leqq |\frac{b}{2}|)$ とすることもできる。これを、絶対最小剰余という。例えば、

$68=7\cdot 10-2$

がある。

公約数・公倍数

定義

2つ以上の数 a, b, ... について、a の約数であり、かつ b の約数であり、かつ、... という数を「a, b, ... の公約数」という。自然数の公約数のうち最大のものを「最大公約数」という。「g.c.d, gcd」などとも書かれ、gcd(a, b, ...)、または単に (a, b, ...) という記号で表す。

2つ以上の数 a, b, ... について、a の倍数であり、かつ b の倍数であり、かつ、... という数を「a, b, ... の公倍数」という。自然数の公約数のうち最小のものを「最小公倍数」という。「l.c.m, lcm, LCM」などとも書かれ、lcm[a, b, ...] という記号で表す。

特に、gcd(a, b) = 1 のとき、「a, b は互いに素である」、という。さらにここでは、3つ以上の数 a, b, c, ... については、gcd(a, b, c, ...) = 1 を「広義の互いに素」あるいは単に「互いに素」、3つ以上の数のうち任意の異なる2数をとっても互いに素であるとき、「狭義の互いに素」「対ごとに互いに素」「どの2つも互いに素」という。対ごとに互いに素な数の組は互いに素である。このような区別は一般的ではなく曖昧な部分もあるがここではこのように約束する。

例 84, 32 の最大公約数は 4, 記号で $\gcd (84,32)=4.$ または $(84,32)=4.$
189, 42 の最大公約数は 21, 記号で $(189,42)=21.$
230, 132, 91 の最大公約数は 23, 記号で $(230,132,91)=23.$

12 と 20 の最小公倍数は 60, 記号で $\text{lcm}[12,20]=60.$ 9, 21, 15 の最小公倍数は 315, 記号で $\text{lcm}[9,21,15]=315.$

6, 7 は互いに素。92, 15 は互いに素。3, 4, 5 は対ごとに互いに素である。4, 6, 7 は互いに素であるが、$(4,6)=2$ なので対ごとに互いに素ではない。6, 10, 15 は互いに素であるが、$(6,10)=2,(10,15)=5,(6,15)=3$ とどの2つをとっても互いに素ではない。

次に述べるものは直観的に考えて合っているもので、証明なしに受け入れられるものである。それを反省する意味でもここに証明を載せる。

定理 1.3

2つ以上の数の公倍数は最小公倍数の倍数である。

証明
2つ以上の数を a, b, ..., k とおく。公倍数は必ず存在する。なぜなら、全てをかけあわせたもの、$ab\cdots k$ は定義より公倍数であるからである。これが負ならば正に直すことで自然数の公倍数がみつかる。そのうち最小のものは存在する。よって最小公倍数は必ず存在する。

さて、ここで最小公倍数を l とおき、m は任意の公倍数とする。定理 1.2 に基づいて、

$m=lq+r,0\leqq r<l$

とおけば、$r=m-lq$

m も l も a, b, ... , k の倍数であるから、定理 1.1 によって r も a, b, ... , k の倍数、すなわち、公倍数である。ここで、l は正のもののうち最小のものだったから、$r=0$ となるしかなく、よって定理の正しいことが証明される。

定理 1.4

2つ以上の数の公約数は最大公約数の約数である。

証明
2つ以上の数を a, b, ..., k とおく。公約数は必ず存在する。なぜなら、1 は定義より公約数であるからである。また、それらの数のうち、最も大きい数を l とおくと、l + 1 以上の数は公約数ではない。よって公約数には最大のものは存在する。よって最小公倍数は必ず存在する。

さて、ここで最大公約数を m とおき、d は任意の公約数とする。また、m, d の最小公倍数を l とおく。仮定によって、a は m の倍数であり、d の倍数である。したがって、定理 1.3 によって、a は l の倍数である。同様に、b, c, ... , k も l の倍数。したがって、l は a, b, c, ... , k の公約数。したがって m は「最大」なので $l\leqq m.$ また、l は m の倍数であるから、$l\geqq m.$ 以上より、$l=m$ となり、d は m の約数であると分かった。

定理 1.5

任意の自然数 a, b について、$\gcd (a,b)=g,\text{lcm}[a,b]=l$ とすると、$ab=gl$

証明
仮定より、$l=a^{\prime }b=a{b}^{\prime }$ とおける。ab は a, b の公倍数である。したがって定理 1.3 によって $ab=dl\cdots (1)$ とおける。
先ほどの式をこれに代入して、$ab=d{a}^{\prime }b,ab=da{b}^{\prime }⟺a=d{a}^{\prime },b=d{b}^{\prime }\cdots$ つまり、d は a, b の公約数。定理 1.4 に基づいて、
$g=de\cdots (2)$とおく。仮定により、$g|a,b⟺de|d{a}^{\prime },d{b}^{\prime }⟺e|a^{\prime },b^{\prime }.$ したがって、$a^{\prime }=e{a}^{″},b^{\prime }=e{b}^{″}$ とおけば、最初の式に代入して

$l=a{b}^{″}e=b{a}^{″}e$ となるが、$e>1$ であると、$\frac{l}{e}(<l)$ が a, b の公倍数となり、l の最小性に反するため、e = 1 となるしかなく、(2) より $g=d.$ (1) より、$ab=gl.$

次の定理も、1.3, 1.4 とともに無条件で受け入れられている、非常に重要な定理である。

定理 1.6

$\gcd (a,b)=1$ のとき $a|bc⟺a|c$

証明
定理 1.5 より、a, b の最小公倍数は ab である。bc は a の倍数かつ b の倍数、したがって定理 1.3 によって $ab|bc⟺a|c.$

定理 1.3 のみを使って証明することもできる。a, b の最小公倍数は当然 b の倍数であるから kb とかける。ab は明らかに a, b の公倍数であるから定理 1.3 より kb の倍数である。よって a は k の倍数である。そこで $a=lk$ とおくと $kb=ab/l$ が a の倍数であるから $b/l$ は整数、つまり l は b の約数である。よって l は a, b の公約数でなければならないが仮定より l=1 つまり k=a でなければならない。したがって a, b の最小公倍数は ab である。bc は a の倍数かつ b の倍数、したがって定理 1.3 によって $ab|bc⟺a|c.$

定理 1.6 は次のように一般化される。

定理 1.6'

$a|bc⟺\frac{a}{\gcd (a,b)}|c$

証明
$a^{\prime }=a/\gcd (a,b),b^{\prime }=b/\gcd (a,b)$ とおくと $\gcd (a^{\prime },b^{\prime })=1$ なので定理 1.6 より $a|bc⟺a^{\prime }|b^{\prime }c⟺a^{\prime }|c.$