除法の原理

同義語：division algorithm除法の定理

概要

定義

整数 $a$ を $0$ でない整数 $b$ で割るとき、小学校の割り算と同じく「商」と「余り」が定まる。負の数まで含めて商と余りをただ 1 通りに決めるには、余りのとる範囲を指定しなければならない。除法の原理は、余りを $0$ 以上 $|b|$ 未満に限れば商と余りが存在してただ 1 組に定まることを主張する（DF04 §0.2。$b>0$ の場合は IR90 Chapter 1 にもある）。
以下、$\mathbb{N}=\{0,1,2,\dots\}$ は通常の順序で整列順序である、すなわち $\mathbb{N}$ の空でない部分集合は最小元をもつことを用いる。

除法の原理

$a,b$ を整数とし、$b\neq0$ とする。このとき
$$ a=qb+r,\qquad 0\le r<|b| $$
を満たす整数 $q,r$ がただ 1 組存在する。

存在：集合 $S:=\{a-kb\mid k\in\mathbb{Z}\}\cap\mathbb{N}$ を考える。$k:=-|a|\,b$ とおくと、$b^2\ge1$ より $a-kb=a+|a|\,b^2\ge a+|a|\ge0$ なので $S$ は空でない。$\mathbb{N}$ は整列順序なので $S$ は最小元 $r$ をもち、ある $q\in\mathbb{Z}$ について $r=a-qb$、すなわち $a=qb+r$、$r\ge0$ である。$r\ge|b|$ と仮定する。$\varepsilon:=b/|b|\in\{1,-1\}$ とおくと $\varepsilon b=|b|$ なので
$$ r-|b|=a-(q+\varepsilon)b\ge0 $$
であり、$r-|b|\in S$ となる。$|b|>0$ より $r-|b|< r$ であり、$r$ の最小性に反する。よって $0\le r<|b|$ である。
一意性：$a=qb+r=q'b+r'$、$0\le r,r'<|b|$ とする。差をとって $(q-q')b=r'-r$ を得る。右辺は $-|b|< r'-r<|b|$ を満たす。$q\neq q'$ なら $|q-q'|\ge1$ で左辺の絶対値は $|b|$ 以上になり矛盾する。よって $q=q'$ であり、したがって $r=r'$ である。$\square$

商と余り

thm-division-algorithm の $q$ を $a$ を $b$ で割った商（quotient）、$r$ を余り（remainder、剰余）という。$r=0$ であることは $b$ が $a$ を割り切る（$b\mid a$、$b$ は $a$ の約数）ことと同値である。

$b=0$ は除外しなければならない。$a=q\cdot0+r$ なら $r=a$ であり、条件 $0\le r<|0|=0$ を満たす $r$ は存在しない。除法の原理は「$0$ で割ること」を扱わない。
$b>0$ のときは $|b|=b$ で、条件は $0\le r< b$ である。$b<0$ の場合は、$a=q|b|+r$ と書いてから $q$ の符号を変えれば $a=(-q)b+r$ となるので、$b>0$ の場合に帰着する。

直感

$b>0$ とすると、$b$ の倍数 $\dots,-2b,-b,0,b,2b,\dots$ は数直線を長さ $b$ の半開区間 $[qb,(q+1)b)$ に切り分け、これらの区間は重ならずに数直線を覆う。整数 $a$ はそのどれか 1 つだけに入る。その区間の番号が商 $q$、区間の左端からの位置が余り $r$ である。区間を閉区間 $[qb,(q+1)b]$ にすると隣どうしが端点を共有して一意性が壊れ、長さを $b$ より短くすると数直線を覆えず存在が壊れる。
余りは $a$ の「$b$ を法とした位置」を表す。$a$ と $a'$ の余りが等しいことは $b\mid a-a'$ と同値であり、余りは合同式や剰余類の標準的な代表を与える。この「大きさの真に小さい余りが残る」という性質を公理にしたのがEuclid整域である。

例と反例

符号の組合せ

