同余的幾個實際應用

曹宏舉，　郭巧麗

(1.大連外國語大學軟件學院，遼寧大連116044；　2.大連東軟信息學院計算機科學與技術系， 遼寧大連116023)

同余的幾個實際應用

曹宏舉1，郭巧麗2

(1.大連外國語大學軟件學院，遼寧大連116044；2.大連東軟信息學院計算機科學與技術系， 遼寧大連116023)

[摘要]同余是《近世代數(shù)》和《離散數(shù)學》等課程的重要概念之一，具有較廣泛的應用，然而傳統(tǒng)的教學和教材，大多只介紹理論應用，造成它除了理論之外毫無用處的錯覺.本文通過身份證號碼、通用商品條形碼、組織機構代碼和書號四方面切入，介紹同余關系在我們生活中的實際應用，豐富教學內容，增強趣味性.

[關鍵詞]同余； 校驗碼； 應用

1引言

無論是數(shù)學專業(yè)的《近世代數(shù)》(或《抽象代數(shù)》)[1，2]，還是計算機相關專業(yè)的《離散數(shù)學》等課程[3，4]，同余無疑是重要概念之一，在相關知識中具有廣泛應用.然而傳統(tǒng)的教材，往往在給出概念之后，就講解其他相關的理論知識，缺少應用背景，以至于學生在學習時感覺同余就是為了其他相關知識的介紹才引入的，甚至部分教師在教學中也有類似的感覺.雖然有論文探討同余理論的應用，但要么依然是進行一些枯燥的計算[5]，要么專業(yè)性過強[6]，不適合課堂授課時引用.同余的應用，除了我們熟知的在密碼學中的應用之外[3]，還具有廣泛的應用，如身份證號碼編碼規(guī)則、商品條形碼、書號等.通過本文對這些應用的介紹，可以豐富教學內容，擴展教師和學生對有關知識的了解，加深對有關知識的理解.

2定義

定義1[3]設m為正整數(shù)，a和b為整數(shù)，如果n|a—b，則稱a模m同余于b，或稱a與b模m同余，記為a≡b(modm).

3實例

3.1　居民身份證號中的同余

居民身份證號碼，是指用來證明居民身份的證件的編碼.中華人民共和國居民身份證的號碼是按照國家的標準編制的，由18位組成，每個人的居民身份證號碼都是唯一的.

居民身份證號碼編碼是根據(jù)《中華人民共和國國家標準GB11643-1999》[7]中有關公民身份號碼的規(guī)定編碼的，公民身份號碼是特征組合碼，由十七位數(shù)字本體碼和一位數(shù)字校驗碼組成.地址碼(身份證前六位)表示編碼對象第一次申領居民身份證時的常住戶口所在縣(市、旗、區(qū))的行政區(qū)劃代碼.生日期碼(身份證第七位到第十四位)表示編碼對象出生的年、月、日，其中年份用四位數(shù)字表示，年、月、日之間不用分隔符.順序碼(身份證第十五位到十七位)是縣、區(qū)級政府所轄派出所的分配碼，每個派出所分配碼為10個連續(xù)號碼，例如“000-009”或“060-069”，其中單數(shù)為男性分配碼，雙數(shù)為女性分配碼，如遇同年同月同日有兩人以上時順延第二、第三、第四、第五個分配碼.校驗碼(身份證最后一位)是根據(jù)前面十七位數(shù)字碼，按照ISO7064:1983.MOD11-2校驗碼計算出來的.

為方便計，將身份證號記為X18X17X16X15X14X13X12X11X10X9X8X7X6X5X4X3X2X1，則身份證號碼中各個位置上的號碼字符應滿足公式：

(1)

其中i表示包含校驗碼在內的號碼字符從右至左的位置序號；Xi表示第i個位置上的號碼字符值；Wi表示第i個位置上的加權因子，其計算公式為Wi≡2i-1(mod11)，公民身份證號各個位置上的加權因子如表1.

表1　公民身份證號的加權因子

當i=1時，W1=1，公式(1)即為

(2)

表2　校驗碼對應表

