同余的几个实际应用

曹宏举，　郭巧丽

(1.大连外国语大学软件学院，辽宁大连116044；　2.大连东软信息学院计算机科学与技术系， 辽宁大连116023)

同余的几个实际应用

曹宏举1，郭巧丽2

(1.大连外国语大学软件学院，辽宁大连116044；2.大连东软信息学院计算机科学与技术系， 辽宁大连116023)

[摘要]同余是《近世代数》和《离散数学》等课程的重要概念之一，具有较广泛的应用，然而传统的教学和教材，大多只介绍理论应用，造成它除了理论之外毫无用处的错觉.本文通过身份证号码、通用商品条形码、组织机构代码和书号四方面切入，介绍同余关系在我们生活中的实际应用，丰富教学内容，增强趣味性.

[关键词]同余； 校验码； 应用

1引言

无论是数学专业的《近世代数》(或《抽象代数》)[1，2]，还是计算机相关专业的《离散数学》等课程[3，4]，同余无疑是重要概念之一，在相关知识中具有广泛应用.然而传统的教材，往往在给出概念之后，就讲解其他相关的理论知识，缺少应用背景，以至于学生在学习时感觉同余就是为了其他相关知识的介绍才引入的，甚至部分教师在教学中也有类似的感觉.虽然有论文探讨同余理论的应用，但要么依然是进行一些枯燥的计算[5]，要么专业性过强[6]，不适合课堂授课时引用.同余的应用，除了我们熟知的在密码学中的应用之外[3]，还具有广泛的应用，如身份证号码编码规则、商品条形码、书号等.通过本文对这些应用的介绍，可以丰富教学内容，扩展教师和学生对有关知识的了解，加深对有关知识的理解.

2定义

定义1[3]设m为正整数，a和b为整数，如果n|a—b，则称a模m同余于b，或称a与b模m同余，记为a≡b(modm).

3实例

3.1　居民身份证号中的同余

居民身份证号码，是指用来证明居民身份的证件的编码.中华人民共和国居民身份证的号码是按照国家的标准编制的，由18位组成，每个人的居民身份证号码都是唯一的.

居民身份证号码编码是根据《中华人民共和国国家标准GB11643-1999》[7]中有关公民身份号码的规定编码的，公民身份号码是特征组合码，由十七位数字本体码和一位数字校验码组成.地址码(身份证前六位)表示编码对象第一次申领居民身份证时的常住户口所在县(市、旗、区)的行政区划代码.生日期码(身份证第七位到第十四位)表示编码对象出生的年、月、日，其中年份用四位数字表示，年、月、日之间不用分隔符.顺序码(身份证第十五位到十七位)是县、区级政府所辖派出所的分配码，每个派出所分配码为10个连续号码，例如“000-009”或“060-069”，其中单数为男性分配码，双数为女性分配码，如遇同年同月同日有两人以上时顺延第二、第三、第四、第五个分配码.校验码(身份证最后一位)是根据前面十七位数字码，按照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，因为雨水濡湿，最后一位数字，即校验码模糊了，那么他的身份证校验码是什么呢？

分析由身份证校验码的计算规则，前十七位分别乘以对应的加权因子再相加，得299，此数字除以11，余2，因此他的身份证最后一位应该是X.

3.2　商品条码中的同余

以13位代码为例，商品条码[8]是由前缀部分、厂商识别代码、商品项目代码和校验码组成.商品条码中的前缀码是用来标识国家或地区的代码，赋码权在国际物品编码协会，如690-695代表中国大陆.厂商识别代码的赋权在各个国家或地区的物品编码组织，中国大陆由国家物品编码中心赋予厂商识别代码.商品项目代码是用来标识商品的代码，赋码权由产品生产企业自己行使，生产企业按照规定条件自己决定在自己的何种商品上使用哪些阿拉伯数字为商品条形码.商品条码最后用1位校验码来校验商品条形码中左起第1-12数字代码的正确性.因此，中国大陆生产的商品的条码有四种结构，如表3.

表3　13位代码结构

通用商品条形码的校验码计算也是按照同余进行的.具体计算是[9]，条形码的前12位数字中的偶数位数字之和乘以3，再加上奇数位数字之和及校验码，所得数字M可以被10整除，即若将通用商品条形码代码记为X13X12X11X10X9X8X7X6X5X4X3X2X1，有

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

且0≡M(mod10).

例2某商品的通用商品条形码是6922266445056.试问此商品的通用商品条形码是否有误？