$b$ と $a$ の符号の 4 通りを計算する。
$$ \begin{align*} 37&=7\cdot5+2, & -17&=(-4)\cdot5+3,\\ 17&=(-3)\cdot(-5)+2, & -17&=4\cdot(-5)+3. \end{align*} $$
いずれも $0\le r<|b|=5$ を満たす。$-17$ を $5$ で割るとき、$-17/5=-3.4$ を $0$ の方向へ丸めた $-3$ を商にすると $-17=(-3)\cdot5+(-2)$ となり、余り $-2$ は条件 $0\le r$ を満たさない。除法の原理の商は $0$ の方向ではなく、$b>0$ なら小さい方向へ丸めた値である（prop-division-algorithm-floor）。

偶数と奇数

$b=2$ とすると、任意の整数 $a$ はただ 1 通りに $a=2q$ または $a=2q+1$ と書ける。すなわちすべての整数は偶数か奇数のどちらか一方だけである。同様に $b=3$ から、任意の整数は $3q$、$3q+1$、$3q+2$ のどれか 1 つの形に書ける。

反例：余りの範囲に上端を含める

条件 $0\le r<|b|$ を $0\le r\le|b|$ に弱めると一意性が壊れる。実際
$$ 10=2\cdot5+0=1\cdot5+5 $$
はどちらも $0\le r\le5$ を満たす。この例は「$a=qb+r$ かつ $0\le r\le|b|$ なら $(q,r)$ は一意」という含意を破る。壊れる原因は、範囲 $\{0,1,\dots,|b|\}$ が $0$ と $|b|$ という $b$ を法として合同な 2 つの値を含むことにある。一般に、余りのとりうる値の集合を $T\subset\mathbb{Z}$ とするとき、$(q,r)$ が高々 1 組であることは $T$ が $b$ を法とする各剰余類から高々 1 つの値しか含まないことと同値であり、存在も込めれば各剰余類からちょうど 1 つずつ含むことと同値である（$a=qb+r=q'b+r'$ なら $r\equiv r'$ であり、逆に $r\neq r'$ が合同なら $r'=r+kb$ として $r=0\cdot b+r=(-k)b+r'$ となる）。したがって範囲は半開区間である必要はなく、閉区間 $[0,|b|-1]$ でも、$b=3$ のときの $\{0,2,4\}$ のような区間でない集合でもよい。

反例：大きさだけを制限した余り

条件を $|r|<|b|$ に替えても存在は保たれるが、一意性は壊れる。
$$ 4=1\cdot3+1=2\cdot3+(-2) $$
で、$|1|<3$、$|-2|<3$ である。この例は「$a=qb+r$ かつ $|r|<|b|$ なら $(q,r)$ は一意」という含意を破る。Euclid整域の定義の除法の条件はこの形であり、そこでは商と余りの一意性を要求しない（同記事の例「有理整数環」）。

性質

床関数による表示と絶対値最小の余り

床関数による商

$a\in\mathbb{Z}$、$b\in\mathbb{Z}$、$b>0$ とする。$a$ を $b$ で割った商と余りは
$$ q=\left\lfloor\frac ab\right\rfloor,\qquad r=a-b\left\lfloor\frac ab\right\rfloor $$
である。ここで $\lfloor x\rfloor$ は実数 $x$ 以下の最大の整数（床関数）である。

$q:=\lfloor a/b\rfloor$ とおくと、床関数の定義から $q\le a/b< q+1$ である。$b>0$ を掛けて $qb\le a< qb+b$、すなわち $r:=a-qb$ は $0\le r< b$ を満たす。thm-division-algorithm の一意性により、この $q,r$ が商と余りである。$\square$

$b<0$ のときは、$b>0$ の場合への帰着（thm-division-algorithm の後の段落）により商は $-\lfloor a/|b|\rfloor$ である。
余りの範囲は $0\le r<|b|$ でなくても、長さ $|b|$ の半開区間であれば同じ議論で一意性が得られる。よく使われるのは $0$ を中心にした区間である。

絶対値最小の余り

$a,b$ を整数とし、$b>0$ とする。このとき
$$ a=qb+r,\qquad -\frac b2< r\le\frac b2 $$
を満たす整数 $q,r$ がただ 1 組存在する。

