弃九法与校验位

全文分三层：

1. 通俗理解：弃九法、弃十一法，以及它们能查和不能查的错误
2. 实际用处：ISBN、EAN/UPC 条形码、银行卡 Luhn、身份证、IBAN，最后简单延伸到 CRC 和 Verhoeff
3. 数学原理：$\mathbb{Z}/n\mathbb{Z}$、环同态、核，以及为什么"模素数"能查得更全，每种方法都配手算例子

第一层：通俗理解

1.1 弃九法：用"数字和"检查算术

小学算 $3847\times 526$，得出 $2023522$，怎么快速检查对不对？

弃九法这样做：

1. 每个数的各位数字加起来，一直加到只剩一位（也可以中途随时扔掉 $9$，"弃九"就是这个意思）：
   • $3847$：$3+8+4+7=22$，$2+2=4$
   • $526$：$5+2+6=13$，$1+3=4$
2. 对这两个"代表数"做同样的运算：$4\times 4=16$，$1+6=7$
3. 算答案的数字和：$2023522$ 是 $2+0+2+3+5+2+2=16$，$1+6=7$
4. 两边都是 $7$，通过检查。

加法、减法也一样：

• $3847+526=4373$。左边 $4+4=8$，右边 $4+3+7+3=17$，$1+7=8$，一致。
• $3847-526=3321$。左边 $4-4=0$，右边 $3+3+2+1=9$，弃九后是 $0$，一致。

为什么数字和能代表一个数？ 因为"各位数字之和"和原数除以 $9$ 的余数相同。比如 $3847\div 9=427$ 余 $4$，正好等于数字和 $22\to 4$。原因是 $10$ 除以 $9$ 余 $1$，所以 $100,1000,\dots$ 除以 $9$ 也都余 $1$，每一位只按它"本身的大小"贡献余数。第三层会严格说明。

而"余数"有一个好性质：先算再取余，等于先取余再算。所以如果真答案除以 $9$ 余 $7$，你的答案却余 $5$，那答案一定错了。

1.2 弃九法能查出什么，查不出什么

能查出来的：大多数单个数字写错。比如把 $2023522$ 写成 $2023532$，数字和变成 $17\to 8\ne 7$，立刻发现。

查不出来的：

总结一下：只要错答案和正确答案的差是 $9$ 的倍数，弃九法就看不出来。 第一行"对调"是最常见的手误，它恰好就属于这一类：把相邻两位 $a,b$ 对调，差值是 $9\times(a-b)\times 10^k$。

1.3 弃十一法：用"交错和"补漏

换成除以 $11$ 的余数可以弥补对调的问题。因为 $10$ 除以 $11$ 余 $-1$（也就是余 $10$），所以

一个数除以 $11$ 的余数 $=$ 从个位开始，一加一减的交错和

例如：

• $3847$：$7-4+8-3=8$
• $526$：$6-2+5=9$
• $8\times 9=72$，$72$ 除以 $11$ 余 $6$
• $2023522$：$2-2+5-3+2-0+2=6$，一致 ✓

再看刚才弃九法漏掉的两个错误：

• 对调错误 $2203522$：交错和 $2-2+5-3+0-2+2=2\ne 6$，查出来了
• 多 $9000$ 的错误 $2032522$：除以 $11$ 余 $8\ne 6$，也查出来了

但弃十一法也有盲区：差值是 $11$ 的倍数的错误它查不出来，比如隔一位的两个数字对调（两位同号，交错和不变）。所以实际中常常两个一起用。差值必须同时是 $9$ 和 $11$ 的倍数，也就是 $99$ 的倍数，错误才会同时漏掉两个检查。

1.4 从"检查算术"到"检查号码"

校验位把这个想法反过来用。弃九法检查的是"计算结果"，校验位检查的是"抄写或输入的号码"：