分析根据通用商品条形码的制订规则，前12位数字中的偶数位数字之和乘以3，再加上奇数位数字之和及校验码，所得数字为119，此数模10余9，不满足与0模10同余，校验码错误，所以此商品的通用商品条形码出现错误.为纠正错误，将最后一位的校验码改为7即可.

3.3　书号中的同余

正规出版的书也有条形码，条形码上的数字一般称为书号，2007年1月1日之前，书号为10位，2007年1月1日之后，书号为13位.10位的书号是十个数字组成的长短不一的四部分构成，分别称为国别语种识别代号、出版社识别代号、书名版别代号和稽核数码；13位的书号是在10书号前面添加978或979并重新计算稽核数码得到的，它是13个数字组成的长短不一的五部分构成，分别是978表示此条形码是图书的条形码、国别语种识别代号、出版社识别代号、书名版别代号和稽核数码.13位的书号，与通用商品条形码一样，也满足前12位数字中的偶数位数字之和乘以3，再加上奇数位数字之和及稽核数码，所得数字可以被10整除，即模10余0.10位的书号则是用10、9、8、7、6、5、4、3、2、1与书号的10位数字分别相乘，再相加求和，所得数字可以模11余0，若稽核数码的数字必须为10，则用X表示.

例3某书2007年1月1日前印刷时的书号为ISBN988-97-0101-4，那么该书2007年1月1日后再出版时(未改版)的书号是什么？

分析根据2007年1月1日前后的书号改变规则，可知该书2007年1月1日后再次出版时的书号为13位，其中前12位为978-988-97010-1，最后一位稽核数码x需要按13位书号的计算方法重新计算，根据稽核号的制定规则，应有

0≡(133+x)(mod10)，

因此x=7，即稽核数码应该为7，因此该书2007年1月1日后再次出版时的书号应该是ISBN978-988-970101-7.

3.4　全国组织机构代码中的同余

全国组织机构代码证制度是我国社会管理的基本制度之一，全国组织机构代码是对中华人民共和国内依法注册、依法登记的机关、企、事业单位、社会团体和民办非企业单位颁发一个在全国范围内唯一的、始终不变的代码标识，俗称单位的“身份证”.

全国组织机构代码[9]由八位数字(或大写英文字母)本体代码和一位数字(或大写英文字母)校验码组成.为便于人工识别，应使用一个连字符“—”分隔本体代码与校验码.机读时，连字符省略.表示形式为：X9X8X7X6X5X4X3X2—X1.本体代码采用系列(即分区段)顺序编码方法.

组织机构代码的校验码X1也是利用同余计算的，公式为

(3)

其中i表示包含校验码在内的号码字符从右至左的位置序号；Xi表示第i个位置上的号码字符值；Wi表示第i个位置上的加权因子，如表4.

表4　组织机构代码的加权因子

当校验码数值为10时，用X表示.如果组织机构代码中有英文字母，在计算时，A用10代替，B用11代替，……，Z用35代替.

例4如大连外国语大学的机构代码是42243701-8，本体代码为42243701，校验码为8，各位数字分别和对应的系数相乘，再相加求和，得165，0≡165(mod11).再如，大连外国语大学国际教育培训中心的机构代码是E5761940-4，本体代码为E5761940，校验码为4，E对应的数字为14，各位数字与对应的系数相乘，再相加求和，得297，0≡297(mod11).

4结论

无论是《近世代数》，还是《离散数学》，在教学过程中，适当地引入同余在生活中的实际应用，可以改变师生对同余只有理论应用的误解，增强师生对同余应用的了解，进而在丰富教学内容的同时，增加学生的学习兴趣.

[参考文献]

[1]邢伟.近世代数[M].北京：科学出版社，2010：25-32.

[2]孟道骥，陈良云，等.抽象代数——代数学基础[M].北京：北京大学出版社，2013：1-7.

[3]耿素云，屈婉玲，张立昂.离散数学[M].3版.北京: 清华大学出版社，2013：257-264.

[4]左孝凌，李为鑑，刘永才.离散数学[M].上海: 上海科学技术文献出版社，2011：131.

[5]刘合义.谈数论中的同余及其应用[J].衡水师专学报，2002，4(1)：38-39.

[6]王健敏.同余理论在光通信系统中的一个应用[J].苏州大学学报(自然科学版)，2011，27(3)：14-16.

[7]马德起，苏明跃，臧世阳.深度挖掘身份证隐藏的信息[J].电脑知识与技术(学术交流)，2007(17)：1193-1194.

[8]全国物流信息管理标准化技术委员会.GB12904-2008[S].北京：中国标准出版社，2008.

[9]GB11714-1997.全国组织机构代码编制规则[S].技术监督实用技术，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