存在：thm-division-algorithm により $a=q_0b+r_0$、$0\le r_0< b$ と書く。$r_0\le b/2$ なら $(q,r):=(q_0,r_0)$ でよい。$r_0>b/2$ なら $(q,r):=(q_0+1,r_0-b)$ とおくと $a=qb+r$ であり、$b/2< r_0< b$ から $-b/2< r<0$ である。
一意性：$a=qb+r=q'b+r'$ で $r,r'$ がともに $(-b/2,b/2]$ に属するとする。$(q-q')b=r'-r$ であり、$-b< r'-r< b$ である（$r'-r\le b/2-r< b$、同様に $r'-r>-b$）。$q\neq q'$ なら左辺の絶対値は $b$ 以上なので矛盾し、$q=q'$、$r=r'$ である。$\square$

たとえば $17=3\cdot5+2$、$19=4\cdot5+(-1)$ である。絶対値最小の余りを使うと、Euclidの互除法の各段で余りの絶対値が除数の半分以下になるので、段数が少なくなることがある。

剰余類・部分群・イデアル

$n\ge1$ について、thm-division-algorithm により任意の整数 $a$ は $\{0,1,\dots,n-1\}$ のちょうど 1 つの元 $r$ と $n$ を法として合同（$n\mid a-r$）である。存在は余り $r$ をとればよく、一意性は $0\le r< s\le n-1$ なら $0< s-r< n$ で $n\nmid s-r$ となることによる。これは $\{0,1,\dots,n-1\}$ が剰余類の集合 $\mathbb{Z}/n\mathbb{Z}$ の完全代表系であることを意味し、剰余類の記事の命題「法 n の剰余類の個数」と剰余環の $\mathbb{Z}/n\mathbb{Z}$ の記述はこれに基づく。
もう 1 つの基本的な帰結は、加法群 $\mathbb{Z}$ の部分群（したがって環 $\mathbb{Z}$ のイデアル）がすべて $n\mathbb{Z}$（$n\ge0$）の形であることである。$\{0\}$ でない部分群 $H$ は正の元を含み（$h\in H$ なら $-h\in H$）、その最小元を $n$ とすると、$h\in H$ を $h=qn+r$（$0\le r< n$）と割れば $r=h-qn\in H$ で、$n$ の最小性から $r=0$ である。よって $H=n\mathbb{Z}$ であり、$\mathbb{Z}$ は単項イデアル整域である。この議論は巡回群の記事の命題「巡回群の部分群は巡回群」の証明と同じものである。

位取り記数法

底 b による展開

$b\ge2$ を整数とする。任意の整数 $n\ge1$ は
$$ n=d_kb^k+d_{k-1}b^{k-1}+\cdots+d_1b+d_0,\qquad 0\le d_i< b,\quad d_k\neq0 $$
の形にただ 1 通りに書ける（$k\ge0$ と $d_0,\dots,d_k$ がともに一意に定まる）。

$n$ に関する強い数学的帰納法で示す。$n\ge1$ とし、$n$ より小さい正の整数については主張が成り立つとする。thm-division-algorithm により $n=qb+d_0$、$0\le d_0< b$ と書く。$b\ge2$ と $n\ge1$ から $0\le q\le n/b< n$ である。
存在：$q=0$ なら $n=d_0$ で、$n\ge1$ より $d_0\neq0$ なので $k=0$ の表示である。$q\ge1$ なら帰納法の仮定により $q=d_kb^{k-1}+\cdots+d_1$（$0\le d_i< b$、$d_k\neq0$、$k\ge1$）と書け、$n=qb+d_0$ に代入すれば $n$ の表示を得る。
一意性：$n=\sum_{i=0}^kd_ib^i$ を条件を満たす表示とする。$n=\bigl(\sum_{i=1}^kd_ib^{i-1}\bigr)b+d_0$、$0\le d_0< b$ なので、thm-division-algorithm の一意性により $d_0$ は $n$ を $b$ で割った余り、$q':=\sum_{i=1}^kd_ib^{i-1}$ は商 $q$ に等しい。$k=0$ なら $q=0$ である。$k\ge1$ なら $q=q'\ge d_kb^{k-1}\ge1$ であり、$q'$ は $q$ の条件を満たす表示なので、帰納法の仮定により $k-1$ と $d_1,\dots,d_k$ は $q$ だけで決まる。$q=0$ と $q\ge1$ のどちらになるかも $n$ だけで決まるので、表示は一意である。$\square$

