如果你的身份证号最后是 X，下面这些事你大概都碰到过：网站的输入框只认数字；客服问你“X 是大写还是小写”；朋友好奇，你的号码怎么带个字母。

如果你的号码最后是数字，你身边也一定有尾号是 X 的人。假如号码的前 17 位足够随机，大约每 11 个人里就有 1 个。

X 不是什么特殊标记，它代表的就是数字 10。可一个号码里为什么会算出 10？为什么不干脆用数字？这得从最后一位是干什么的说起。

按国家标准，身份证号分四段。前 6 位是地址码，表示登记户口时所在的县区。接着 8 位是出生日期。再往后 3 位是顺序码，给同一地方、同一天出生的人排个号，其中最后一位单数给男性、双数给女性。最后 1 位是校验码。

前 17 位都在记录关于你的信息。只有最后一位什么也不记录，它是用前 17 位算出来的。

1984 年起签发的老身份证，号码是 15 位：出生年份只写两位，也没有这最后一位。1999 年修订国家标准，同年 10 月 1 日起，新编的号码改成 18 位：年份补全成四位，末尾加上校验码。

算法只有四步。拿图 1 的示例号码走一遍。

第一步，给前 17 位各配一个固定的权重：7、9、10、5、8、4、2、1、6、3、7、9、10、5、8、4、2。第二步，每一位乘上自己的权重。第三步，把 17 个乘积加起来。第四步，看这个和除以 11 余几，再查一张表，换成校验码。

除以 11，余数可能是 0 到 10，一共 11 种。其中 10 种都能对应一个数字，剩下那一种只能用一个新符号来写。国家标准选了罗马数字里的十：X。

那串权重也不是随便定的。从倒数第二位往前看，权重依次是 2、4、8、5、10、9……每次都是上一个乘 2，再取除以 11 的余数。那张对照表看着乱，背后其实是一句很整齐的话：把校验码也算进去（X 当 10，权重是 1），18 位的加权和除以 11，永远余 1。

校验码的用处只有一个：发现抄错。

号码是人一位一位抄、一位一位敲的，难免出错。荷兰数学家 Verhoeff 在 1969 年的博士论文里，统计了一万两千多个真实的抄写错误，结果很集中。

单个数字写错占了快八成，两位挨着写反占一成。一个好的校验码，至少要把这两类错全抓住。身份证的校验码做到了，还多做了一些。

隔 10 位对调这种错，人几乎不会犯。真正常见的两类错，一个也跑不掉。

X 带来的麻烦是实打实的：输入框不认，数据库要专门留一个能放字母的位置，有人写大写有人写小写。那么，能不能把 11 换成 10，校验码只用 0 到 9？

试试看。还是乘权重、相加，这回只看和的个位，也就是除以 10 的余数。

先看单个错字。某一位从 $a$ 改成 $b$，个位的变化是 $w(b-a)$ 的个位。要是权重是 2，把 0 写成 5，变化是 10，个位不变，查不出来。图 4 下半部分画的就是这件事：乘 2 以后，0 和 5 撞成了同一个数。

想不撞车，权重只能选 1、3、7、9，也就是和 10 没有公因数的数。这四个数都是奇数。

再看相邻对调。挨着的两位数字 $a$、$b$ 写反，个位的变化是两个权重之差乘上 $b-a$。为了不撞车，这个差也得是 1、3、7、9 之一，至少得是奇数。可两个奇数相减，结果一定是偶数。

商品条形码就是这么取舍的。条形码（EAN-13）的权重是 1 和 3 交替，单个错字全抓，可是相差 5 的两个数字挨着写反（比如 27 写成 72），它就看不出来。

你也许会想：乘法太死板，换个花样呢？

银行卡号用的 Luhn 算法就换了花样。从右往左数，偶数位上的数字先翻倍，翻倍后是两位数，就把两位加起来（比如 7 翻倍是 14，再变成 1 + 4 = 5），最后全部相加看个位。“翻倍再相加”把 0 到 9 一对一地换成了另一串数字，所以单个错字全抓得住。

