整除と余りのある割り算

整数における整除

自然数の演算についての課では、自然数 $b$ が別の自然数 $a$ を割り切るといい、$b \mid a$ と書くのは、$a$ が $b$ の倍数であるときであった。この定義はそのまま整数に拡張される。整数の構成は整数についての課で学ぶ。整数 $b$ が整数 $a$ を割り切るとは、$a$ が $b$ とある整数との積であることをいう。その課は次の単元に属する。ここでは整数を先取りして用い、そこで基礎づけられる整数の算術と順序の規則を証明なしに認める。すなわち、符号の規則、整数に自然数を掛けても不等式の向きが保たれること、積の中の 零でない因数は簡約できること、そして整数とは自然数、$0$、自然数の反数のことであることである。これらの証明には自然数から整数を構成することが必要だが、その構成はこの課の内容を何も使わないので、循環は生じない。

また、$b$ は $a$ の約数である、$a$ は $b$ の倍数である、ともいう。定義から、いくつかの極端な場合がただちに従う。$0$ はすべての整数の倍数である。$0 = b \cdot 0$ だからである。数 $1$ と $-1$ はすべての整数を割り切る。そして $0$ が割り切るのは $0$ だけである。$0 \cdot k = 0$ がすべての $k$ について成り立つからである。さらに、$a = bk$ は $-a = b(-k)$ とも $a = (-b)(-k)$ とも同値である。したがって $a$ と $-a$ は同じ約数をもち、$b$ と $-b$ は同じ数を割り切る。そのため、実際には自然数の約数を調べれば十分である。

整除の性質

すべての整数 $a$、$b$、$c$、$d$、$x$、$y$ について次の性質が成り立ち、その証明は定義に帰着する：

1. 反射律：$a \mid a$。$a = a \cdot 1$ だからである。
2. 推移律：$a \mid b$ かつ $b \mid c$ ならば $a \mid c$。実際、$b = ak$ かつ $c = bl$ ならば $c = a(kl)$ である。
3. 一次結合：$d \mid a$ かつ $d \mid b$ ならば $d \mid ax + by$。これは次の命題で証明する。
4. 有界性：$b \mid a$ かつ $a > 0$ ならば $-a \leq b \leq a$。$b > 0$ の場合を示せば十分である。このとき $a = bk$ で $k$ は自然数であり、$k \geq 1$ だから $a = b + b(k - 1) \geq b$ が成り立つ。
5. 自然数における反対称律：$a$ と $b$ が自然数で、$a \mid b$ かつ $b \mid a$ ならば $a = b$。有界性から $a \leq b$ と $b \leq a$ が得られるからである。

有界性からは、今後しばしば用いる帰結が得られる。零でない整数の約数は有限個しかない。すべての性質のうち三番目が最も実り豊かであり、完全な主張と証明をともに覚えておくとよい。

この性質を逆向きに読むと、約数を除外するのに役立つ。$d$ が $a$ を割り切り $b$ を割り切らないならば、$a + b$ を割り切らない。もし割り切るなら、差 $(a + b) - a = b$ も割り切ることになるからである。