What is Check digit?

以人人都有，人人都必須要記得的身份證舉例，18位元數位組合的方式是：

4個碼解釋：

• 地址碼
  對於內地戶籍居民，地址碼是公民首次獲得身份號碼（例如新生兒出生登記、無戶口人員登記戶口）時所在縣（市、鎮、區）的行政區劃程式碼，如110102是北京市西城區，如果日後行政區劃出現調整或將戶口遷往外地地址碼也不會改變。由於新生兒通常根據屬人主義確定戶籍，故地址碼並不總能代表公民的出生地。
  對於港澳臺居民，地址碼根據居民的實際身份分配香港、澳門或臺灣的行政區劃程式碼，只精確到省級，第三位至第六位全部為0。[1][2][3]
• 出生日期碼
  表示公民出生的公曆年（4位元）、月（2位）、日（2位）。
• 順序碼
  是給同地址碼同出生日期碼的人編定的順序號，其中奇數分配給男性，偶數分配給女性。
• 校驗碼
  這裡採用的是ISO 7064:1983, MOD 11-2校驗碼系統。校驗碼為一位數，但如果最後採用校驗碼系統計算的校驗碼是「10」，礙於身份證號碼為18位元的規定，則以「X」代替校驗碼「10」。

思考：這個校驗碼是什麼？怎麼計算出來的?

校驗碼的原理

身份證的最後一位數位就是驗證碼，是通過前面的數位進行簡單的數學運算後計算出來的。下面我們就來看一下它究竟是怎麼算出來的，為什麼要進行這樣的運算。

為什麼會有 X？

最後一位只能有：1-10 裡面任意一個數位。

身份證後面的X並不是字母X，而是羅馬數位裡的10。為什麼不寫10呢？因為如果是10，寫出來身份證號碼就變成19位了。在編碼學中，不一樣的數位就不太容易儲存或者使用。

那麼問題來了，那為什麼最後一位的校驗碼會算出10呢？怎麼能算出1-10？
需要了解一下棄九數

「棄九數」驗演演算法的啟發

什麼叫棄九數？
比如有一個數位是：3217

• 如果把它每一位上的數位連續相加，3加2加1加7等於13。
• 繼續把13的每一位上的數位相加，1加3等於4。
• 直到得到個位數位4為止，這個4就叫做3217的棄九數。
  （其實這個棄九數就是3217除以9之後的餘數，只不過這種連續相加是一種快速演演算法法，很早以前的數學家就知道了。）

棄九數有什麼用呢？
它關鍵是要檢驗運算是否準確。 這個時候就有棄九法了，大家想一想，平常在計算加減乘除運算的時候，是不是經常容易算錯？
古人就很聰明，發明了棄九法。

比如，
現在要檢查一個乘法運算：$$ 3169 * 732 = 2319708 $$ 是否準確？

• 如果沒有別的方法的話，只能把它重新算一遍。
  但是棄九法是怎麼檢驗的？

1. 首先把3169的棄九數求出來，它是1。就是把每一位連續相加，最後得到個位數位1。
2. 732它的棄九數是3。
3. 2319708的棄九數是3。
4. 最後，(用等式遷移的思維)我們看一下，1乘以3是不是等於3，結果是準確的。$$ 1 * 3 = 3 $$

這說明前面非常大的數位的乘法運算，大概率是正確的。但是如果用棄九法檢驗是錯誤的，說明前面的運算一定是錯誤的。
這就是古人的驗算方法，充滿了智慧（智慧一定不是指莽幹）。

數學家只是有高維優勢，普通計算都一樣菜！

古代也有很多工程類計算，需要達到高精度的運算，前輩的數學家也需要檢驗。即使是一流的數學家，他也只是比普通人在考慮高維問題的時候具有優勢。但是如果是比純粹的加減乘除運算，數學家相對普通人來講，其實他們的差別並不大。

棄九法和同餘理論的關係

在棄九法發展的過程中，數學家們逐漸還認識到了棄七法、棄十一法、棄十三法等。這些方法其實都屬於今天初等數論中的同餘理論。

初等數論的教學大綱(高中數學課本)：

什麼是同餘理論?

（這裡只是初步入門介紹）
這種同餘理論在我們日常生活中比較常見的服務是什麼？
是計算校驗碼。 迴歸到正題了，身份證最後一位就是校驗碼。
注意：我說的校驗碼和你手機裡的簡訊驗證碼，不是一碼事，不是一個概念！注意區分。

為什麼需要校驗碼？

和我們生活最息息相關的校驗碼就在身份證上。我們平常在手機或者電腦經常需要輸入身份證號碼，假如沒有校驗碼，就是輸入17位數位，很容易發生不小心有一位輸錯了，鍵盤的數位挨著近，或者某兩位顛倒位置的情況。 那麼有了第18位元校驗碼，就能及時發現這種情況。正是因為一個小小的校驗碼，就可以保證整個系統的安全性。

身份證的校驗碼計算步驟（文字描述版）：

那它是怎麼算的？主要分三步：

1. 首先身份證號碼總共是17位，把前17位號碼依次乘以不同的係數。比如第一位乘以7，第二位乘以9，第三位乘以10，以此類推，這在數學上叫做加權因子。相同兩位加權因子不一樣，是為了區分數位。（加權因子的作用）

係數為：7、9、10、5、8、4、2、1、6、3、7、9、10、5、8、4、2

更通俗的說：第1位*7、第2位*9、第3位*10、第4位元*5、第5位*8、第6位*4、第7位*2、第8位元*1、第9位*6、第10位*3、第11位*7、第12位元*9、第13位*10、第14位元*5、第15位*8、第16位元*4、第17位*2

2. 把這17個乘積相加，然後取模11得餘數；

3. 餘數和校驗碼對應表：

計算出來的餘數和校驗碼錶對應，如果對應上了，就是正確。如果對應不上，就是錯誤。

身份證的校驗碼計算步驟（公式描述版）：

實際做一次操作

例子：410928198904015474

8 對應 4 ，正確！

同餘理論的驗證思想，無處不在

• 計算校驗碼，各種校驗碼，書後面的ISBN編號，錢上的編號，證件上的碼，密碼的...
• 訊號丟失
  在通訊中，訊號丟失是很正常的情況。為了防止訊號丟失所造成的損失。可以考慮在訊號後面加上校驗碼，這樣前面如果丟失一個數位的情況下，還可以通過校驗碼找回來。如果訊號是N位的，而我們在後面加上N-1位，那麼就可以有前面丟失了N-1位時還能找回完整的資訊。這種方法比單純的重複發一遍資訊要有效得多。
  編碼是代數中的一個應用分支，是非常有用的。

Reference

https://mp.weixin.qq.com/s/dRlWjcysXM7vsIC2Y4aEUg