証明は、$n$ を $b$ で割って余りを最下位の桁とし、商をさらに $b$ で割ることを商が $0$ になるまで繰り返す計算法そのものである。たとえば $b=2$ で $n=13$ なら $13=6\cdot2+1$、$6=3\cdot2+0$、$3=1\cdot2+1$、$1=0\cdot2+1$ なので、$13=1\cdot2^3+1\cdot2^2+0\cdot2+1$（2 進表示 $1101$）である（位取り記数法）。

互除法

$a,b$ の最大公約数 $\gcd(a,b)$ は、除法の原理を繰り返すことで計算できる。その根拠は次の命題である。

余りへの置き換え

$a,b$ を整数、$b\neq0$ とし、$a=qb+r$ を除法の原理による表示とする。このとき $a$ と $b$ の公約数全体と、$b$ と $r$ の公約数全体は一致する。とくに $\gcd(a,b)=\gcd(b,r)$ である。

$d$ が $a$ と $b$ を割り切れば、$r=a-qb$ も割り切る。逆に $d$ が $b$ と $r$ を割り切れば、$a=qb+r$ も割り切る。公約数の集合が一致するので、その最大元も一致する（$b\neq0$ なので公約数は有限個で最大元がある）。$\square$

$a$ と $b>0$ から始めて $r_0:=a$、$r_1:=b$ とし、$r_{i+1}$ を $r_{i-1}$ を $r_i$ で割った余りとする。$r_1>r_2>r_3>\cdots\ge0$ は $\mathbb{N}$ の真に減少する列なので有限回で $0$ になり、$r_{s+1}=0$ となったときの $r_s$ が $\gcd(a,b)$ である（prop-division-algorithm-gcd を各段に使うと $\gcd(a,b)=\gcd(r_s,0)=r_s$）。たとえば
$$ 252=1\cdot198+54,\quad 198=3\cdot54+36,\quad 54=1\cdot36+18,\quad 36=2\cdot18+0 $$
より $\gcd(252,198)=18$ である。これが Euclidの互除法であり、各段で $r_i=ax_i+by_i$ となる係数を $x_{i+1}=x_{i-1}-q_ix_i$、$y_{i+1}=y_{i-1}-q_iy_i$（$q_i$ は $r_{i-1}$ を $r_i$ で割った商）と更新していくと（または各段を逆にたどると）、$\gcd(a,b)=ax+by$ となる整数 $x,y$ が求まる（Bézoutの等式の記事の命題「互除法による係数の計算」）。

多項式の除法

除法の原理は、可換環上の多項式環でも、割る多項式の最高次係数が単元であれば成り立つ。余りの「大きさ」は次数で測る。

多項式の除法の原理

$A$ を可換環とし、$G(X)\in A[X]$ の最高次係数が $A$ の単元であるとする。このとき任意の $F(X)\in A[X]$ に対し
$$ F(X)=Q(X)G(X)+R(X),\qquad \deg R<\deg G $$
となる $Q(X),R(X)\in A[X]$ がただ 1 組存在する（$\deg0=-\infty$ とする）。とくに体 $K$ 上では、$0$ でない任意の $G(X)\in K[X]$ で割ることができる。

多項式の除法の原理の出典