1. 规定一个"指纹函数"，例如"加权求和再除以 $11$ 取余"
2. 发号码时多加一位（校验位），让整个号码的指纹等于某个固定值，比如 $0$
3. 有人抄号码或者扫描号码时，重新算一遍指纹。不对，就说明号码错了

人抄写时最常见的两类错误是：

• 单个数字错误：$\dots 4\dots \to \dots 7\dots$，约占人工输入错误的 $60\%$–$80\%$
• 相邻数字对调：$\dots 45\dots \to \dots 54\dots$，约占 $10\%$–$20\%$

设计校验位就是要选好"模数"和"权重"，让这两类错误全部能查出来。下面每种方案都会看它在这两点上表现如何。

第二层：实际用处

先给一张总表，后面逐个解释：

规律很明显：模数是素数（$11$、$97$）的方案效果最好。第三层会解释原因。

2.1 ISBN-10：模 $11$，校验位可以是 X

2007 年以前的书号有 $10$ 位 $a_1a_2\cdots a_{10}$，规则是

$$10a_1+9a_2+8a_3+\cdots+2a_9+1\cdot a_{10}\equiv 0 \pmod{11}.$$

因为模 $11$ 的余数有 $0$ 到 $10$ 共 $11$ 种，校验位 $a_{10}$ 有时需要等于 $10$，这时用罗马数字 X 表示。所以有些老书的书号以 X 结尾。

例子：ISBN 0-306-40615-2（维基百科等资料常用的示例书号）

总和 $=132=12\times 11\equiv 0\pmod{11}$ ✓

带 X 的例子：0-8044-2957-X。前 $9$ 位的加权和是 $0+72+0+28+24+10+36+15+14=199$，而 $199\equiv 1\pmod{11}$。校验位 $c$ 要满足 $1+c\equiv 0$，所以 $c=10$，写成 X。

查错能力：所有单个数字错误、所有对调（不只是相邻对调）都能查出来。

• 把第 8 位的 $1$ 写成 $7$：总和变为 $132+3\times 6=150\equiv 7\not\equiv 0$，查出
• 把 40615 写成 46015（$0$ 和 $6$ 对调）：总和 $\equiv 6\not\equiv 0$，查出

2.2 ISBN-13、EAN-13、UPC：模 $10$，权重 $1$ 和 $3$

超市条形码和现在的书号用的是这一套。规则是从左往右，权重 $1,3,1,3,\dots$ 交替：

$$a_1+3a_2+a_3+3a_4+\cdots+a_{13}\equiv 0\pmod{10}.$$

（$12$ 位的 UPC-A 从左起权重是 $3,1,3,1,\dots$，原理相同。）

例子：ISBN-13 978-0-306-40615-7

总和 $=100\equiv 0\pmod{10}$ ✓。UPC 示例 036000291452 用同样方法验算也通过。

查错能力：

• 单个数字错误：全部查出，因为乘 $1$ 或乘 $3$ 都不会把非零的差变成 $10$ 的倍数。
• 相邻对调：$a,b$ 对调后，总和变化 $\pm 2(a-b)$。当 $|a-b|=5$ 时，变化量是 $\pm 10\equiv 0$，查不出来。
  • 例子：把 40615 写成 40165（$6$ 和 $1$ 对调），得到 978-0-306-40165-7，校验照样通过。
  • 漏掉的 $5$ 对是 $0\leftrightarrow5$、$1\leftrightarrow6$、$2\leftrightarrow7$、$3\leftrightarrow8$、$4\leftrightarrow9$。

为了兼容条形码系统，ISBN-13 放弃了 ISBN-10 的模 $11$，所以查错能力反而变弱了。

2.3 银行卡号：Luhn 算法

Visa、Mastercard、银联等卡号的最后一位都是 Luhn 校验位（IBM 的 Hans Peter Luhn 1954 年提出）。规则是：