例1某個人的身份證復印件，前十七位為21020219801122851，因為雨水濡濕，最后一位數(shù)字，即校驗碼模糊了，那么他的身份證校驗碼是什么呢？

分析由身份證校驗碼的計算規(guī)則，前十七位分別乘以對應的加權因子再相加，得299，此數(shù)字除以11，余2，因此他的身份證最后一位應該是X.

3.2　商品條碼中的同余

以13位代碼為例，商品條碼[8]是由前綴部分、廠商識別代碼、商品項目代碼和校驗碼組成.商品條碼中的前綴碼是用來標識國家或地區(qū)的代碼，賦碼權在國際物品編碼協(xié)會，如690-695代表中國大陸.廠商識別代碼的賦權在各個國家或地區(qū)的物品編碼組織，中國大陸由國家物品編碼中心賦予廠商識別代碼.商品項目代碼是用來標識商品的代碼，賦碼權由產品生產企業(yè)自己行使，生產企業(yè)按照規(guī)定條件自己決定在自己的何種商品上使用哪些阿拉伯數(shù)字為商品條形碼.商品條碼最后用1位校驗碼來校驗商品條形碼中左起第1-12數(shù)字代碼的正確性.因此，中國大陸生產的商品的條碼有四種結構，如表3.

表3　13位代碼結構

通用商品條形碼的校驗碼計算也是按照同余進行的.具體計算是[9]，條形碼的前12位數(shù)字中的偶數(shù)位數(shù)字之和乘以3，再加上奇數(shù)位數(shù)字之和及校驗碼，所得數(shù)字M可以被10整除，即若將通用商品條形碼代碼記為X13X12X11X10X9X8X7X6X5X4X3X2X1，有

M=[3(X12+X10+X8+X6+X4+X2)+(X13+X11+X9+X7+X5+X3)+X1]，

且0≡M(mod10).

例2某商品的通用商品條形碼是6922266445056.試問此商品的通用商品條形碼是否有誤？

分析根據(jù)通用商品條形碼的制訂規(guī)則，前12位數(shù)字中的偶數(shù)位數(shù)字之和乘以3，再加上奇數(shù)位數(shù)字之和及校驗碼，所得數(shù)字為119，此數(shù)模10余9，不滿足與0模10同余，校驗碼錯誤，所以此商品的通用商品條形碼出現(xiàn)錯誤.為糾正錯誤，將最后一位的校驗碼改為7即可.

3.3　書號中的同余

正規(guī)出版的書也有條形碼，條形碼上的數(shù)字一般稱為書號，2007年1月1日之前，書號為10位，2007年1月1日之后，書號為13位.10位的書號是十個數(shù)字組成的長短不一的四部分構成，分別稱為國別語種識別代號、出版社識別代號、書名版別代號和稽核數(shù)碼；13位的書號是在10書號前面添加978或979并重新計算稽核數(shù)碼得到的，它是13個數(shù)字組成的長短不一的五部分構成，分別是978表示此條形碼是圖書的條形碼、國別語種識別代號、出版社識別代號、書名版別代號和稽核數(shù)碼.13位的書號，與通用商品條形碼一樣，也滿足前12位數(shù)字中的偶數(shù)位數(shù)字之和乘以3，再加上奇數(shù)位數(shù)字之和及稽核數(shù)碼，所得數(shù)字可以被10整除，即模10余0.10位的書號則是用10、9、8、7、6、5、4、3、2、1與書號的10位數(shù)字分別相乘，再相加求和，所得數(shù)字可以模11余0，若稽核數(shù)碼的數(shù)字必須為10，則用X表示.

例3某書2007年1月1日前印刷時的書號為ISBN988-97-0101-4，那么該書2007年1月1日后再出版時(未改版)的書號是什么？

分析根據(jù)2007年1月1日前后的書號改變規(guī)則，可知該書2007年1月1日后再次出版時的書號為13位，其中前12位為978-988-97010-1，最后一位稽核數(shù)碼x需要按13位書號的計算方法重新計算，根據(jù)稽核號的制定規(guī)則，應有

0≡(133+x)(mod10)，

