除法の原理

まず自然数\(a,b\) に対して \(b\neq0\) ならば \[a=bq+r\quad (0\leq r<b)\] となる整数 \(q,r\) が存在することを示す.
\(a\) に関する数学的帰納法で示す.
\(a=0\) のとき \(q=0,r=0\) とすれば良い.
\(a\) より小さな自然数に対して主張が成り立つと仮定する.
\(a<b\) ならば \(q=0,r=a\) とおけば良い.
\(a\geq b\) ならば \(0\leq a-b<a\) なので仮定より \(a-b=bq^\prime+r^\prime\ (0\leq r^\prime<b)\) となる整数 \(q^\prime,r^\prime\) が存在する.
よって \(a=b(q^\prime+1)+r^\prime\) より \(q=q^\prime+1,r=r^\prime\) とすれば良い.
以上より, 自然数 \(a,b\) に対して主張が成立する.

次に整数 \(a,b\) に対して \(b\neq0\) ならば \[a=bq+r\quad (0\leq r<|b|)\] となる整数 \(q,r\) が存在することを示す.
\(a\geq 0,b>0\) のときは良い.
\(a<0, b>0\) のとき \(-a>0\) なので \(-a=bq+r\ (0\leq r<b)\) となる整数 \(q,r\) が存在する.
よって \(a=b(-q)-r=b(-q-1)+(b-r)\) であり, \(0<b-r<b\) であるから良い.
\(b<0\) のとき, \(-b>0\) より, \(a=(-b)q+r\ (0\leq r<-b)\) となる整数 \(q,r\) が存在する.
このとき \(a=b(-q)+r\) かつ \(|b|=-b\) であるから良い.
以上より, 整数 \(a,b\) 主張が成立する.

最後に \(q,r\) の一意的を示す.
整数 \(a,b\neq 0\) に対して 整数 \(q,q^\prime,r,r^\prime\) が \[a=bq+r\quad (0\leq r<|b|)\\a=bq^\prime+r^\prime\quad (0\leq r^\prime<|b|)\] を満たしているとする.
このとき \(bq+r=bq^\prime+r^\prime\) より \(b(q-q^\prime)=r^\prime-r\) である.
\(q>q^\prime\) ならば
\(b>0\) のとき \(r^\prime-r\geq b\) となるが \(-b<r^\prime-r<b\) なので矛盾.
\(b<0\) のとき \(r^\prime-r\leq b\) となるが \(b<r^\prime-r<-b\) なので矛盾.
同様に \(q<q^\prime\) の場合も矛盾する.
ゆえに \(q=q^\prime\) であり, このとき \(r=r^\prime\) でもあるから一意性は示された.