1. 从右往左数，第 $2,4,6,\dots$ 位乘以 $2$
2. 如果乘出来是两位数，就把两位数字加起来（等价于减 $9$），例如 $7\times 2=14\to 1+4=5$
3. 把所有位加起来，总和必须 $\equiv 0\pmod{10}$

例子：4111 1111 1111 1111（Visa 公开的测试卡号，常用于支付开发测试，不是真卡）

从右往左，偶数位（从左数的第 $1,3,5,\dots,15$ 位）要加倍：

• 最左的 $4$ 在加倍位：$4\to 8$
• 其他 $7$ 个加倍位都是 $1$：$1\to 2$，共 $7\times 2=14$
• $8$ 个不加倍的 $1$：共 $8$

总和 $=8+14+8=30\equiv 0\pmod{10}$ ✓

如果手误把倒数第二位写成 $2$（...1121），这一位在加倍位，变成 $4$。总和变为 $32\not\equiv 0$，查出。

查错能力：

• 单个数字错误：全部查出，因为"加倍并取数字和"把 $0,1,\dots,9$ 一一映射到 $0,2,4,6,8,1,3,5,7,9$，是一个置换
• 相邻对调：只漏一种，$09\leftrightarrow 90$。例如虚构的号码 4090 0000 0000 0003 和 4900 0000 0000 0003 都能通过 Luhn 校验
• 为什么只漏这一对，见第三层 3.6

2.4 中国居民身份证第 18 位：ISO 7064 MOD 11-2

$18$ 位身份证号 $a_1a_2\cdots a_{18}$ 中，前 $6$ 位是地区码，接下来 $8$ 位是出生日期，再 $3$ 位是顺序码，最后 $a_{18}$ 是校验码。规则是

$$\sum_{i=1}^{18} a_i\cdot 2^{18-i}\equiv 1\pmod{11},$$

其中 $a_{18}$ 如果需要等于 $10$，就写成 X。这就是为什么有些人的身份证号以 X 结尾，原因和 ISBN-10 完全一样。

把 $2^{18-i}$ 对 $11$ 取余，前 $17$ 位的权重是

$$7,\ 9,\ 10,\ 5,\ 8,\ 4,\ 2,\ 1,\ 6,\ 3,\ 7,\ 9,\ 10,\ 5,\ 8,\ 4,\ 2,$$

最后一位的权重是 $2^0=1$。实际计算时先求前 $17$ 位的加权和 $S$，再查表：

（这张表就是解方程 $S+c\equiv 1\pmod{11}$ 得到的结果。）

例子：11010519491231002X。这是国家标准 GB 11643—1999 里的示例号码，不对应真实个人。

$S=167=15\times 11+2$，所以 $S\equiv 2$，查表得校验码 X ✓。验证：$167+10=177=16\times 11+1\equiv 1$ ✓。

如果把生日 1231 抄成 1213（相邻的 $3,1$ 对调），算出的校验码会变成 $9$，与 X 不符，查出。

查错能力：所有单个数字错误和所有相邻对调都能查出来。

2.5 IBAN：模 $97$

国际银行账号（IBAN，欧洲、中东等地使用）用两位校验数字，规则是 ISO 7064 MOD 97-10：

1. 把开头 $4$ 个字符（国家代码和两位校验数字）挪到末尾
2. 字母换成两位数：$\mathrm{A}=10,\ \mathrm{B}=11,\ \dots,\ \mathrm{Z}=35$
3. 得到的大整数必须 $\equiv 1\pmod{97}$

例子：GB82 WEST 1234 5698 7654 32。这是 IBAN 标准文档常用的虚构示例账号。

• 挪动：WEST12345698765432GB82
• 换字母（$\mathrm{W}=32,\ \mathrm{E}=14,\ \mathrm{S}=28,\ \mathrm{T}=29,\ \mathrm{G}=16,\ \mathrm{B}=11$）：

$$N=3214282912345698765432161182$$