因此x=7，即稽核數(shù)碼應該為7，因此該書2007年1月1日后再次出版時的書號應該是ISBN978-988-970101-7.

3.4　全國組織機構代碼中的同余

全國組織機構代碼證制度是我國社會管理的基本制度之一，全國組織機構代碼是對中華人民共和國內依法注冊、依法登記的機關、企、事業(yè)單位、社會團體和民辦非企業(yè)單位頒發(fā)一個在全國范圍內唯一的、始終不變的代碼標識，俗稱單位的“身份證”.

全國組織機構代碼[9]由八位數(shù)字(或大寫英文字母)本體代碼和一位數(shù)字(或大寫英文字母)校驗碼組成.為便于人工識別，應使用一個連字符“—”分隔本體代碼與校驗碼.機讀時，連字符省略.表示形式為：X9X8X7X6X5X4X3X2—X1.本體代碼采用系列(即分區(qū)段)順序編碼方法.

組織機構代碼的校驗碼X1也是利用同余計算的，公式為

(3)

其中i表示包含校驗碼在內的號碼字符從右至左的位置序號；Xi表示第i個位置上的號碼字符值；Wi表示第i個位置上的加權因子，如表4.

表4　組織機構代碼的加權因子

當校驗碼數(shù)值為10時，用X表示.如果組織機構代碼中有英文字母，在計算時，A用10代替，B用11代替，……，Z用35代替.

例4如大連外國語大學的機構代碼是42243701-8，本體代碼為42243701，校驗碼為8，各位數(shù)字分別和對應的系數(shù)相乘，再相加求和，得165，0≡165(mod11).再如，大連外國語大學國際教育培訓中心的機構代碼是E5761940-4，本體代碼為E5761940，校驗碼為4，E對應的數(shù)字為14，各位數(shù)字與對應的系數(shù)相乘，再相加求和，得297，0≡297(mod11).

4結論

無論是《近世代數(shù)》，還是《離散數(shù)學》，在教學過程中，適當?shù)匾胪嘣谏钪械膶嶋H應用，可以改變師生對同余只有理論應用的誤解，增強師生對同余應用的了解，進而在豐富教學內容的同時，增加學生的學習興趣.

[參考文獻]

[1]邢偉.近世代數(shù)[M].北京：科學出版社，2010：25-32.

[2]孟道驥，陳良云，等.抽象代數(shù)——代數(shù)學基礎[M].北京：北京大學出版社，2013：1-7.

[3]耿素云，屈婉玲，張立昂.離散數(shù)學[M].3版.北京: 清華大學出版社，2013：257-264.

[4]左孝凌，李為鑑，劉永才.離散數(shù)學[M].上海: 上?？茖W技術文獻出版社，2011：131.

[5]劉合義.談數(shù)論中的同余及其應用[J].衡水師專學報，2002，4(1)：38-39.

[6]王健敏.同余理論在光通信系統(tǒng)中的一個應用[J].蘇州大學學報(自然科學版)，2011，27(3)：14-16.

[7]馬德起，蘇明躍，臧世陽.深度挖掘身份證隱藏的信息[J].電腦知識與技術(學術交流)，2007(17)：1193-1194.

[8]全國物流信息管理標準化技術委員會.GB12904-2008[S].北京：中國標準出版社，2008.

[9]GB11714-1997.全國組織機構代碼編制規(guī)則[S].技術監(jiān)督實用技術，1998，5(2)：32.

Some Practical Applications of Congruence

CAOHong-ju1，GUOQiao-li2

(1.School of Software， Dalian University of Foreign Languages，Dalian， Liaoning 116044，China;

2.Computer Science and Technology， Dalian Neusoft University Information， Dalian， Liaoning 116023，China)

Abstract:As one of the most important concept form Modern Algebra and Discrete Mathematics， congruence has many applications. However， during the traditional teaching course， the practical applications of congruence are always ignored. In order to enrich the teaching material， the applications of congruence in ID number， the Universal Product Code， National Organization Code and International Standard Book Number are introduced.

Key words:congruence; check digit; application

[中圖分類號]O29

[文獻標識碼]A

[文章編號]1672-1454(2015)04-0105-04