10716 身份證會有連號嗎？

01-29

　　今天刷到一個有意思的問題：雙胞胎的身份證為什麼不是連號的？我們知道，身份證號碼的最後一位是校驗位，因為它的存在，身份證出現連號的幾率是很小的。但到底有沒有這種可能呢？

　　首先，要定義一下什麼叫「連號」。最簡單的定義方法，就是把身份證號看成一個 18 位數，如果兩個數相差 1，就叫「連號」。身份證號的末位可能出現 X，這種號碼就先忽略了。

　　因為校驗位是由前 17 位完全決定的，所以不會出現前 17 位都相同，只有最後一位相差 1 的情況。「連號」的身份證，必須在前 17 位中也有不同。

　　身份證號的結構為：6 位地區 + 8 位生日 + 3 位順序號 + 1 位校驗位。這樣，要找「連號」的身份證，就應該讓順序號相差 1，同時校驗位分別為 9 和 0。例如，兩個身份證號分別以 0059 和 0060 結尾。這樣的身份證號是否存在呢？這就需要弄懂校驗位是怎麼算出來的。

　　校驗位的演算法如下：

把第 1 到 17 位分別乘以 $2^{17}, 2^{16}, ldots, 2^1$ ，並相加；
把上一步的結果除以 11，取餘數；
用 12 減去這個餘數，並再次對 11 取余。

以題圖中「奧巴馬的身份證」為例：

$begin{array}{cc} & 3 & & 2 & & 6 & & 2 & & 2 & & 1 & & 1 & & 9 & & 6 & & 1 & & 0 & & 8 & & 0 & & 4 & & 0 & & 0 & & 9 & & times & 2^{17} & & 2^{16} & & 2^{15} & & 2^{14} & & 2^{13} & & 2^{12} & & 2^{11} & & 2^{10} & & 2^9 & & 2^8 & & 2^7 & & 2^6 & & 2^5 & & 2^4 & & 2^3 & & 2^2 & & 2^1 & & hline & 393216 & + & 131072 & + & 196608 & + & 32768 & + & 16384 & + & 4096 & + & 2048 & + & 9216 & + & 3072 & + & 256 & + & 0 & + & 512 & + & 0 & + & 64 & + & 0 & + & 0 & + & 18 & = & 789330 end{array}$

789330 除以 11 余 3，12 減 3 得 9，對 11 取余還是 9。你看，果然是偽造的身份證，校驗位都不對呢！

　　回到「連號」的問題。我們發現關鍵在於：當順序號差 1 的時候，對校驗位有什麼影響呢？校驗位演算法的關鍵，在於第一步中各位乘的係數。順序號的三位，乘的係數分別為 8, 4, 2。另外還要注意第三步中做了一次減法，所以當順序號的三位分別增加 1 的時候，校驗位會分別減去 8, 4, 2 —— 當然，如果結果小於 0 了，要加上 11。

　　要找「連號」的身份證號，就要讓校驗位由 9 變成 0，即校驗位減 9。如果順序號只是個位加 1，那麼校驗位會減 2，滿足不了要求。所以上文中說的以 0059 和 0060 結尾這樣的連號是不存在的。那麼，像 0599 和 0600 這樣，順序號十位發生變化的連號是否存在呢？注意在順序號十位加 1 的同時，個位減了 9。這二者分別導致校驗位減 4 和加 18，凈效果相當於加 3 或者減 8，也不行。那如果像 5999 和 6000 這樣，順序號百位進位呢？此時，順序號百位加 1，十位和個位都減 9，對校驗位的影響分別是減 8、加 36、加 18 —— 凈效果正是減 9！

　　於是，要找「連號」的身份證號，就應當去找末三位（順序號的後兩位和校驗位）都是 9 的號碼，然後把它加 1。可以驗證，如果把奧巴馬的身份證號的順序號改成 199，那麼校驗位就是 9 了。這樣，我們就找到了一對「連號」的身份證號：326221196108041999 和 326221196108042000。

　　如果你的身份證號是以 999 或 000 結尾的，那麼就很可能有一個人的身份證號跟你「連號」哦！這個人可能是你的親兄弟或親姐妹，也可能是與你同一天出生在同一個地區的一名異性。請珍惜這種緣份 ^_^