曹宏舉，　郭巧麗

(1.大連外國(guó)語(yǔ)大學(xué)軟件學(xué)院，遼寧大連116044；　2.大連東軟信息學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系， 遼寧大連116023)

同余的幾個(gè)實(shí)際應(yīng)用

曹宏舉1，郭巧麗2

(1.大連外國(guó)語(yǔ)大學(xué)軟件學(xué)院，遼寧大連116044；2.大連東軟信息學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系， 遼寧大連116023)

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

[關(guān)鍵詞]同余； 校驗(yàn)碼； 應(yīng)用

1引言

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

2定義

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

3實(shí)例

3.1　居民身份證號(hào)中的同余

居民身份證號(hào)碼，是指用來(lái)證明居民身份的證件的編碼.中華人民共和國(guó)居民身份證的號(hào)碼是按照國(guó)家的標(biāo)準(zhǔn)編制的，由18位組成，每個(gè)人的居民身份證號(hào)碼都是唯一的.

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

為方便計(jì)，將身份證號(hào)記為X18X17X16X15X14X13X12X11X10X9X8X7X6X5X4X3X2X1，則身份證號(hào)碼中各個(gè)位置上的號(hào)碼字符應(yīng)滿足公式：

(1)

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

表1　公民身份證號(hào)的加權(quán)因子

當(dāng)i=1時(shí)，W1=1，公式(1)即為

(2)

表2　校驗(yàn)碼對(duì)應(yīng)表

例1某個(gè)人的身份證復(fù)印件，前十七位為21020219801122851，因?yàn)橛晁?，最后一位?shù)字，即校驗(yàn)碼模糊了，那么他的身份證校驗(yàn)碼是什么呢？

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

3.2　商品條碼中的同余

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

表3　13位代碼結(jié)構(gòu)

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

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

且0≡M(mod10).

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

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

3.3　書號(hào)中的同余

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

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

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

0≡(133+x)(mod10)，

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

3.4　全國(guó)組織機(jī)構(gòu)代碼中的同余

全國(guó)組織機(jī)構(gòu)代碼證制度是我國(guó)社會(huì)管理的基本制度之一，全國(guó)組織機(jī)構(gòu)代碼是對(duì)中華人民共和國(guó)內(nèi)依法注冊(cè)、依法登記的機(jī)關(guān)、企、事業(yè)單位、社會(huì)團(tuán)體和民辦非企業(yè)單位頒發(fā)一個(gè)在全國(guó)范圍內(nèi)唯一的、始終不變的代碼標(biāo)識(shí)，俗稱單位的“身份證”.

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

組織機(jī)構(gòu)代碼的校驗(yàn)碼X1也是利用同余計(jì)算的，公式為

(3)

其中i表示包含校驗(yàn)碼在內(nèi)的號(hào)碼字符從右至左的位置序號(hào)；Xi表示第i個(gè)位置上的號(hào)碼字符值；Wi表示第i個(gè)位置上的加權(quán)因子，如表4.

表4　組織機(jī)構(gòu)代碼的加權(quán)因子

當(dāng)校驗(yàn)碼數(shù)值為10時(shí)，用X表示.如果組織機(jī)構(gòu)代碼中有英文字母，在計(jì)算時(shí)，A用10代替，B用11代替，……，Z用35代替.

例4如大連外國(guó)語(yǔ)大學(xué)的機(jī)構(gòu)代碼是42243701-8，本體代碼為42243701，校驗(yàn)碼為8，各位數(shù)字分別和對(duì)應(yīng)的系數(shù)相乘，再相加求和，得165，0≡165(mod11).再如，大連外國(guó)語(yǔ)大學(xué)國(guó)際教育培訓(xùn)中心的機(jī)構(gòu)代碼是E5761940-4，本體代碼為E5761940，校驗(yàn)碼為4，E對(duì)應(yīng)的數(shù)字為14，各位數(shù)字與對(duì)應(yīng)的系數(shù)相乘，再相加求和，得297，0≡297(mod11).

4結(jié)論

無(wú)論是《近世代數(shù)》，還是《離散數(shù)學(xué)》，在教學(xué)過(guò)程中，適當(dāng)?shù)匾胪嘣谏钪械膶?shí)際應(yīng)用，可以改變師生對(duì)同余只有理論應(yīng)用的誤解，增強(qiáng)師生對(duì)同余應(yīng)用的了解，進(jìn)而在豐富教學(xué)內(nèi)容的同時(shí)，增加學(xué)生的學(xué)習(xí)興趣.

[參考文獻(xiàn)]

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

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

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

[4]左孝凌，李為鑑，劉永才.離散數(shù)學(xué)[M].上海: 上海科學(xué)技術(shù)文獻(xiàn)出版社，2011：131.

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

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

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

[8]全國(guó)物流信息管理標(biāo)準(zhǔn)化技術(shù)委員會(huì).GB12904-2008[S].北京：中國(guó)標(biāo)準(zhǔn)出版社，2008.

[9]GB11714-1997.全國(guó)組織機(jī)構(gòu)代碼編制規(guī)則[S].技術(shù)監(jiān)督實(shí)用技術(shù)，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

[中圖分類號(hào)]O29

[文獻(xiàn)標(biāo)識(shí)碼]A

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