チェックディジット
概要
チェックディジット（check digit）とは、数字の列の最後に付ける検査のための 1 桁で、各桁に重みを掛けた和が法 $n$ で $0$ と合同になるように決め、番号の誤りは、誤りによる和の変化が $n$ で割り切れないときに見つかる。ISBN-10（重み $10,9,\dots,1$、法 $11$、最後の桁の $10$ は $\mathrm{X}$ と書く）では、11 が素数なので、1 桁の誤りと 2 つの異なる数字の入れ替え（隣り合わなくてもよい）は必ず見つかる。ISBN-13（重み $1,3,1,3,\dots$、法 $10$）では、1 桁の誤りは必ず見つかるが、隣り合う 2 つの異なる数字 $a,b$ の入れ替えは $\lvert a-b\rvert=5$ のときに限って見つからない。どちらの方式でも、見つからない 2 か所の誤りがある。
前提知識: 合同式の計算規則, 合同式の割り算と逆元
出発点：番号の打ち間違いを見つける
本には ISBN という番号がついていて、本を注文するときや図書館で探すときに使われる。番号を手で書き写したりキーボードで打ったりすると、1 桁を打ち間違えたり、隣り合う 2 つの数字を逆に打ったりすることがある。ISBN には、そのような間違いを見つけるための仕掛けがある。最後の 1 桁が、ほかの桁から計算で決まる 検査のための数字 になっているのである。
曜日の計算 では、日付の各部分に決まった数を掛けて足し、7 で割った余りを見た。ここでも同じように、各桁に重みを掛けて足し、ある数で割った余りを見る。
ある数学書の奥付には、10 桁の ISBN として 0-521-83378-7 が印刷されている（- は区切りで、数としては意味をもたない）。左から順に、桁に重み $10,9,8,\dots,1$ を掛けて足すと
$$
10\cdot0+9\cdot5+8\cdot2+7\cdot1+6\cdot8+5\cdot3+4\cdot3+3\cdot7+2\cdot8+1\cdot7
$$
$$
=0+45+16+7+48+15+12+21+16+7=187=11\cdot17
$$
で、11 で割り切れる（図 1）。10 桁の ISBN は、このように重みつきの和が 11 で割り切れるように作られている。
ISBN-10 の 0-521-83378-7 の 10 桁に、左から重み 10, 9, …, 1 を掛けた表。積の和は 187 で、11 × 17 になる。最後の桁が検査のための数字
- 7 桁目の 3 を 8 と打ち間違えて 0-521-83878-7 としたとする。7 桁目の重みは 4 なので、和は $4\cdot(8-3)=20$ だけ増えて $207$ になる。$207=11\cdot18+9$ で 11 で割り切れないので、どこかが間違っていることが分かる。
- 4 桁目と 5 桁目の 1 と 8 を逆に打って 0-528-13378-7 としたとする。4 桁目の重みは 7、5 桁目の重みは 6 なので、和の変化は
$$ (7\cdot8+6\cdot1)-(7\cdot1+6\cdot8)=62-55=7 $$
で、和は $194=11\cdot17+7$ になる。これも 11 で割り切れないので、間違いが分かる。
どちらの間違いも見つかった。これはたまたまなのか、それとも必ずそうなるのか。この記事では次の問いに答える。
- 検査のための数字は、ほかの桁からどう決まるか。→ def-chk-isbn10、def-chk-isbn13
- ISBN-10 では、1 桁の誤りや 2 つの数字の入れ替えは必ず見つかるか。→ thm-chk-isbn10
- 13 桁の ISBN-13 では、何が見つかり、何が見つからないか。→ thm-chk-isbn13
- 2 か所を同時に間違えたら、見つかるとは限らないのはなぜか。→ prop-chk-two
- 重みや割る数を変えると、何が起こるか。→ ex-chk-cx-plain、ex-chk-cx-weight2
高校の計算 この記事の言葉 大学の言葉 重みを掛けて足し、余りを見る 検査の式 線形な検査式（法 $n$ での内積） $\gcd(a,n)=1$ なら法 $n$ で割り算できる 1 桁の誤りが見つかる条件 法 $n$ の可逆元 素数 $p$ が $ab$ を割れば $a$ か $b$ を割る 入れ替えが見つかる理由 体には零因子がない 1 か所変えると必ず式が崩れる 誤りの検出 最小距離 2 の符号
言葉の準備：検査の式と誤りの種類
正の整数 $n$（法）と整数 $w_1,w_2,\dots,w_k$（重み）を決める。数字の列 $x_1x_2\cdots x_k$ が
$$
w_1x_1+w_2x_2+\cdots+w_kx_k\equiv0\pmod n
$$
をみたすとき、この列を 正しい番号 という。この式を 検査の式 という。最初の $k-1$ 桁を決めたとき、検査の式をみたすように決める最後の 1 桁 $x_k$ を チェックディジット（検査数字）という。
番号の誤りとして、次の 2 種類を考える。
(R1) 1 桁の誤り：ある 1 つの位置の数字が、別の数字に替わる。
(R2) 入れ替え：異なる 2 つの位置の、異なる 2 つの数字が入れ替わる（例：$\cdots18\cdots$ が $\cdots81\cdots$ になる）。2 つの位置が隣り合う場合を 隣り合う入れ替え という。
正しい番号に誤りが起きた列が検査の式をみたさないとき、その誤りは 見つかる という。検査の式をみたしてしまうと、その列も正しい番号に見えるので、誤りは見つからない。条件 (ii) で「異なる 2 つの数字」としたのは、同じ数字どうしを入れ替えても列は変わらず、誤りにならないからである。
誤りが起きると、検査の式の左辺がどれだけ変わるかを見ればよい。位置 $i$ の数字が $x_i$ から $x_i'$ に替わると、左辺は
$$
w_ix_i'-w_ix_i=w_i(x_i'-x_i)
$$
だけ変わる。位置 $i,j$ の数字が入れ替わると、左辺は
$$
(w_ix_j+w_jx_i)-(w_ix_i+w_jx_j)=(w_i-w_j)(x_j-x_i)
$$
だけ変わる（展開して確かめられる）。元の列は検査の式をみたしているので、誤りが見つかるのは、この変化が $n$ で割り切れないときである。
ISBN-10
ISBN-10 は 10 桁の番号 $x_1x_2\cdots x_{10}$ で、$x_1,\dots,x_9$ は $0$ から $9$ までの数字、$x_{10}$ は $0$ から $10$ までの数（$10$ は X と書く）であり、次の検査の式をみたす。
$$
10x_1+9x_2+8x_3+\cdots+2x_9+1\cdot x_{10}\equiv0\pmod{11}
$$
つまり法は $11$、重みは $w_i=11-i$（$i=1,2,\dots,10$）である。
ISBN-10 と次の節の ISBN-13 の検査の式、X の使い方、ISBN-10 から ISBN-13 への書き換えは Wei26 にある。
最初の 9 桁を決めると、$x_{10}$ はただ 1 つに決まる。$S=10x_1+9x_2+\cdots+2x_9$ とおくと、検査の式は $x_{10}\equiv-S\pmod{11}$ で、$0$ 以上 $10$ 以下の整数のうち 11 で割った余りが $-S$ と同じものはちょうど 1 つあるからである。$-S$ を 11 で割った余りが $10$ になることもあるので、最後の桁には $0$ から $9$ の数字のほかに X（$10$）が要る。
- ex-chk-start の最初の 9 桁 0-521-83378 では、$S=0+45+16+7+48+15+12+21+16=180$ で、$180=11\cdot16+4$ である。$x_{10}\equiv-4\equiv7\pmod{11}$ なので、チェックディジットは $7$ である。
- 別の本の奥付に印刷された ISBN-10 は 1717134815 である。最初の 9 桁で $S=10+63+8+49+6+15+16+24+2=193=11\cdot17+6$ なので、$x_{10}\equiv-6\equiv5\pmod{11}$ で、確かに最後の桁は $5$ である。
- 最初の 9 桁が 0-000-00006 なら $S=2\cdot6=12\equiv1$ で、$x_{10}\equiv-1\equiv10\pmod{11}$ となり、チェックディジットは X である。番号は 0-000-00006-X で、和は $12+10=22=11\cdot2$ である。
道具：法と互いに素な数を掛けても 0 にならない
$n$ を 2 以上の整数、$w$ を $\gcd(w,n)=1$ をみたす整数とする。整数 $e$ が $n$ で割り切れなければ、$we$ も $n$ で割り切れない。
方針：$we\equiv0$ と仮定し、$w$ の逆元を掛けて $e\equiv0$ を導く（背理法）。
$\gcd(w,n)=1$ なので、合同式の割り算と逆元 の定理「逆元をもつ条件」により、$w$ は法 $n$ で逆元 $u$ をもつ。つまり $uw\equiv1\pmod n$ となる整数 $u$ がある。$we\equiv0\pmod n$ だったとすると、両辺に $u$ を掛けて（合同式の計算規則 の定理「和・差・積の合同」）
$$
e\equiv1\cdot e\equiv(uw)e=u(we)\equiv u\cdot0=0\pmod n
$$
となり、$e$ が $n$ で割り切れることになって仮定に反する。よって $we$ は $n$ で割り切れない。$\square$
$n$ が素数 $p$ なら、$p$ で割り切れない $w$ はすべて $\gcd(w,p)=1$ をみたすので、lem-chk-coprime は「$p$ で割り切れない 2 つの数の積は $p$ で割り切れない」と言いかえられる。これは 合同式の割り算と逆元 の系「素数を法とする積が 0 と合同なら」の対偶である。
- 法 $10$ と $w=3$：$\gcd(3,10)=1$ である。$e=1,2,\dots,9$ について $3e$ は $3,6,9,12,15,18,21,24,27$ で、どれも 10 で割り切れない。
- 法 $10$ と $w=2$：$\gcd(2,10)=2$ である。$e=5$ は 10 で割り切れないが、$2\cdot5=10$ は割り切れる。lem-chk-coprime の仮定 $\gcd(w,n)=1$ を外すと、結論は成り立たない。
主定理 1：ISBN-10 は 1 桁の誤りも入れ替えも見つける
正しい ISBN-10 に起きた次の誤りは、必ず見つかる。
- 1 桁の誤り。
- 2 つの数字の入れ替え（隣り合わない 2 つの位置でもよい）。
方針：誤りによる検査の式の左辺の変化を、def-chk-scheme の後で求めた形に書き、それが 11 で割り切れないことを lem-chk-coprime で示す。11 は素数なので、11 で割り切れない数はすべて 11 と互いに素である。
段 1（1 桁の誤り）。位置 $i$ の数が $x_i$ から $x_i'$（$x_i'\ne x_i$）に替わると、左辺は $w_i(x_i'-x_i)$ だけ変わる。重み $w_i=11-i$ は $1$ 以上 $10$ 以下なので、11 で割り切れず、11 と互いに素である。また $x_i,x_i'$ はどちらも $0$ 以上 $10$ 以下なので、$e=x_i'-x_i$ は $-10\le e\le10$、$e\ne0$ をみたし、11 で割り切れない。lem-chk-coprime（$n=11$、$w=w_i$）により $w_i(x_i'-x_i)$ は 11 で割り切れず、誤りは見つかる。
段 2（入れ替え）。位置 $i< j$ の異なる数 $x_i\ne x_j$ が入れ替わると、左辺は $(w_i-w_j)(x_j-x_i)$ だけ変わる。$w_i-w_j=(11-i)-(11-j)=j-i$ で、$1\le i< j\le10$ から $1\le j-i\le9$ なので、11 と互いに素である。$e=x_j-x_i$ は段 1 と同じく $-10\le e\le10$、$e\ne0$ で、11 で割り切れない。lem-chk-coprime により変化は 11 で割り切れず、誤りは見つかる。$\square$
この性質と、次の主定理 2 の性質は、Wei26 にも述べられている。証明で効いているのは、法 $11$ が素数で、しかも重みとその差（$1$ から $10$ まで、$1$ から $9$ まで）と数字の差（$-10$ から $10$ まで）がどれも 11 の倍数にならないほど、11 が大きいことである。
隣り合う位置 $i,i+1$ では $w_i-w_{i+1}=1$ なので、入れ替えによる変化は $x_{i+1}-x_i$ である。ex-chk-start の 0-521-83378-7 で、隣り合う 2 桁を入れ替えた 9 通りの変化を並べる。
| 入れ替える位置 | 1・2 | 2・3 | 3・4 | 4・5 | 5・6 | 6・7 | 7・8 | 8・9 | 9・10 |
|---|---|---|---|---|---|---|---|---|---|
| 2 つの数字 | 0, 5 | 5, 2 | 2, 1 | 1, 8 | 8, 3 | 3, 3 | 3, 7 | 7, 8 | 8, 7 |
| 和の変化 | $5$ | $-3$ | $-1$ | $7$ | $-5$ | $0$ | $4$ | $1$ | $-1$ |
6・7 桁目は同じ数字 3 なので、入れ替えても番号は変わらず、誤りにならない。それ以外の 8 通りでは変化が 11 で割り切れず、どれも見つかる。4・5 桁目の変化 $7$ は ex-chk-start-errors の (2) と一致する。
0-521-83378-7 の 2 桁目の 5 と 9 桁目の 8 を入れ替えて 0-821-83375-7 とすると、$w_2-w_9=9-2=7$、$x_9-x_2=8-5=3$ なので、和は $7\cdot3=21$ 変わって $208=11\cdot18+10$ になる。11 で割り切れないので見つかる。
主定理 2：ISBN-13 の得意と不得意
ISBN-13 は 13 桁の番号 $x_1x_2\cdots x_{13}$ で、どの桁も $0$ から $9$ までの数字であり、次の検査の式をみたす。
$$
x_1+3x_2+x_3+3x_4+\cdots+3x_{12}+x_{13}\equiv0\pmod{10}
$$
つまり法は $10$、重みは奇数番目の位置で $1$、偶数番目の位置で $3$ である。
ISBN-10 と同じく、最初の 12 桁を決めると $x_{13}$ は $0$ から $9$ の中にただ 1 つに決まる（$x_{13}$ の重みは $1$ なので、$x_{13}\equiv-(x_1+3x_2+\cdots+3x_{12})\pmod{10}$）。法が $10$ なので、X は要らない。ISBN-10 の番号に対応する ISBN-13 は、先頭に 978 を付けて最初の 9 桁を続け、チェックディジットを計算し直したものである。
- ex-chk-start の本の奥付には、ISBN-13 として 978-0-521-83378-3 も印刷されている。最初の 12 桁 978052183378 に重み $1,3,1,3,\dots$ を掛けて足すと
$$ 9+21+8+0+5+6+1+24+3+9+7+24=117 $$
で、$x_{13}\equiv-117\equiv3\pmod{10}$ となり、チェックディジットは $3$ である。13 桁全体の和は $117+3=120$ で、10 で割り切れる。ISBN-10 のチェックディジット $7$ とは違う数になっていることに注意する（法も重みも違うから）。 - ex-chk-isbn10 の (2) の本の ISBN-13 は 978-1717134813 である。最初の 12 桁の和は $9+21+8+3+7+3+7+3+3+12+8+3=87$ で、$x_{13}\equiv-87\equiv3$ となり、確かに最後の桁は $3$ である。
正しい ISBN-13 について、次が成り立つ。
- 1 桁の誤りは必ず見つかる。
- 隣り合う 2 つの異なる数字 $a,b$ の入れ替えは、$\lvert a-b\rvert=5$ のときに限って見つからない。$\lvert a-b\rvert\ne5$ なら必ず見つかる。
方針：主定理 1 と同じく左辺の変化を調べる。ただし法 $10$ は素数ではないので、重みと 10 が互いに素かどうか、変化が 10 の倍数になるのはどんなときかを、具体的に調べる。
段 1（1 桁の誤り）。位置 $i$ の数字が $x_i$ から $x_i'$ に替わると、左辺は $w_i(x_i'-x_i)$ 変わる。$w_i$ は $1$ か $3$ で、$\gcd(1,10)=\gcd(3,10)=1$ である。$e=x_i'-x_i$ は $-9\le e\le9$、$e\ne0$ なので 10 で割り切れない。lem-chk-coprime（$n=10$）により変化は 10 で割り切れず、誤りは見つかる。
段 2（隣り合う入れ替えの変化）。隣り合う位置 $i,i+1$ の重みは $1$ と $3$ か、$3$ と $1$ なので、$w_i-w_{i+1}=\pm2$ である。位置 $i$ の数字を $a$、位置 $i+1$ の数字を $b$（$a\ne b$）とすると、入れ替えによる変化は
$$
(w_i-w_{i+1})(b-a)=\pm2(b-a)
$$
である。
段 3（10 で割り切れる条件）。$\pm2(b-a)$ が 10 で割り切れるのは、$2(b-a)=10m$ となる整数 $m$ があるとき、つまり $b-a=5m$ のとき、すなわち $b-a$ が 5 の倍数のときである。$a,b$ は $0$ から $9$ の異なる数字なので $-9\le b-a\le9$、$b-a\ne0$ で、この範囲の 5 の倍数は $\pm5$ だけである。よって、変化が 10 で割り切れる（誤りが見つからない）のは $\lvert a-b\rvert=5$ のときに限り、それ以外では誤りが見つかる。$\square$
段 3 で $2$ を約したところに、法 $10$ が素数でないことが現れている。$2$ は $10$ と互いに素でないので、lem-chk-coprime が使えず、$b-a$ が 10 の倍数でなくても $2(b-a)$ は 10 の倍数になりうる。見つからない隣り合う組 $(a,b)$ は $(0,5),(1,6),(2,7),(3,8),(4,9)$ とその逆の 10 組で、異なる 2 つの数字の並び 90 組のうちの 10 組である（図 2）。
ex-chk-isbn13 の 978-0-521-83378-3 の 4 桁目と 5 桁目は 0 と 5 で、差が 5 である。入れ替えて 978-5-021-83378-3 とすると、和は
$$
9+21+8+15+0+6+1+24+3+9+7+24+3=130
$$
で 10 で割り切れ、誤りは見つからない。変化は $130-120=10$ で、段 2 の $2(b-a)$ の形では、4 桁目の重みが 3、5 桁目の重みが 1 なので $(3-1)(5-0)=10$ である。
一方、7 桁目と 8 桁目の 1 と 8（差 7）を入れ替えた 978-0-528-13378-3 では、変化は $(1-3)(8-1)=-14$ で、和は $106$ になり、見つかる。
隣り合う 2 つの数字 a, b を入れ替えたときに、誤りが見つかるかどうかを表した図。左の ISBN-10（数字 0 から 9 の範囲）ではすべて見つかり、右の ISBN-13 では差が 5 の 10 組（赤）だけ見つからない
ここまでを表にまとめる。比べのために、重みをすべて $1$ にして数字の和を 10 で割った余りを見る方式も並べた（この方式は ex-chk-cx-plain で調べる）。
| 方式 | 法 | 重み | 1 桁の誤り | 隣り合う入れ替え | 重みの異なる離れた入れ替え | 重みの同じ位置の入れ替え |
|---|---|---|---|---|---|---|
| ISBN-10 | $11$ | $10,9,\dots,1$ | すべて見つかる | すべて見つかる | すべて見つかる | （重みはすべて異なる） |
| ISBN-13 | $10$ | $1,3,1,3,\dots,1$ | すべて見つかる | 差が 5 のときだけ見つからない | 差が 5 のときだけ見つからない | すべて見つからない |
| 数字の和 | $10$ | $1,1,\dots,1$ | すべて見つかる | すべて見つからない | すべて見つからない | すべて見つからない |
ISBN-13 で重みの異なる離れた 2 つの位置（奇数番目と偶数番目）の入れ替えも、変化は $\pm2(b-a)$ なので、段 3 と同じ理由で差が 5 のときだけ見つからない。重みの同じ 2 つの位置（どちらも奇数番目、またはどちらも偶数番目）の入れ替えでは、$w_i-w_j=0$ なので変化は $0$ で、まったく見つからない（ex-chk-cx-same）。
2 か所の誤りは見つかるとは限らない
主定理 1・2 は、誤りが 1 つ（1 桁の誤りか、1 回の入れ替え）のときの話である。2 つの桁が同時に替わると、見つからないことがある。これは ISBN の工夫が足りないからではなく、検査のための数字が 1 桁しかないことから必ず起こる。
ISBN-10 でも ISBN-13 でも、どの正しい番号についても、その番号の 2 つの桁を替えて別の正しい番号にする方法がある。つまり、見つからない 2 か所の誤りが必ずある。
方針：最初の桁を替え、チェックディジットを計算し直す。1 桁の誤りが必ず見つかること（主定理 1・2 の 1）を使って、チェックディジットも替わることを示す。
ISBN-10 で考える（ISBN-13 でも同じ）。正しい番号 $x=x_1x_2\cdots x_{10}$ をとり、$x_1$ を別の数字 $x_1'$ に替える。def-chk-isbn10 の後で見たとおり、最初の 9 桁 $x_1'x_2\cdots x_9$ に対してチェックディジット $c$ がただ 1 つ決まり、$x'=x_1'x_2\cdots x_9c$ は正しい番号である。
もし $c=x_{10}$ なら、$x'$ は $x$ と 1 桁目だけが違う正しい番号になる。すると、$x$ に「1 桁目を $x_1'$ にする」という 1 桁の誤りが起きても検査の式がみたされ、誤りが見つからないことになる。これは thm-chk-isbn10 の 1 に反する。よって $c\ne x_{10}$ であり、$x'$ は $x$ と 1 桁目と 10 桁目のちょうど 2 か所が違う正しい番号である。ISBN-13 でも、def-chk-isbn13 の後で見たチェックディジットのただ 1 つの決まり方と thm-chk-isbn13 の 1 を使えば、同じ議論ができる。$\square$
- 0-521-83378-7 の 1 桁目を 1 にすると、和は $10\cdot1=10$ 増えて $197\equiv10\pmod{11}$ になる。10 桁目を $x_{10}'$ にして和を 11 の倍数にもどすには $x_{10}'\equiv7-10\equiv8\pmod{11}$ とすればよく、1-521-83378-8 は和が $198=11\cdot18$ の正しい番号である。
- 9 桁目の 8 を 9 に、10 桁目の 7 を 5 にすると、和の変化は $2\cdot1+1\cdot(-2)=0$ で、0-521-83379-5 も正しい番号になる。このように、変化が打ち消し合う 2 か所の誤りは見つからない。
誤り訂正符号 の言葉では、正しい番号どうしの違う桁の個数の最小値（最小距離）が、ISBN-10 でも ISBN-13 でもちょうど $2$ だということである。主定理 1・2 の 1 は「最小距離が $2$ 以上」を、prop-chk-two は「最小距離が $2$ 以下」を述べている。最小距離が 2 の符号は、1 か所の誤りを見つけることはできても、どこが誤りかまでは分からない。
例と反例：重みと法の選び方
主定理 1・2 の証明で使ったのは、重み $w_i$ と法 $n$ が互いに素であること（1 桁の誤り）と、重みの差 $w_i-w_j$ と法 $n$ が互いに素であること（入れ替え）だった。これらを外すと、誤りを見逃す。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 重みの差 $w_i-w_j$ と法が互いに素（重みをすべて $1$ にすると、差は $0$ になる） | 数字の和を 10 で割る方式：314156 と 134156（ex-chk-cx-plain） | どの入れ替えも見つからない（1 桁の誤りは見つかる） |
| 重み $w_i$ と法が互いに素（法 $10$ で重み $2$ を使う。重みの差 $\pm1$ は 10 と互いに素のまま） | 重み $1,2,1,2,1$、法 $10$：31419 と 36419（ex-chk-cx-weight2） | 重み 2 の位置で、数字が 5 だけ替わる 1 桁の誤りが見つからない |
| 重みの差と法が互いに素（ISBN-13 では隣り合う重みの差 $\pm2$ が 10 と互いに素でない） | 978-0-521-83378-3 と 978-5-021-83378-3（ex-chk-isbn13-swap） | 差が 5 の隣り合う入れ替えが見つからない |
| 重みの差が $0$ でない（ISBN-13 の重みの同じ位置どうし） | 978-0-521-83378-3 と 975-0-821-83378-3（ex-chk-cx-same） | その位置の入れ替えはすべて見つからない |
| 誤りが 1 つだけ（定理の場合分けの外：2 か所の誤り） | 0-521-83378-7 と 0-521-83379-5（ex-chk-two） | 見つからない誤りがある（prop-chk-two） |
重みをすべて $1$、法を $10$ にして、数字の和が 10 で割り切れるように最後の桁を決める方式を考える。31415 に続けて $6$ を付けた 314156 は、和が $3+1+4+1+5+6=20$ で正しい番号である。
(1) 1 桁の誤りは見つかる。重み $1$ は 10 と互いに素なので、lem-chk-coprime が使える。たとえば 3 桁目の 4 を 9 にすると、和は 5 増えて 25 になり、10 で割り切れない。
(2) 入れ替えは見つからない。最初の 2 桁を入れ替えた 134156 も、和は同じ 20 である。足し算は順序によらないので、どこをどう入れ替えても和は変わらない。重みの言葉では $w_i-w_j=1-1=0$ で、変化 $(w_i-w_j)(x_j-x_i)$ がいつも $0$ になる。
和を 9 で割った余りを見ても同じで、倍数の判定法 の定理「各位の数字の和による判定」が示すとおり、数の各位の数字を並べ替えても 9 で割った余りは変わらない。この性質は Kaprekarの操作 で積極的に使う。
法を $10$、重みを $1,2,1,2,1$ とする。3141 に続けて最後の桁 $c$ を、$3+2\cdot1+4+2\cdot1+c=11+c$ が 10 で割り切れるように決めると $c=9$ で、31419 が正しい番号である。
2 桁目（重み $2$）の 1 を 6 に打ち間違えた 36419 では、和は $3+12+4+2+9=30$ で、10 で割り切れる。誤りは見つからない。変化は $2\cdot(6-1)=10$ で、ex-chk-coprime の (2) の $2\cdot5=10$ と同じことが起きている。重み $2$ の位置では、数字が $0\leftrightarrow5$、$1\leftrightarrow6$、$2\leftrightarrow7$、$3\leftrightarrow8$、$4\leftrightarrow9$ と替わる誤りがすべて見逃される。
一方、この方式では隣り合う重みの差が $\pm1$ で 10 と互いに素なので、隣り合う入れ替えはすべて見つかる。1 桁の誤りの検出だけが崩れている。
978-0-521-83378-3 の 3 桁目の 8 と 5 桁目の 5 を入れ替えると 975-0-821-83378-3 になる。3 桁目と 5 桁目の重みはどちらも $1$ なので、和は $120$ のまま変わらず、誤りは見つからない。2 つの数字の差は $3$ で、5 ではない。隣り合わない入れ替えでは、thm-chk-isbn13 の 2 の「差が 5 のときに限る」は成り立たない（定理の 2 は隣り合う入れ替えについての主張である）。
大学数学で見る：素数の法と体
thm-chk-isbn10 の証明の核心は、「11 で割り切れない 2 つの数の積は 11 で割り切れない」ことだった。0 から $p-1$ までの余りの世界（法 $p$ の剰余類）は、$p$ が素数なら、0 以外のどの数でも割り算ができる 体 になっている（合同式の割り算と逆元 の系「素数を法とすると 0 以外は逆元をもつ」）。体では、0 でない数どうしの積は 0 にならない。ISBN-10 が 1 桁の誤りも任意の入れ替えも見つけられるのは、法 11 の世界が体で、しかも 11 が数字の差 $-10,\dots,10$ を 0 にしないほど大きいからである。
法が素数でないときと、誤りの位置が分かっているときを開く
法 $10$ の世界では、$2\cdot5=10\equiv0$ のように、0 でない数どうしの積が 0 になることがある（このような数を零因子という）。ISBN-13 が差 5 の入れ替えを見逃すのは、重みの差 $2$ が零因子だからである。法を素数にすれば零因子はなくなるが、ISBN-10 のように 11 を法にすると余りが 11 通りになり、10 進法の 1 桁では書ききれないので X という記号が要る。
誤りが 1 桁で、その位置 $i$ が分かっているときは、正しい数字を 1 通りに決められる。検査の式は $w_ix_i\equiv-(\text{ほかの桁の重みつきの和})$ で、$w_i$ が法と互いに素なら逆元を掛けて $x_i$ が求まるからである（ISBN-10 では $x_i$ は $0$ 以上 $10$ 以下でただ 1 つ、ISBN-13 では $0$ 以上 $9$ 以下でただ 1 つ）。位置が分からないときに誤りを直すには、誤り訂正符号 のように検査のための桁を増やして最小距離を 3 以上にする必要がある。
演習
ISBN-10 の 0-521-8□378-7 の □ が汚れて読めない。□ に入る数字を求めよ。
解答を開く
□ は 6 桁目で、重みは $5$ である。□ を $x$ とすると、和は $0+45+16+7+48+5x+12+21+16+7=172+5x$ で、これが 11 で割り切れればよい。$172=11\cdot15+7$ なので $5x\equiv-7\equiv4\pmod{11}$。$5$ の法 $11$ での逆元は $9$（$5\cdot9=45=11\cdot4+1$）なので、$x\equiv9\cdot4=36\equiv3\pmod{11}$。$0\le x\le9$ から $x=3$ で、0-521-83378-7 にもどる。
ISBN-13 で、位置の分かっている 1 桁だけが読めないとき、その数字は $0$ から $9$ の中にただ 1 つに決まることを示せ。
解答を開く
読めない位置を $i$、その数字を $x$、ほかの桁の重みつきの和を $T$ とすると、検査の式は $w_ix+T\equiv0\pmod{10}$ である。$w_i$ は $1$ か $3$ で 10 と互いに素なので、法 $10$ での逆元 $u$（$w_i=1$ なら $u=1$、$w_i=3$ なら $u=7$。$3\cdot7=21\equiv1$）がある。両辺に $u$ を掛けると $x\equiv-uT\pmod{10}$ となり、$0$ 以上 $9$ 以下の $x$ はただ 1 つに決まる。2 つの数字 $x,x'$ がともに式をみたすとすると、thm-chk-isbn13 の 1 の証明と同じく $w_i(x-x')\equiv0$ から $x=x'$ となる、と考えてもよい。
さらに先へ
- 各桁に重みを掛けて足し、余りを見る計算は、日付から曜日を求める 曜日の計算 と同じ形である。
- 誤りを見つけるだけでなく直す方法は 誤り訂正符号 で扱う。そこでは 0 と 1 の列で、検査のための桁を何桁か付けて最小距離を大きくする。
- 2 つの数字を入れ替えると和の変化が $(w_i-w_j)(x_j-x_i)$ になる、という計算は、数字の並べ替えで作る数の性質を調べる Kaprekarの操作 でも使う。
- 法 $n$ での割り算と逆元は 合同式の割り算と逆元、いくつかの法を組み合わせる話は 中国剰余定理（高校数学） で扱う。
関連項目
- 前提: 合同式の計算規則, 合同式の割り算と逆元
- 前に読む: 曜日の計算, 倍数の判定法, 合同式の割り算と逆元
- 次に読む: Kaprekarの操作
- 関連（高校数学）: 中国剰余定理（高校数学）, RSA暗号（高校数学）, 合同式の計算規則
- 発展: 誤り訂正符号
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
