整数の筆算の仕組み
概要
整数の筆算の仕組み（how integer long arithmetic works）とは、四則演算の筆算が、位取り記数法（正の整数を $\sum_k d_k10^k$、$0\le d_k\le9$ とただ 1 通りに書く方法）と分配法則から出てくることを示す見方である。足し算と掛け算は位ごとの和や 1 桁どうしの積に分けたあと、10 以上になった分を上の位へ送る繰り上がりで数字に直す。掛け算の 2 段目をずらして書くのは $a\times b=\sum_j(a\times b_j)10^j$ だからである。割り算は、整数 $a\ge0$、$b\ge1$ について $a<10^mb$ となる $m$ から始めて各段で $10^ib$ を引けるだけ引くと、各段の商は $0$〜$9$ の 1 桁になり、最後の残りが $b$ 未満の余りになる。$10$ を 2 以上の整数に替えても同じである。
小学校で習う足し算・掛け算・割り算の筆算は、手順として覚えることが多い。「右端から計算する」「2 段目は 1 桁ずらして書く」「割り算では上の桁から商を立てる」。この記事では、これらの手順がどれも 位取り記数法 と 分配法則 から出てくることを、一行ずつ確かめる。筆算は、数を $10$ の累乗のまとまりに分け、分配法則で計算を小さな計算に分け、最後に $10$ 個のまとまりを 1 つ上の位へ送る（繰り上がり）手続きである。全体の案内は 筆算と分配法則 にある。
証明では、2 つの事実を使う。1 つは、整数を正の整数で割った商と余りがただ 1 組に決まること（除法の原理）で、証明は 整数の割り算と互除法 にある。もう 1 つは 数学的帰納法 で、考え方は 数学的帰納法と整列性 で扱っている。
高校での出発点：3 つの筆算
まず、見慣れた筆算を 3 つ並べる。
$478+356$ を筆算で計算する。右端（一の位）から順に、
- 一の位：$8+6=14$。$4$ を書き、$1$ を十の位へ繰り上げる。
- 十の位：$7+5+1=13$。$3$ を書き、$1$ を百の位へ繰り上げる。
- 百の位：$4+3+1=8$。$8$ を書く。
答えは $834$ である。
$47\times36$ を筆算で計算する（図 1）。
- 1 段目：$47\times6=282$。
- 2 段目：$47\times3=141$ を、1 桁左にずらして書く。
- 2 つの段を足す：$282+1410=1692$。
答えは $1692$ である。
47×36 の筆算。2 段目は 47×30 = 1410 の最後の 0 を書かずに 1 桁ずらしたもの
$7394\mathbin{÷}23$ を筆算で計算する（図 2）。
- $73$ の中に $23$ は $3$ 回入る。$73-69=4$。次の $9$ を下ろして $49$。
- $49$ の中に $23$ は $2$ 回入る。$49-46=3$。次の $4$ を下ろして $34$。
- $34$ の中に $23$ は $1$ 回入る。$34-23=11$。
商は $321$、余りは $11$ である。検算すると $23\times321+11=7383+11=7394$ である。
7394÷23 の筆算。各段で引いているのは 23×3×100、23×2×10、23×1 である
手順は覚えていても、理由を聞かれると答えにくい。この記事で答える問いは次の 5 つである。
- 数を「各位の数字」で表す方法は、なぜ 1 通りに決まるのか。→ thm-ila-unique
- 足し算・掛け算を右端から計算し、10 を超えたら繰り上げてよいのはなぜか。→ lem-ila-carry、prop-ila-add
- 掛け算の 2 段目をずらして書くのはなぜか。九九だけで足りるのはなぜか。→ prop-ila-mul、rem-ila-kuku
- 割り算で、各段の商がいつも $0$〜$9$ の 1 桁に収まり、最後に正しい余りが出るのはなぜか。→ thm-ila-div
- 足し算・掛け算は右端から計算するのに、割り算だけ左（上の位）から計算するのはなぜか。→ rem-ila-why-left
筆算の操作と、この記事で使う言葉の対応は次のとおりである。
位取り記数法：数を 10 の累乗で表す
筆算は、数を「$1$ が何個、$10$ が何個、$100$ が何個……」と分けて書くことから始まる。
正の整数 $N$ が、整数 $d_0,d_1,\dots,d_m$ を使って
$$
N=d_m\cdot10^m+d_{m-1}\cdot10^{m-1}+\dots+d_1\cdot10+d_0=\sum_{k=0}^{m}d_k\,10^k
$$
と書け、
- 各 $d_k$ は $0\le d_k\le9$ を満たし（$d_k$ を 数字 という）、
- 最上位の数字は $d_m\ne0$ である
とき、この式を $N$ の 10 進法の表し方 といい、数字を上の位から並べて $N=(d_md_{m-1}\cdots d_1d_0)$ と書く。$d_k$ を $N$ の $10^k$ の位の数字 という。このように、数字を置く場所（位）で $10$ の累乗を表す方法を 位取り記数法 という。$0$ は、数字 $0$ だけの並び $(0)$ で表すと約束する。
- $2026=2\cdot10^3+0\cdot10^2+2\cdot10+6$。数字は上から $2,0,2,6$ である。百の位の数字は $0$ である。
- $305=3\cdot10^2+0\cdot10+5$ と $35=3\cdot10+5$ は違う数である。$0$ の数字は「その位のまとまりがない」ことを表し、省くと位がずれてしまう。
- $7394=7\cdot1000+3\cdot100+9\cdot10+4$。
筆算の途中では、ある位に $10$ 以上の数が現れることがある（ex-ila-add-start の $8+6=14$）。そのとき使うのが次の補題である。$10$ 個の $10^k$ は $1$ 個の $10^{k+1}$ と同じ量だから、$10$ 個のまとまりを上の位へ送っても数は変わらない。
- $1\cdot10^2+13\cdot10+14$ を直す。一の位の $14=10\cdot1+4$ なので、一の位を $4$ にし、$1$ を十の位へ送ると $1\cdot10^2+14\cdot10+4$。十の位の $14=10\cdot1+4$ なので、十の位を $4$ にし、$1$ を百の位へ送ると $2\cdot10^2+4\cdot10+4=244$。実際 $100+130+14=244$ である。
- $2\cdot10^2+25\cdot10+36$ を直す。$36=10\cdot3+6$ で一の位は $6$、十の位は $25+3=28=10\cdot2+8$ で $8$、百の位は $2+2=4$。結果は $486$ で、実際 $200+250+36=486$ である。
$c_0,c_1,\dots,c_m$ を $0$ 以上の整数とし、$N=\sum_{k=0}^{m}c_k\,10^k$ とおく（$c_k$ は $10$ 以上でもよい）。$k>m$ では $c_k=0$ とする。$t_0=0$ とし、$k=0,1,2,\dots$ の順に、$c_k+t_k$ を $10$ で割った商を $t_{k+1}$、余りを $d_k$ とする：
$$
c_k+t_k=10\,t_{k+1}+d_k,\qquad 0\le d_k\le9.
$$
このとき、ある $K>m$ で $t_K=0$ となり、
$$
N=\sum_{k=0}^{K-1}d_k\,10^k
$$
が成り立つ。つまり、下の位から順に「$10$ で割った余りを残し、商を 1 つ上の位へ足す」と、各位が $0$〜$9$ の数字に直り、数は変わらない。$t_{k+1}$ を $10^k$ の位からの 繰り上がり という。
方針：1 つの位での繰り上げが数を変えないことを示し、それを全部の位について足し合わせる。最後に、繰り上がりがいつか $0$ になることを示す。
段 1（1 つの位）。定義の式 $c_k+t_k=10\,t_{k+1}+d_k$ の両辺に $10^k$ を掛けると、分配法則により
$$
c_k\,10^k+t_k\,10^k=d_k\,10^k+t_{k+1}\,10^{k+1}
$$
である（$10\cdot10^k=10^{k+1}$ を使った）。
段 2（足し合わせる）。$K$ を $m$ より大きい整数とし、段 1 の式を $k=0,1,\dots,K-1$ について足すと
$$
\sum_{k=0}^{K-1}c_k\,10^k+\sum_{k=0}^{K-1}t_k\,10^k=\sum_{k=0}^{K-1}d_k\,10^k+\sum_{k=0}^{K-1}t_{k+1}\,10^{k+1}
$$
である。左辺の第 1 の和は、$k>m$ で $c_k=0$ なので $N$ に等しい。左辺の第 2 の和は $t_0+t_1\cdot10+\dots+t_{K-1}10^{K-1}$、右辺の第 2 の和は $t_1\cdot10+\dots+t_{K-1}10^{K-1}+t_K10^K$ である。両辺から共通の $t_1\cdot10+\dots+t_{K-1}10^{K-1}$ を引き、$t_0=0$ を使うと
$$
N=\sum_{k=0}^{K-1}d_k\,10^k+t_K\,10^K
$$
となる。
段 3（繰り上がりはいつか 0 になる）。$k>m$ では $c_k=0$ なので、$t_k=10\,t_{k+1}+d_k$ であり、$d_k\ge0$ から $10\,t_{k+1}\le t_k$ である。よって $t_k\ge1$ ならば $t_{k+1}\le t_k/10< t_k$ となり、繰り上がりは $0$ 以上の整数のまま真に減っていく。$0$ 以上の整数が限りなく真に減り続けることはないので、ある $K>m$ で $t_K=0$ となる。この $K$ を段 2 の式に入れると $N=\sum_{k=0}^{K-1}d_k\,10^k$ を得る。各 $d_k$ は $10$ で割った余りなので $0\le d_k\le9$ である。$\square$
段 3 の議論は、たとえば一の位に $1234$ があるとき、繰り上がりが $123,12,1,0$ と減っていくことを言っている。補題を使うと、10 進法の表し方がいつもあり、しかも 1 通りしかないことが示せる。
すべての正の整数 $N$ は 10 進法の表し方（def-ila-decimal）をもつ。しかもその表し方はただ 1 通りである。
方針：存在は $N=N\cdot10^0$ に lem-ila-carry を使う。一意性は、一の位の数字が「$10$ で割った余り」として決まることを使い、桁数についての帰納法で示す。
段 1（存在）。$c_0=N$、$m=0$ として lem-ila-carry を使うと、$N=\sum_{k=0}^{K-1}d_k\,10^k$（$0\le d_k\le9$）と書ける。$N\ge1$ なので $d_k$ のどれかは $0$ でない。$0$ でない $d_k$ のうち $k$ が最大のものを $d_m$ とし、それより上の位（すべて $0$）を捨てれば、10 進法の表し方になる。
段 2（一意性の準備）。2 つの表し方
$$
N=\sum_{k=0}^{m}d_k\,10^k=\sum_{k=0}^{m'}e_k\,10^k
$$
があるとする。上の位に $0$ を補って、$m=m'$ としてよい（$0$ を補っても値は変わらない）。そこで、$m\ge0$ についての次の主張 $P(m)$ を示せばよい。
$P(m)$：$0\le d_k\le9$、$0\le e_k\le9$ を満たす整数について $\sum_{k=0}^{m}d_k\,10^k=\sum_{k=0}^{m}e_k\,10^k$ ならば、すべての $k$ で $d_k=e_k$ である。
段 3（一の位）。両辺の値を $N$ とする。$m=0$ なら $N=d_0=e_0$ なので $P(0)$ は成り立つ。$m\ge1$ のとき、$N'=\sum_{k=1}^{m}d_k\,10^{k-1}$、$N''=\sum_{k=1}^{m}e_k\,10^{k-1}$ とおくと、分配法則で $10$ をくくり出して
$$
N=10\,N'+d_0=10\,N''+e_0,\qquad 0\le d_0\le9,\quad 0\le e_0\le9
$$
である。除法の原理（証明は 整数の割り算と互除法）により、$N$ を $10$ で割った商と余りはただ 1 組なので、$d_0=e_0$ かつ $N'=N''$ である。
段 4（帰納法）。$N'=N''$ は、$k-1$ を $j$ と書き直すと $\sum_{j=0}^{m-1}d_{j+1}10^j=\sum_{j=0}^{m-1}e_{j+1}10^j$ であり、位が 1 つ少ない同じ形の等式である。$P(m-1)$ が成り立つと仮定すると、$d_{j+1}=e_{j+1}$（$j=0,\dots,m-1$）、つまり $d_1=e_1,\dots,d_m=e_m$ である。段 3 の $d_0=e_0$ と合わせて $P(m)$ が成り立つ。数学的帰納法（数学的帰納法と整列性）により、すべての $m$ で $P(m)$ が成り立つ。補った $0$ を除けば、2 つの表し方は同じである。$\square$
- $2026$ の数字を、段 3 のとおり $10$ で割り続けて取り出す：
$$ 2026=10\cdot202+6,\quad 202=10\cdot20+2,\quad 20=10\cdot2+0,\quad 2=10\cdot0+2. $$
余りは $6,2,0,2$ の順に出てくる。出てきた順と逆に並べると $2,0,2,6$ で、$2026$ の数字に一致する。 - $7394$ の一の位の数字は、$7394=10\cdot739+4$ の余り $4$ である。残りの $739$ が、一の位を取り除いた数 $(739)$ である。
この取り出し方は、10 以外の数で割っても同じように使える。あとで def-ila-base で使う。$10$ で割った余りが一の位の数字になることは、多項式 $f(x)$ を $x$ で割った余りが定数項 $f(0)$ になることと同じ形である。多項式を $x-a$ で割った余りが $f(a)$ になること（剰余の定理）は 剰余の定理と因数定理 で扱う。
足し算と引き算：位ごとに計算して繰り上げる
足し算の筆算は、2 つの数を位ごとに分け、同じ位どうしを足してから繰り上げる。まず ex-ila-add-start を式で書き直してみる。
$478=4\cdot10^2+7\cdot10+8$、$356=3\cdot10^2+5\cdot10+6$ である。足し算の順番を入れかえ（交換法則・結合法則）、同じ位をまとめる（分配法則）と
$$
478+356=(4+3)\cdot10^2+(7+5)\cdot10+(8+6)=7\cdot10^2+12\cdot10+14
$$
である。一の位の $14$ と十の位の $12$ は $10$ 以上なので、lem-ila-carry の手順で直す。
- 一の位：$14=10\cdot1+4$。数字 $4$、繰り上がり $1$。
- 十の位：$12+1=13=10\cdot1+3$。数字 $3$、繰り上がり $1$。
- 百の位：$7+1=8$。数字 $8$、繰り上がり $0$。
結果は $834$ で、ex-ila-add-start の筆算と同じ計算をしている。
$999+1$ を位ごとに書くと $9\cdot10^2+9\cdot10+(9+1)$ である。
- 一の位：$10=10\cdot1+0$。数字 $0$、繰り上がり $1$。
- 十の位：$9+1=10$。数字 $0$、繰り上がり $1$。
- 百の位：$9+1=10$。数字 $0$、繰り上がり $1$。
- 千の位：$0+1=1$。数字 $1$、繰り上がり $0$。
結果は $1000$ である。繰り上がりは次の位の計算に影響するので、筆算は右端（一の位）から計算する。
$0$ 以上の整数 $a,b$ を、上の位に $0$ を補って同じ位の数で
$$
a=\sum_{k=0}^{m}a_k\,10^k,\qquad b=\sum_{k=0}^{m}b_k\,10^k\qquad(0\le a_k\le9,\ 0\le b_k\le9)
$$
と書く。このとき
$$
a+b=\sum_{k=0}^{m}(a_k+b_k)\,10^k
$$
であり、$c_k=a_k+b_k$ に lem-ila-carry の手順を使って得る $d_k$ が $a+b$ の各位の数字である。さらに、各位の繰り上がり $t_k$ は $0$ か $1$ である。
方針：和を同じ位ごとにまとめ直し、繰り上がりの補題と一意性の定理を使う。繰り上がりの大きさは帰納法で押さえる。
段 1（位ごとにまとめる）。和の順番は入れかえてよいので
$$
a+b=\sum_{k=0}^{m}\bigl(a_k\,10^k+b_k\,10^k\bigr)
$$
である。分配法則により $a_k\,10^k+b_k\,10^k=(a_k+b_k)\,10^k$ なので、$a+b=\sum_{k=0}^{m}(a_k+b_k)\,10^k$ を得る。
段 2（数字になる）。$c_k=a_k+b_k\ge0$ に lem-ila-carry を使うと、$a+b=\sum_{k=0}^{K-1}d_k\,10^k$（$0\le d_k\le9$）となる。thm-ila-unique により、10 進法の表し方は 1 通りなので（上の位の $0$ を除いて）、この $d_k$ が $a+b$ の数字である。
段 3（繰り上がりは 0 か 1）。$t_0=0$ である。$t_k\le1$ と仮定すると、$c_k+t_k=a_k+b_k+t_k\le9+9+1=19$ なので、$10$ で割った商 $t_{k+1}$ は $1$ 以下である。数学的帰納法（数学的帰納法と整列性）により、すべての $k$ で $t_k\le1$ である。$\square$
引き算の筆算の「借りてくる」操作は、繰り上がりを逆向きに使ったものである。$1$ 個の $10^{k+1}$ を $10$ 個の $10^k$ に崩しても、数は変わらない。
- $503-278$。一の位 $3$ から $8$ は引けないので、上の位から借りる。$503=5\cdot10^2+0\cdot10+3$ の百の位の $1$ 個を $10$ 個の $10$ に崩し、さらにそのうち $1$ 個の $10$ を $10$ 個の $1$ に崩すと
$$ 503=4\cdot10^2+9\cdot10+13 $$
である。これで各位が引けて、$503-278=(4-2)\cdot10^2+(9-7)\cdot10+(13-8)=2\cdot10^2+2\cdot10+5=225$ となる。 - $1000-1$。$1000=9\cdot10^2+9\cdot10+10$ と崩すと、$1000-1=9\cdot10^2+9\cdot10+9=999$ である。ex-ila-add-chain の繰り上がりを逆にたどっている。
掛け算：分配法則で 1 桁どうしの積に分ける
掛け算の筆算は、分配法則を 2 回使う。まず面積で見てみる。
縦 $36$、横 $47$ の長方形を、横を $40$ と $7$、縦を $30$ と $6$ に分けると、4 つの長方形に分かれる（図 3）。面積を足すと
$$
47\times36=(40+7)(30+6)=40\cdot30+40\cdot6+7\cdot30+7\cdot6=1200+240+210+42=1692
$$
である。筆算の 1 段目 $282$ は下の 2 つの長方形 $240+42$、2 段目 $1410$ は上の 2 つの長方形 $1200+210$ にあたる。
47×36 の面積図。4 つの長方形の面積の和が積になる
$0$ 以上の整数 $a=\sum_{k=0}^{m}a_k\,10^k$ と $b=\sum_{j=0}^{n}b_j\,10^j$（$a_k,b_j$ は数字）について、次が成り立つ。
- 1 桁の数 $d$（$0\le d\le9$）との積は $a\times d=\sum_{k=0}^{m}(a_k d)\,10^k$ であり、$c_k=a_kd$ に lem-ila-carry の手順を使うと $a\times d$ の数字が得られる。
- $a\times b=\sum_{j=0}^{n}(a\times b_j)\,10^j$ である。$a\times b_j$ を $10^j$ 倍すると、その数字はそのまま $j$ 桁上の位へ移り、下の $j$ 桁は $0$ になる。
方針：1 は $a$ を位ごとに分けて分配法則を使う。2 は $b$ を位ごとに分けて分配法則を使い、$10^j$ 倍が位を $j$ 個ずらすことを確かめる。
段 1（1 の式）。分配法則により
$$
a\times d=\Bigl(\sum_{k=0}^{m}a_k\,10^k\Bigr)d=\sum_{k=0}^{m}a_k\,10^k\,d=\sum_{k=0}^{m}(a_kd)\,10^k
$$
である（最後に掛け算の順番を入れかえた）。各 $a_kd$ は $0$ 以上なので、lem-ila-carry と thm-ila-unique により、繰り上げて得る $d_k$ が $a\times d$ の数字である。
段 2（2 の式）。$b=\sum_{j=0}^{n}b_j\,10^j$ に分配法則を使うと
$$
a\times b=a\sum_{j=0}^{n}b_j\,10^j=\sum_{j=0}^{n}(a\times b_j)\,10^j
$$
である。
段 3（$10^j$ 倍は位をずらす）。$a\times b_j=\sum_{k=0}^{K}e_k\,10^k$（$e_k$ は数字）とすると、
$$
(a\times b_j)\,10^j=\sum_{k=0}^{K}e_k\,10^{k+j}=e_K\,10^{K+j}+\dots+e_0\,10^j+0\cdot10^{j-1}+\dots+0\cdot10^0
$$
である。右辺は各位が $0$〜$9$ の 10 進法の表し方なので、thm-ila-unique により、$10^{k+j}$ の位の数字は $e_k$、$10^j$ より下の位の数字は $0$ である。つまり、数字の並びが $j$ 桁左へずれ、右に $0$ が $j$ 個つく。筆算で $j$ 段目を $j$ 桁ずらして書き、右の $0$ を省くのはこのためである。$\square$
- $47\times6$：prop-ila-mul の 1 により $47\times6=(4\cdot6)\cdot10+7\cdot6=24\cdot10+42$。一の位 $42=10\cdot4+2$ で数字 $2$、繰り上がり $4$。十の位 $24+4=28=10\cdot2+8$ で数字 $8$、繰り上がり $2$。百の位は $2$。よって $282$。
- $47\times36=47\times6+(47\times3)\cdot10=282+141\cdot10=282+1410=1692$。$141\cdot10=1410$ は $141$ を 1 桁ずらして $0$ をつけたものである。
- $305\times24=305\times4+(305\times2)\cdot10=1220+6100=7320$。$305\times4=(3\cdot4)\cdot10^2+(0\cdot4)\cdot10+5\cdot4=12\cdot10^2+0\cdot10+20$ を繰り上げると、一の位 $20$ で数字 $0$・繰り上がり $2$、十の位 $0+2=2$、百の位 $12=10\cdot1+2$ で数字 $2$・繰り上がり $1$、千の位 $1$ となり $1220$ である。
prop-ila-mul の 1 で計算する積 $a_kd$ は、どれも $0$〜$9$ の数字どうしの積である。$0$ との積は $0$ なので、覚えておく必要があるのは $1$〜$9$ どうしの $81$ 個の積、つまり九九の表だけである。あとは足し算と繰り上がりで済む。何桁の数どうしの掛け算でも、九九の表と足し算だけで計算できるのは、分配法則で「1 桁どうしの積」に分けられるからである。$m+1$ 桁の数と $n+1$ 桁の数の積では、1 桁どうしの積を $(m+1)(n+1)$ 回計算する（$0$ との積も数えた回数である）。
九九の表の $81$ 個の数をすべて足すといくつか。分配法則で
$$
(1+2+\dots+9)\times(1+2+\dots+9)
$$
を展開すると、$1$〜$9$ から 1 つずつ選んだ 2 数の積 $i\times j$ が $81$ 個、ちょうど 1 回ずつ現れる。これは九九の表の数全部の和である。よって和は
$$
(1+2+\dots+9)^2=45^2=2025
$$
である。小さい場合で確かめると、$1$〜$2$ の表 $1,2,2,4$ の和は $9=(1+2)^2$ である。
割り算：上の位から順に引いていく
割り算の筆算では、商の数字を上の位から 1 つずつ決める。各段でしていることは「割る数の $10^i$ 倍を、できるだけ多く引く」ことである。
ex-ila-div-start の 3 つの段は、次の引き算である（図 2）。
- 百の位の段：$23\times100=2300$ を引けるだけ引く。$2300\times3=6900\le7394<9200=2300\times4$ なので $3$ 回引けて、$7394-6900=494$。
- 十の位の段：$23\times10=230$ を引けるだけ引く。$230\times2=460\le494<690=230\times3$ なので $2$ 回引けて、$494-460=34$。
- 一の位の段：$23$ を引けるだけ引く。$23\times1=23\le34<46=23\times2$ なので $1$ 回引けて、$34-23=11$。
まとめると $7394=23\times300+23\times20+23\times1+11=23\times321+11$ で、$0\le11<23$ である。筆算で書く「$4$」「$49$」「$3$」「$34$」は、途中の数 $494$ と $34$ のうち、その段で必要な上の桁だけを書いたものである（lem-ila-top）。
一般の場合を述べる。以下、$\lfloor x\rfloor$ は $x$ 以下の最大の整数を表す（たとえば $\lfloor 3.21\rfloor=3$、$\lfloor 7\rfloor=7$）。
$a\ge0$、$b\ge1$ を整数とし、$a<10^m\,b$ となる正の整数 $m$ を 1 つとる。$r_m=a$ とおき、$i=m-1,m-2,\dots,0$ の順に
$$
q_i=\left\lfloor\frac{r_{i+1}}{10^i\,b}\right\rfloor,\qquad r_i=r_{i+1}-10^i\,b\,q_i
$$
と定める（$10^i b$ を引ける回数だけ引く）。このとき次が成り立つ。
- 各段の商は 1 桁である：$0\le q_i\le9$。
- 各段の残りは $0\le r_i<10^i\,b$ を満たす。
- $q=\sum_{i=0}^{m-1}q_i\,10^i$ とおくと、$a=bq+r_0$ かつ $0\le r_0< b$ である。
したがって $q$ と $r_0$ は $a$ を $b$ で割った商と余りであり、$q_{m-1},\dots,q_0$ は（上の位の $0$ を除いて）商の各位の数字である。
方針：「段を始めるとき $0\le r_{i+1}<10^{i+1}b$」が各段で保たれることを示す。これから 1 と 2 が出る。3 は各段の引き算を足し合わせて得る。
段 1（最初の段の前）。$r_m=a$ で、$a\ge0$ と $m$ の選び方 $a<10^m\,b$ から $0\le r_m<10^m\,b$ である。
段 2（1 つの段）。$0\le r_{i+1}<10^{i+1}b$ と仮定する。$q_i$ は $r_{i+1}/(10^ib)$ 以下の最大の整数なので
$$
q_i\le\frac{r_{i+1}}{10^i\,b}< q_i+1
$$
である。各辺に正の数 $10^ib$ を掛けて
$$
10^i\,b\,q_i\le r_{i+1}<10^i\,b\,q_i+10^i\,b
$$
を得る。各辺から $10^i\,b\,q_i$ を引くと $0\le r_{i+1}-10^ibq_i<10^ib$、つまり $0\le r_i<10^i\,b$ である。これが 2 である。
段 3（商は 1 桁）。$r_{i+1}\ge0$ なので $r_{i+1}/(10^ib)\ge0$ であり、$q_i\ge0$ である。また仮定 $r_{i+1}<10^{i+1}b$ から
$$
\frac{r_{i+1}}{10^i\,b}<\frac{10^{i+1}\,b}{10^i\,b}=10
$$
なので、$q_i\le r_{i+1}/(10^ib)<10$ であり、整数だから $q_i\le9$ である。これが 1 である。
段 4（帰納法）。段 2 で示した $0\le r_i<10^ib$ は、次の段（添字 $i-1$）を始めるときの仮定そのものである。段 1 から始めて、すべての段で仮定が保たれる。
段 5（足し合わせる）。定義から $r_{i+1}-r_i=10^i\,b\,q_i$ である。これを $i=0,1,\dots,m-1$ について足すと、左辺は $r_m-r_0$ になる（途中の $r_1,\dots,r_{m-1}$ は打ち消し合う）。よって
$$
a-r_0=r_m-r_0=\sum_{i=0}^{m-1}b\,q_i\,10^i=b\,q
$$
であり、$a=bq+r_0$ である。段 2 で $i=0$ とすると $0\le r_0< b$ である。（隣どうしの差を足すと両端だけが残るこの計算は、数列の和と差分 で扱う差分の和と同じ形である。）
段 6（商と余り）。除法の原理（証明は 整数の割り算と互除法）により、$a=bq+r$、$0\le r< b$ を満たす整数の組 $(q,r)$ はただ 1 組なので、$q$ と $r_0$ は商と余りである。1 により各 $q_i$ は数字なので、$q=\sum q_i\,10^i$ は $q$ の 10 進法の表し方（上の位の $0$ を除く）である。$\square$
- $1000\mathbin{÷}7$。$1000<7\times10^3$ なので $m=3$ とする。$i=2$：$q_2=\lfloor1000/700\rfloor=1$、$r_2=1000-700=300$。$i=1$：$q_1=\lfloor300/70\rfloor=4$、$r_1=300-280=20$。$i=0$：$q_0=\lfloor20/7\rfloor=2$、$r_0=20-14=6$。よって $1000=7\times142+6$ である。
- $6048\mathbin{÷}12$。$6048<12\times10^3$ なので $m=3$ とする。$i=2$：$q_2=\lfloor6048/1200\rfloor=5$、$r_2=6048-6000=48$。$i=1$：$q_1=\lfloor48/120\rfloor=0$、$r_1=48$。$i=0$：$q_0=\lfloor48/12\rfloor=4$、$r_0=0$。よって $6048=12\times504$ である。十の位の段では $120$ が $1$ 回も引けないので、商の十の位の数字は $0$ になる。筆算でこの $0$ を書き忘れると、$54$ という誤った商になる。
筆算で途中の数を全部書かず、「上の桁だけ見て商を立て、次の数字を下ろす」のは、次の補題による。
$r\ge0$、$b\ge1$、$i\ge0$ を整数とする。$r$ を $10^i$ で割って $r=10^i\,r'+s$（$0\le s<10^i$）と書く（$r'$ は $r$ の下の $i$ 桁を取り除いた数、$s$ は下の $i$ 桁）。このとき
$$
\left\lfloor\frac{r}{10^i\,b}\right\rfloor=\left\lfloor\frac{r'}{b}\right\rfloor
$$
である。さらに $q=\lfloor r'/b\rfloor$ とおくと、$r-10^ibq=10^i(r'-bq)+s$ であり、引いたあとも下の $i$ 桁 $s$ は変わらない。
方針：$r'$ を $b$ で割った商と余りを使い、$r/(10^ib)$ が $q$ 以上 $q+1$ 未満であることを示す。
段 1。$r'=bq+R$、$0\le R\le b-1$ と書く（除法の原理。証明は 整数の割り算と互除法）。すると
$$
r=10^i\,r'+s=10^i\,b\,q+10^i\,R+s
$$
であり、両辺を $10^ib$ で割ると
$$
\frac{r}{10^i\,b}=q+\frac{10^i\,R+s}{10^i\,b}
$$
である。
段 2。$10^iR+s\ge0$ である。また $s<10^i$ と $R\le b-1$ から
$$
10^i\,R+s<10^i\,R+10^i=10^i(R+1)\le10^i\,b
$$
なので、$0\le\dfrac{10^iR+s}{10^ib}<1$ である。よって $q\le r/(10^ib)< q+1$ となり、$\lfloor r/(10^ib)\rfloor=q=\lfloor r'/b\rfloor$ である。
段 3。分配法則により $r-10^ibq=10^ir'+s-10^ibq=10^i(r'-bq)+s$ である。$\square$
- ex-ila-div-stages の百の位の段：$7394=100\times73+94$ なので、$\lfloor7394/2300\rfloor=\lfloor73/23\rfloor=3$。筆算では $73$ だけを見て $3$ を立てる。引いたあとは $100\times(73-69)+94=100\times4+94=494$ で、下の 2 桁 $94$ はそのまま残る。書くのは $4$ だけで、次の段で $9$ を下ろして $49$ とする。
- 十の位の段：$494=10\times49+4$ なので、$\lfloor494/230\rfloor=\lfloor49/23\rfloor=2$。引いたあとは $10\times(49-46)+4=34$ である。
lem-ila-top から、割り算だけを左から計算する理由が分かる。
足し算・掛け算と割り算では、計算の影響が伝わる向きが逆である。
- 足し算・掛け算では、答えの $10^k$ の位の数字は、もとの数の $10^k$ の位とそれより下の位だけで決まる。上の位は下の位に影響しないが、下の位からの繰り上がりは上の位に入る（lem-ila-carry）。だから、繰り上がりが先に決まる下の位（右端）から計算する（ex-ila-add-chain）。
- 割り算では逆に、商のいちばん上の数字は、割られる数の上の桁だけで決まる（lem-ila-top）。そして、その段で引いた残りが次の位の商を決める。だから、上の位（左）から計算する。
- 下の位から始めようとしても、商の一の位は割られる数の一の位だけでは決まらない。$7394\mathbin{÷}23$ の商は $321$（余り $11$）、$7494\mathbin{÷}23$ の商は $325$（余り $19$。$23\times325=7475$、$7475+19=7494$）である。割られる数の一の位はどちらも $4$ なのに、百の位を $3$ から $4$ に変えただけで、商の一の位が $1$ から $5$ に変わる。
足し算・掛け算で答えの一の位が一の位どうしだけで決まることは、合同式の言葉では「$a\equiv a_0$、$b\equiv b_0\pmod{10}$ ならば $a+b\equiv a_0+b_0$、$ab\equiv a_0b_0\pmod{10}$」と言える。この計算規則は 合同式の計算規則 で証明している。
商の数字は上の桁だけで決まるが、その数字を一目で当てられるとは限らない。実際の筆算では「仮の商」を立てて、大きすぎたら 1 ずつ減らす。
$1728\mathbin{÷}27$。
- 十の位の段：$172$ に $27$ が何回入るかを、上の桁どうし $17\mathbin{÷}2$ から $8$ と見積もる。$27\times8=216>172$ なので大きすぎる。$7$ にすると $27\times7=189>172$ でまだ大きい。$6$ にすると $27\times6=162\le172$ で、$172-162=10$。
- 一の位の段：$8$ を下ろして $108$。$10\mathbin{÷}2$ から $5$ と見積もると $27\times5=135>108$。$4$ にすると $27\times4=108$ で、余り $0$。
よって $1728=27\times64$ である。thm-ila-div は、正しい商の数字 $q_i=\lfloor r_{i+1}/(10^ib)\rfloor$ がいつも $0$〜$9$ にあることを保証する。見積もりは、その数字を探す手がかりにすぎない。
10 以外の底：2 進法の筆算
これまでの証明で $10$ について使った性質は、「$10$ は $2$ 以上の整数である」ことと「$10\cdot10^k=10^{k+1}$」だけである。したがって $10$ を他の整数に取りかえても、同じ筆算ができる。
$B\ge2$ を整数とする。正の整数 $N$ を
$$
N=\sum_{k=0}^{m}d_k\,B^k\qquad(0\le d_k\le B-1,\ d_m\ne0)
$$
と書いた式を $N$ の $B$ 進法の表し方 といい、$N=(d_m\cdots d_1d_0)_B$ と書く。$B$ を 底 という。$B=2$ のときを 2 進法 といい、数字は $0$ と $1$ だけである。
lem-ila-carry、thm-ila-unique、prop-ila-add、prop-ila-mul、thm-ila-div、lem-ila-top の証明で、$10$ をすべて $B$ に、数字の上限 $9$ を $B-1$ に取りかえると、$B$ 進法の同じ主張の証明になる。たとえば足し算の繰り上がりが $0$ か $1$ であることは、$(B-1)+(B-1)+1=2B-1<2B$ から出る。
- $(1011)_2=1\cdot2^3+0\cdot2^2+1\cdot2+1=8+0+2+1=11$ である。
- $45$ を 2 進法で表す。ex-ila-unique と同じく $2$ で割り続けると
$$ 45=2\cdot22+1,\ \ 22=2\cdot11+0,\ \ 11=2\cdot5+1,\ \ 5=2\cdot2+1,\ \ 2=2\cdot1+0,\ \ 1=2\cdot0+1 $$
で、余りを出てきた順と逆に並べて $45=(101101)_2$ である。確かめると $32+8+4+1=45$ である。
2 進法の表し方がただ 1 通りであることは、rem-ila-base のとおり thm-ila-unique と同じ証明で示せる。同じ事実を母関数を使って別の方法で示すこともでき、それは 分割の母関数 で扱う。
$(1011)_2+(110)_2$ を位ごとに計算する（$11+6$ の計算である）。
- $2^0$ の位：$1+0=1$。数字 $1$、繰り上がり $0$。
- $2^1$ の位：$1+1=2=2\cdot1+0$。数字 $0$、繰り上がり $1$。
- $2^2$ の位：$0+1+1=2$。数字 $0$、繰り上がり $1$。
- $2^3$ の位：$1+0+1=2$。数字 $0$、繰り上がり $1$。
- $2^4$ の位：$1$。
結果は $(10001)_2=16+1=17$ で、$11+6=17$ と一致する。
2 進法の数字どうしの積は $0\cdot0=0$、$0\cdot1=0$、$1\cdot0=0$、$1\cdot1=1$ の 4 通りしかない。2 進法の「九九の表」はこれだけである。そのため prop-ila-mul の 1 の積 $a\times b_j$ は、$b_j=0$ なら $0$、$b_j=1$ なら $a$ そのものになり、掛け算の筆算は「$a$ をずらして足す」だけになる。
$(1011)_2\times(101)_2$ を計算する（$11\times5$ の計算である。図 4）。$(101)_2$ の数字は下から $1,0,1$ なので、
$$
(1011)_2\times(101)_2=(1011)_2\times1+(1011)_2\times0\cdot2+(1011)_2\times1\cdot2^2=(1011)_2+(101100)_2
$$
である。足すと $(110111)_2=32+16+4+2+1=55$ で、$11\times5=55$ と一致する。
2 進法の掛け算 1011×101。各段は 0 か、上の数を 1 桁ずつずらしたもの
コンピュータが 2 進法で計算するのは、数字が 2 種類なら電気の「切・入」で表せ、九九も 4 通りで済むからである。
例と反例：どの条件が効いているか
筆算の正しさは、「数字は $0$〜$9$」「割り算の各段では引けるだけ引く」という条件に支えられている。これらを外すと何が崩れるかを確かめる。
| 外した条件 | 崩れる主張 | ボックス |
|---|---|---|
| 数字を $0$〜$9$ に限る | 表し方の一意性（thm-ila-unique） | ex-ila-digit10 |
| 各段で $10^ib$ を引けるだけ引く | 各段の商が 1 桁（thm-ila-div の 1） | ex-ila-toofew |
| 余りを $b$ 未満にする | 商と余りの一意性 | ex-ila-toofew |
| 割る数の全桁で比べる（上の 1 桁どうしで見積もるだけにする） | 見積もった商がそのまま正しい | ex-ila-trial |
数字の範囲 $0\le d_k\le9$ を外すと、thm-ila-unique の一意性が崩れる。
- $12=1\cdot10+2=0\cdot10+12$。一の位に $12$ を許すと、2 通りに書ける。
- $100=1\cdot10^2+0\cdot10+0=0\cdot10^2+10\cdot10+0=0\cdot10^2+9\cdot10+10$。3 通りに書ける。
- $19=1\cdot10+9=2\cdot10+(-1)$。負の数字を許しても 2 通りになる。
証明のどこが使えなくなるかというと、prf-ila-unique の段 3 で「$0\le d_0\le9$ だから $d_0$ は $10$ で割った余り」と言えなくなる。
- $7394\mathbin{÷}23$ の百の位の段で、$2300$ を $3$ 回でなく $2$ 回だけ引いたとする。残りは $7394-4600=2794$ で、$2794\ge2300=10^2\cdot23$ である。prf-ila-div の仮定「$r_i<10^ib$」が崩れ、次の十の位の段では $\lfloor2794/230\rfloor=12$ となって、商の数字が $9$ を超えてしまう。
- 途中でやめて $7394=23\times320+34$ と書くと、等式は正しいが $34\ge23$ なので $34$ は余りではない。$0\le r< b$ を満たす組 $(321,11)$ だけが、除法の原理 の商と余りである。
さらに先へ
- 多項式の筆算：prop-ila-mul と thm-ila-div の $10$ を文字 $x$ に置きかえると、多項式の掛け算・割り算の筆算になる。多項式では繰り上がりがないので、手順はかえって簡単になる。これは 多項式の筆算と組立除法 で扱う（Sho08 §17.1）。
- 繰り上がりを後回しにする：掛け算の筆算で、位ごとの積を全部集めてから最後に 1 回だけ繰り上げても同じ答えになる。この見方で積の各位は「畳み込み」になる。掛け算の筆算と畳み込み で扱う。
- 平方根の筆算：$(10a+d)^2=100a^2+(20a+d)d$ という分配法則の式から、平方根を 1 桁ずつ求める筆算（開平法）が得られる。開平法：平方根の筆算 で扱う。
- 割り算を小数点以下まで続けると、余りは $0$〜$b-1$ の $b$ 通りしかないので、いつか同じ余りがくり返し、分数の小数表示は循環する（実数とは何か：無理数の証明）。
- 商と余りの存在と一意性（除法の原理）は、整数の割り算と互除法 で整列性から証明している。この記事の thm-ila-div は、その商と余りを実際に 1 桁ずつ作る手順である。コンピュータで大きな整数を扱うときの筆算の手順と計算量は Sho08 §3.3 に詳しい（割り算の各段の残りの評価は §3.3.4）。
関連項目
- 前提: 整数, 分配法則, 除法の原理, 数学的帰納法
- 前に読む: 筆算と分配法則, 整数の割り算と互除法, 数学的帰納法と整列性
- 次に読む: 剰余の定理と因数定理, 多項式の筆算と組立除法, 循環小数と分数, 倍数の判定法, n進法と記数法
- 関連（高校数学）: 分割の母関数, 数列の和と差分, 実数とは何か：無理数の証明, 掛け算の筆算と畳み込み
- 発展: 位取り記数法, 2進法, 多倍長演算
- 比較: 合同式の計算規則
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