• 手算 $N\bmod 97$ 时可以分段：先取一段，求余，再把余数接到后面的数字前面，继续求余：

$$\begin{aligned} 321428291 &\equiv 70 \pmod{97}\\ 702345698 &\equiv 29 \pmod{97}\\ 297654321 &\equiv 24 \pmod{97}\\ 2461182 &\equiv 1 \pmod{97}\ \checkmark \end{aligned}$$

这种分段算法成立，也是因为取模是环同态，第三层会说明。

生成校验位时，先把校验位当成 00 算出 $N_0$，校验位就是 $98-(N_0\bmod 97)$。这个例子里算出来正好是 $82$。

为什么选 $97$：$97$ 是小于 $100$ 的最大素数。两位校验数字最多能表示 $100$ 种值，$97$ 几乎全用上了，而且它是素数，查错能力最强。IBAN 能查出所有单字符错误和所有相邻数字对调，实际漏检率约为 $1/97\approx 1\%$。

2.6 延伸：CRC 和 Verhoeff

第三层：数学原理

3.1 同余与 $\mathbb{Z}/n\mathbb{Z}$

固定正整数 $n$。如果 $n\mid a-b$，就说 $a\equiv b\pmod n$。这是一个等价关系，$a$ 的等价类记为

$$\bar a = a+n\mathbb{Z}=\{\dots,a-n,\ a,\ a+n,\ \dots\}.$$

全部等价类构成 $\mathbb{Z}/n\mathbb{Z}=\{\bar 0,\bar 1,\dots,\overline{n-1}\}$，运算定义为

$$\bar a+\bar b=\overline{a+b},\qquad \bar a\,\bar b=\overline{ab}.$$

3.2 取模映射是环同态

定义

$$\pi:\mathbb{Z}\to\mathbb{Z}/n\mathbb{Z},\qquad \pi(a)=\bar a.$$

由 3.1 的运算定义直接可得

$$\pi(a+b)=\pi(a)+\pi(b),\qquad \pi(ab)=\pi(a)\,\pi(b),\qquad \pi(1)=\bar 1,$$

所以 $\pi$ 是一个（满的）环同态。用文字说就是"先算再取余 $=$ 先取余再算"，也就是

$$\overline{ab}=\bar a\,\bar b .$$

弃九法就是取 $n=9$ 的情形：要检查 $c\stackrel{?}{=}ab$，只需检查 $\bar c\stackrel{?}{=}\bar a\,\bar b$ 在 $\mathbb{Z}/9\mathbb{Z}$ 里是否成立。$\mathbb{Z}/9\mathbb{Z}$ 只有 $9$ 个元素，计算量很小。

逻辑方向要注意：

$$c=ab\ \Longrightarrow\ \pi(c)=\pi(a)\pi(b),$$

但反过来不成立。所以弃九法只能否定，不能肯定。

IBAN 的分段求余也是同态性质的应用。设 $N=A\cdot 10^k+B$，那么

$$\pi(N)=\pi(A)\,\pi(10)^k+\pi(B),$$

所以可以先把 $A$ 换成它的余数 $r$，再算 $r\cdot 10^k+B$ 的余数，结果不变。

3.3 为什么"$10\equiv 1$"推出数字和

设 $N=\sum_{k=0}^{m} d_k\,10^k$，其中 $d_k\in\{0,\dots,9\}$ 是各位数字。用同态 $\pi:\mathbb{Z}\to\mathbb{Z}/9\mathbb{Z}$，

$$\pi(N)=\sum_{k=0}^{m}\pi(d_k)\,\pi(10)^k=\sum_{k=0}^{m}\bar d_k\cdot\bar 1^{\,k}=\overline{\textstyle\sum_k d_k},$$

因为 $10=9+1$，所以 $\pi(10)=\bar 1$。也就是说，

$$N\equiv d_0+d_1+\cdots+d_m\pmod 9 .$$