可它也有漏洞：09 写成 90，查不出来。这不是设计失误。下面这条定理说，无论你怎么换花样，漏洞都在。

整个证明的关键，只是一个小学生都会算的数：0 加到 9 等于 45，除以 10 余 5，不是 0。

Luhn 算法的漏洞，正好让这个证明现了形。图 6 的第三行，就是证明里的 $f(x)-g(x)$：十个数里少了一个 5，就一定有一个数出现两次。重复的是 0，对应的数字是 0 和 9，所以 09 和 90 分不出来。

同样的论证对任何偶数个符号都成立：0 加到 $n-1$，除以 $n$ 一定余 $n/2$。只要符号的个数是偶数，“换数字、相加”的办法就一定有漏网之鱼。要跳出来，最省事的办法是换成奇数个符号，比如 11 个。0 到 9 之外多出来的第 11 个，就是那个 X。

知道了这条定理，再看身边的号码，就能看出每一家做了什么取舍。

银行卡选了只用数字。代价是 09 和 90 分不出来，隔一位的对调（比如 123 写成 321）也一个都抓不住。条形码漏得更多：相邻对调里，大约每 9 次就漏 1 次。

书号走过一段回头路。老的 10 位 ISBN 也用除以 11，也有 X，任意两位对调都抓得住。2007 年书号改成 13 位，为了和商品条形码统一，换成了条形码的规则。X 没了，校验也变弱了。

身份证站在另一头：多付一个符号 X，换来两类常见错误一个不漏。企业的统一社会信用代码也是这个思路，只是走得更远：它用了数字加 21 个字母，一共 31 个字符，校验时除以 31。31 是奇数，也是质数。

只用 0 到 9，就真的没办法了吗？

有办法，但得把“加法”换掉。定理 3 的证明里，有一步悄悄用到了加法的一个性质：先加谁后加谁，结果都一样，所以十个差才能拆开、重新排队求和。要是“加法”的结果和顺序有关，这个证明就走不通了。

1969 年，Verhoeff 找到了一种和顺序有关的“加法”：正五边形的对称。一个正五边形可以转 0 到 4 格（每格 72°），也可以先翻过来再转，一共 10 种摆法，正好对应 10 个数字。两种摆法“相加”，就是先做一个、再做另一个。

用这种“加法”代替普通加法，再配上一套打乱数字的规则，Verhoeff 造出了一种只用 0 到 9 的校验码：单个错字和相邻对调，一个不漏。印度的身份证号 Aadhaar 是 12 位纯数字，最后一位用的就是 Verhoeff 算法。2004 年，德国的 Damm 又找到另一种办法，只需要查一张 10 × 10 的表。

那我们的身份证为什么没用它？我没查到当年的讨论。一个合理的猜测是：模 11 有现成的国际标准，手算只要乘法和除法；Verhoeff 要查三张表，没有计算机几乎没法验。

最后说清楚校验码的边界。

第一，它只报警，不定位。算出来对不上，你只知道“有地方错了”，不知道错在哪一位，更没法自动改对。

任意两个合法的号码至少有两位不同，改一位一定会落到不合法的号码上；可从这个不合法的号码出发，改不同的位，可能回到好几个不同的合法号码，你分不清原来是哪个。想要自动纠错，就得多加几位冗余。二维码脏了一块还能扫，靠的就是这种多加的冗余，那是另一个故事。

第二，它防手滑，不防造假。算法是公开的，谁都能算出一个“合法”的号码。校验码对得上，只说明这串数字没抄错，不说明它真的属于某个人。

下次填表时，如果你看到一个号码以 X 结尾，可以多看它一眼。

它不是瑕疵，也不是什么特殊身份。它是一道算术题的答案：想靠加法抓住所有单个错字和相邻对调，十个数字不够用，因为 0 加到 9 等于 45。所以借来了第 11 个符号。

那个 X 不是多出来的，
是完美的价钱。