証明は多項式環の記事の定理「除法の原理」にある。存在は、$F=a_mX^m+\cdots$（$a_m\neq0$）、$G=b_nX^n+\cdots$（$b_n$ は単元）とおき、$m\ge n$ なら $F$ の最高次の項を $a_mb_n^{-1}X^{m-n}G$ を引いて消していく $\deg F$ に関する帰納法、一意性は $G$ の最高次係数が零因子でないことから $\deg\bigl((Q-Q')G\bigr)=\deg(Q-Q')+\deg G$ となることによる。体上の場合は DF04 §9.2 にもある。

たとえば $\mathbb{Q}[X]$ で $F=X^3+2X+1$ を $G=X-1$ で割ると
$$ X^3+2X+1=(X^2+X+3)(X-1)+4 $$
である。余り $4$ は $F(1)=4$ に等しい。一般に $X-\alpha$ で割った余りは $F(\alpha)$ である（多項式環の記事の系「剰余定理と因数定理」）。$G$ がモニック（最高次係数 $1$）なら係数環は体でなくてよく、$\mathbb{Z}[X]$ でも $X^2+1=(X-1)(X+1)+2$ のように割り算が $\mathbb{Z}[X]$ の中で完結する。
整数の場合と同じく、体 $K$ 上の $K[X]$ でも除法の原理から、イデアルがすべて単項であること、Euclid の互除法で最大公約元が計算できることが従い、$K[X]$ は Euclid整域になる（多項式環の記事の定理「体上の多項式環は単項イデアル整域」と命題「Euclid の互除法」）。

反例：最高次係数が単元でないと商が存在しない

$\mathbb{Z}[X]$ で $F=X$ を $G=2X$ で割ることはできない。$X=Q\cdot2X+R$、$\deg R<1$ となる $Q,R\in\mathbb{Z}[X]$ があったとする。$R$ は定数 $c\in\mathbb{Z}$ であり、両辺の定数項を比べると $Q\cdot2X$ の定数項は $0$ なので $c=0$ である。すると $X=2XQ$ であり、$X$ の係数を比べると $1=2Q(0)$ となるが、これを満たす整数 $Q(0)$ はない。
$\mathbb{Z}[X]$ は整域であり、$G=2X$ の最高次係数 $2$ は $0$ でないが単元でない。この例は「整域 $A$ 上で $G\neq0$ なら $F=QG+R$、$\deg R<\deg G$ と割れる」という含意を破り、thm-division-algorithm-polynomial の単元の仮定が存在に必要であることを示す。$\mathbb{Q}[X]$ では $X=\tfrac12\cdot2X+0$ と割れるので、失敗の原因は係数 $2$ の逆元が $\mathbb{Z}$ にないことにある。
一方、$\mathbb{Z}[X]$ では、割れる場合の商と余りは一意である。$QG+R=Q'G+R'$、$\deg R,\deg R'<\deg G$、$Q\neq Q'$ とすると、整域上では $\deg\bigl((Q-Q')G\bigr)=\deg(Q-Q')+\deg G\ge\deg G$ となり（多項式環の記事の命題「次数の公式と整域性」）、次数が $\deg G$ 未満の $R'-R$ に等しいことに反する。整域の上で壊れるのは存在のほうである。

反例：最高次係数が零因子だと一意性が壊れる

$A=\mathbb{Z}/4\mathbb{Z}$、$G=2X+1\in A[X]$ とする。$A$ で $4=0$ なので $2G=4X+2=2$ であり、
$$ 0=0\cdot G+0=2\cdot G+2 $$
はどちらも $\deg R<\deg G=1$ を満たす。よって $F=0$ を $G$ で割った商と余りは一意でない。$G$ の最高次係数 $2$ は $A$ の零因子（$2\cdot2=0$）である。この例は「$\deg R<\deg G$ を満たす商と余りは一意」という含意を破り、thm-division-algorithm-polynomial の単元の仮定が一意性にも必要であることを示す。なお $(2X+1)^2=4X^2+4X+1=1$ なので $G$ は $A[X]$ の単元であり、任意の $F$ について $F=(FG)\cdot G+0$ とも書ける。

整数と多項式以外への一般化

整数の絶対値や多項式の次数のように、元の大きさを測る関数 $\phi$ があって「$b\neq0$ なら $a=qb+r$、$\phi(r)<\phi(b)$ と書ける」整域を Euclid整域という。Gauss整数環 $\mathbb{Z}[i]$ はノルム $N(x+yi)=x^2+y^2$ についての Euclid 整域である（Euclid整域の記事の例「Gauss整数環の除法」）。Euclid 整域の定義は商と余りの一意性を要求せず、$\mathbb{Z}$ と絶対値の組でさえ ex-division-algorithm-absolute-bound のように一意でない。一方、変数が 2 つ以上の多項式環 $K[X,Y]$ や $\mathbb{Z}[X]$ は単項イデアル整域でないので、どのような大きさの関数についても除法の原理を満たさない（Euclid整域の記事の注意「反例：Euclid整域でない整域」）。