模 $3$ 同理，因为 $10\equiv 1\pmod 3$。这就是"数字和被 $3$ 整除则原数被 $3$ 整除"的原因。

换成模 $11$：$10=11-1$，所以 $\pi(10)=\overline{-1}$，于是

$$N\equiv\sum_{k=0}^{m}(-1)^k d_k = d_0-d_1+d_2-\cdots\pmod{11},$$

这就是交错和。

3.4 核是 $9\mathbb{Z}$：哪些错误查不出

$$\ker\pi=\{a\in\mathbb{Z}:\ \pi(a)=\bar 0\}=9\mathbb{Z}.$$

设正确答案是 $c$，写下的答案是 $c'$，错误量为 $e=c'-c$。那么

$$\pi(c')=\pi(c)\iff \pi(e)=\bar 0\iff e\in\ker\pi=9\mathbb{Z}.$$

所以一个错误查不出来，当且仅当错误量落在核里。这是同态最基本的性质：$\pi(x)=\pi(y)\iff x-y\in\ker\pi$。由第一同构定理，$\mathbb{Z}/\ker\pi\cong\mathbb{Z}/9\mathbb{Z}$，核里的差别在像里完全看不出来。

逐一对照 1.2 的表格：

• 单个数字错误：第 $k$ 位从 $a$ 变成 $b$，错误量 $e=(b-a)10^k$。因为 $\gcd(10,9)=1$，所以 $e\in 9\mathbb{Z}\iff 9\mid b-a\iff\{a,b\}=\{0,9\}$。
• 相邻对调：第 $k+1$ 位和第 $k$ 位分别是 $a,b$，对调后错误量为 $$e=(b-a)10^{k+1}+(a-b)10^k=9\,(b-a)\,10^k\in 9\mathbb{Z},$$ 所以永远查不出来。
• 模 $11$：同一个相邻对调，$e=9(b-a)10^k\equiv 9(b-a)(-1)^k\pmod{11}$。因为 $11$ 是素数，$9\not\equiv 0$，而 $0<|b-a|\le 9$ 时 $b-a\not\equiv 0$，所以 $e\not\equiv 0$，一定查得出。
• 隔一位对调：$e=(b-a)(10^{k+2}-10^k)=99\,(b-a)\,10^k$，同时属于 $9\mathbb{Z}$ 和 $11\mathbb{Z}$，两种方法都查不出。

3.5 加权校验位的一般框架，以及素数为什么重要

所有"加权和"型校验位都可以写成

$$\varphi(a_1,\dots,a_m)=\sum_{i=1}^{m} w_i\,a_i\ \in\ \mathbb{Z}/n\mathbb{Z},\qquad \text{合法号码}\iff\varphi=\bar t .$$

$\varphi$ 是从 $(\mathbb{Z}/n\mathbb{Z})^m$ 到 $\mathbb{Z}/n\mathbb{Z}$ 的模同态（线性映射），所以查错分析和 3.4 一样：错误向量 $e$ 查不出来，当且仅当 $e\in\ker\varphi$。

(1) 单个数字错误：第 $i$ 位从 $a$ 变成 $b$，$\varphi$ 的变化量是 $w_i(b-a)$。

(2) 第 $i,j$ 位对调：设原来分别是 $a,b$，变化量是

$$w_i(b-a)+w_j(a-b)=(w_i-w_j)(b-a).$$

因为数字满足 $0\le a,b\le 9$，所以 $a\ne b$ 时 $b-a\in\{\pm1,\dots,\pm9\}$。

逐一检查：

• ISBN-10（$p=11$，$w_i=11-i$）：$w_i\in\{1,\dots,10\}$ 全部非零；对任意 $i\ne j$，$w_i-w_j=j-i\in\{\pm1,\dots,\pm 9\}$ 也非零。所以单个错误和任意位置的对调都能查出。校验位如果是 $10$，就必须写成 X，这是用素数 $11$ 而不是 $10$ 付出的代价。
• 身份证 MOD 11-2（$p=11$，$w_i=2^{18-i}$）：$2$ 在 $\mathbb{Z}/11\mathbb{Z}$ 中可逆，所以每个 $w_i\ne 0$。相邻两位的权重差是 $$w_i-w_{i+1}=2^{k+1}-2^{k}=2^{k}\ne\bar 0,$$ 所以相邻对调都能查出。另外，$2$ 是模 $11$ 的原根，$2^1,\dots,2^{10}$ 恰好取遍 $\{\bar1,\dots,\overline{10}\}$，因此任意两位只要相距不是 $10$ 的倍数，权重就不同，对调也能查出。
• IBAN MOD 97-10（$p=97$，按十进制数字看，$w=10^k$）：$10^k$ 可逆；相邻差 $10^{k+1}-10^k=9\cdot 10^k$ 可逆。$10$ 在 $\mathbb{Z}/97\mathbb{Z}$ 中的阶是 $96$，所以权重在很长一段内互不相同。

反例：模数不是素数时，零因子会造成漏检

• EAN（$n=10$，权重 $1,3$）：
  • 单个错误：$w\in\{1,3\}$，在 $\mathbb{Z}/10\mathbb{Z}$ 中可逆（$\gcd(3,10)=1$），所以全部能查出。
  • 相邻对调：变化量 $(3-1)(b-a)=2(b-a)$。但 $\bar 2$ 是 $\mathbb{Z}/10\mathbb{Z}$ 中的零因子：$\bar 2\cdot\bar 5=\bar 0$。所以 $b-a=\pm 5$ 时变化量为 $\bar 0$，查不出来。这正是 2.2 里 40615 改成 40165 仍能通过的原因： $$(3-1)(1-6)=-10\equiv 0\pmod{10}.$$
• 弃九法（$n=9$，权重全是 $1$）：相邻对调时 $w_i-w_j=0$，任何对调都查不出。

3.6 Luhn 为什么只漏 $09\leftrightarrow 90$

Luhn 不是纯粹的加权和。设"加倍取数字和"函数为

$$\delta(x)=\begin{cases}2x, & 0\le x\le 4,\\ 2x-9, & 5\le x\le 9,\end{cases}$$

它的取值表是

（注意 $\delta(x)\equiv 2x\pmod 9$，因为数字和不改变模 $9$ 的余数，这里又用到了 3.3。）

单个错误：如果发生在不加倍的位置，变化量是 $b-a\not\equiv 0\pmod{10}$；如果发生在加倍的位置，变化量是 $\delta(b)-\delta(a)$。从上表可以看出 $\delta$ 是 $\{0,\dots,9\}$ 上的置换（单射），所以 $a\ne b$ 时 $\delta(a)\ne\delta(b)$，并且两者都在 $0$ 到 $9$ 之间，差不可能是 $10$ 的倍数。因此单个错误全部能查出。

相邻对调：相邻两位中恰好一位加倍。设原来加倍位是 $a$、普通位是 $b$，对调后加倍位是 $b$、普通位是 $a$。总和的变化量为

$$\big(\delta(b)+a\big)-\big(\delta(a)+b\big)=f(b)-f(a),\qquad f(x):=\delta(x)-x .$$

计算 $f(x)\bmod 10$：

在 $\mathbb{Z}/10\mathbb{Z}$ 中，$f$ 只有一次"撞车"：$f(0)=f(9)=0$。所以 $a\ne b$ 时，

$$f(a)\equiv f(b)\pmod{10}\iff\{a,b\}=\{0,9\},$$

也就是说，Luhn 只漏掉 $09\leftrightarrow 90$ 这一种相邻对调。直观上，$0$ 加倍还是 $0$，$9$ 加倍是 $18\to 9$，两者都是 $\delta$ 的不动点，所以无论哪一位加倍，总和都一样。