If your ID number ends in X, you have probably run into all of these: a website whose input box accepts only digits; a customer service agent asking whether “the X is upper or lower case”; friends wondering why your number has a letter in it.

If yours ends in a digit, you surely know someone whose number ends in X. Assuming the first 17 digits are random enough, that's about 1 person in 11.

The X is not a special mark. It simply stands for the number 10. But how does a 10 end up in an ID number? Why not just use a digit? To answer that, we have to start with what the last digit is for.

Under the national standard, an ID number has four parts. The first 6 digits are the address code: the county or district where your household was registered. The next 8 are your date of birth. The next 3 are the sequence code, which numbers the people born in the same place on the same day; its last digit is odd for men and even for women. The final digit is the check digit.

The first 17 digits all record something about you. Only the last one records nothing: it is computed from the first 17.

The old ID cards issued from 1984 had 15-digit numbers: the birth year took only two digits, and there was no check digit at the end. The national standard was revised in 1999, and from October 1 of that year new numbers had 18 digits: the year was written out in full, and a check digit was added at the end.

The algorithm has just four steps. Let's walk through them with the sample number in Figure 1.

First, give each of the first 17 digits a fixed weight: 7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2. Second, multiply each digit by its weight. Third, add up the 17 products. Fourth, find the remainder when this sum is divided by 11, and look it up in a table to get the check digit.

Divided by 11, the remainder can be anything from 0 to 10: 11 possibilities. Ten of them can each be matched with a digit, and the one left over needs a new symbol. The national standard chose the Roman numeral for ten: X.

The weights aren't arbitrary either. Reading leftward from the second-to-last digit, they go 2, 4, 8, 5, 10, 9, …: each one is the previous one doubled, then reduced to its remainder on division by 11. The lookup table looks messy, but behind it is one tidy statement: count the check digit too (X as 10, with weight 1), and the weighted sum of all 18 digits always leaves remainder 1 when divided by 11.

A check digit has exactly one job: to catch copying errors.

People copy and type numbers one digit at a time, and mistakes are bound to happen. In a 1969 doctoral thesis, the Dutch mathematician Verhoeff tallied more than 12,000 real copying errors, and they fell into just a few kinds.

Single-digit errors make up almost 80 percent, and swapped neighbors about 10 percent. A good check digit should at least catch every error of these two kinds. The ID check digit does, and a little more.

Nobody really swaps two digits 10 places apart. The two kinds of error that actually happen never get through.

The trouble the X causes is real: input boxes reject it, databases need a field that can hold a letter, and some people write it upper case while others write it lower case. So could we replace 11 with 10 and make the check digit use only 0 to 9?

Let's try. Multiply by the weights and add, as before, but this time look only at the units digit of the sum, that is, its remainder on division by 10.

Start with single-digit errors. If one digit changes from $a$ to $b$, the units digit of the sum shifts by the units digit of $w(b-a)$. With a weight of 2, writing a 0 as a 5 changes the sum by 10, which leaves the units digit as it was, so the error goes unnoticed. The bottom half of Figure 4 shows exactly this: after doubling, 0 and 5 collide.

To avoid collisions, the weight has to be 1, 3, 7 or 9, the numbers that share no factor with 10. All four are odd.

Now adjacent transpositions. If two neighboring digits $a$ and $b$ are written in the wrong order, the units digit shifts by the difference of the two weights times $b-a$. To avoid collisions, that difference must also be 1, 3, 7 or 9, so at the very least it must be odd. But the difference of two odd numbers is always even.

Product barcodes make exactly this trade-off. The barcode (EAN-13) alternates the weights 1 and 3. It catches every single-digit error, but when two neighboring digits that differ by 5 are swapped (27 written as 72, say), it cannot tell.

You might think: multiplication is too rigid, so why not try something fancier?

The Luhn algorithm used for bank card numbers does just that. Counting from the right, every digit in an even position is doubled first; if the result has two digits, they are added together (7 doubled is 14, which becomes 1 + 4 = 5). Then everything is added up and you look at the units digit. “Double, then add the digits” turns 0 to 9, one for one, into a different sequence of digits, so every single-digit error is caught.

But it has a hole too: write 09 as 90 and it won't notice. This is not a design mistake. The next theorem says that however fancy you get, the hole is always there.

The whole proof turns on a sum any primary-school child can do: 0 through 9 add up to 45, which leaves remainder 5 when divided by 10, not 0.

The hole in Luhn's algorithm is this proof made visible. The third row of Figure 6 is the $f(x)-g(x)$ from the proof: with a 5 missing from its ten numbers, some number has to appear twice. The repeated one is 0, which comes from the digits 0 and 9, so 09 and 90 can't be told apart.

The same argument works for any even number of symbols: the sum of 0 through $n-1$, divided by $n$, always leaves remainder $n/2$. As long as the number of symbols is even, any “replace the digits, then add” scheme lets something slip through the net. The easiest way out is an odd number of symbols, say 11. The 11th symbol, the one beyond 0 to 9, is that X.

With this theorem in hand, look at the numbers around you and you can see the trade-off each one made.

Bank cards chose digits only. The price: 09 and 90 can't be told apart, and not a single jump transposition (123 written as 321, say) is caught. Barcodes miss even more: about 1 in every 9 adjacent transpositions gets through.

Book numbers took a step backward. The old 10-digit ISBN also divides by 11, also has an X, and catches every swap of any two digits. In 2007 ISBNs grew to 13 digits and, to match product barcodes, switched to the barcode rule. The X disappeared, and the check got weaker.

The ID number stands at the other end: it pays for one extra symbol, X, and in return catches every error of the two common kinds. The Unified Social Credit Code for companies follows the same idea and goes further: it uses the digits plus 21 letters, 31 characters in all, and its check divides by 31. And 31 is odd, and prime too.

So is there really no way to do it with just 0 to 9?

There is, but “addition” has to go. One step in the proof of Theorem 3 quietly used a property of addition: the order in which you add things doesn't matter, which is what let us split up the ten differences and regroup the sum. If the result of “addition” depended on the order, the proof would fall apart.

In 1969 Verhoeff found an “addition” in which order matters: the symmetries of a regular pentagon. A regular pentagon can be turned 0 to 4 notches (72° each), or flipped over and then turned, which gives 10 positions in all, one for each digit. To “add” two of them, you do one and then the other.

With this “addition” in place of ordinary addition, plus a set of rules that shuffle the digits, Verhoeff built a check digit that uses only 0 to 9 and lets no single-digit error or adjacent transposition through. India's ID number, Aadhaar, is 12 digits with no letters, and its last digit is computed with Verhoeff's algorithm. In 2004, Damm in Germany found another way that needs only a single 10 × 10 table.

So why didn't the Chinese ID number use it? I couldn't find any record of the discussions at the time. A reasonable guess: mod 11 already had an international standard and needs only multiplication and division by hand, while Verhoeff's method needs three lookup tables and is nearly impossible to check without a computer.

Finally, let's be clear about the limits of a check digit.

First, it raises the alarm but doesn't locate the error. If the result doesn't match, all you know is that “something is wrong”: not which digit, let alone how to fix it automatically.

Any two valid numbers differ in at least two places, so changing one digit always lands on an invalid number. But from that invalid number, changing different digits can lead back to several different valid numbers, and you can't tell which one was the original. To correct errors automatically, you need more redundant digits. A QR code with a smudge on it still scans thanks to exactly this kind of extra redundancy, but that's another story.

Second, it guards against slips, not forgeries. The algorithm is public, and anyone can compute a “valid” number. A matching check digit only means the digits weren't miscopied; it doesn't mean the number really belongs to anyone.

Next time you're filling in a form and see a number that ends in X, give it a second look.

It isn't a flaw, and it doesn't mark anyone as special. It is the answer to an arithmetic problem: if you want addition to catch every single-digit error and every adjacent transposition, ten digits aren't enough, because 0 through 9 add up to 45. So an 11th symbol was borrowed.

That X isn't extra.
It pays for perfection.