早在一千多年前,数学家们便基于印度-阿拉伯记数法发明了相应的加、减、乘、除、比例、开方等计算方法,与此同时还给出了相应的检验方法——弃九法。
公元952年左右,阿拉伯数学家乌格里迪西完成了《印度算术书》一书,这是现存最早的阿拉伯文算术文献,其中论述了阿拉伯数字的加倍、减半、加法、减法、乘法、除法、开方和弃九法等内容,其中弃九法的主要作用是对各种数字之间的算术运算进行检验。
在了解弃九法之前,我们首先要了解 弃九数 。
将任一整数的每一位数字相加,如此重复,直到结果成为个位数(如果相加结果是9,则将其舍去使得最终结果为0),这就是原数的弃九数。例如数字3217,3+2+1+7=13,继续运算1+3=4,此时数字4就是原数3 217的弃九数。这一系列操作的目的是求出每一个数除以9后的余数。
弃九法可以检验算术运算的结果,验算方法为:用式中所有数字的弃九数在运算中代替各自原数的位置,检验该算式是否依旧成立。若成立,则说明计算可能是对的;若不成立,则结果一定是错的。下面以《印度算术书》中的加法检验为例。
检验86 767+7 485=94 252是否正确:
①计算86 767的弃九数是7;
②计算7 485的弃九数是6;
③7+6=13,13的弃九数是4;
④计算原运算结果94 252的弃九数,也是4;
二者相等说明原运算可能正确。
随后乌格里迪西还讲述了用弃九法检验其他运算正确性的算法过程。
弃九法的检验过程十分简便,但这种方法是否真的有效呢?乌格里迪西在《印度算术书》中对其进行了证明,同时也指出了它的不足。弃九法的验算方法并不“完美”,它只能用来判定计算结果是错误的,不能肯定结果是正确的。例如137+975=1112,用弃九法检验得到2+3=5可以判断加法运算可能是正确的;但如果你计算得到137+975=1 121,此时运算结果是错误的,但是弃九法无法检验出错误。事实上,只要按照加、减、乘、除的四则运算法则进行运算,可能出现的错误往往跟进位、借位等有关,这些错误比较容易通过弃九法检验出来。如果不是为了刻意举出反例,在实际计算中,将137+975错算为1 121的可能性非常小!
在《印度算术书》之后的阿拉伯算术书中也大都记载了弃九法,该算法在传播演化过程中不仅可以用来检验整数运算,还可以检验分数、六十进制数的运算,此外还衍生出弃七法、弃十一法、弃十三法、弃十七法等检验算法。上述阿拉伯算法在13世纪初由意大利数学家斐波那契传入欧洲并广为流传。
15世纪初,阿尔·卡西在计算圆周率的过程中利用弃五十九法检验
在西学东渐的背景下,该算法被传教士传入中国。16世纪末,天主教耶稣会传教士利玛窦(Matteo Ricci,1552—1610)来到中国,李之藻(1565—1630)跟他学习西方数学。二人起初准备合译利玛窦的老师——德国天文学家、数学家克拉维乌斯(Christopher Clavius,1538—1612)所著《实用算术概要》(1583),但利玛窦不幸病逝,翻译未能完成。后来,李之藻将未完成的译本单独改编,于1613年以《同文算指》之名出版,这在中国数学发展史上被认为是西方数学传入中国的开始。其中《同文算指》中介绍的弃九法、弃七法,就源自克拉维乌斯所著的《实用算术概要》。该算法在清代的中文算书中比较常见。
总之,弃九法虽不完美,但它在人类上千年的文明发展过程中始终是一种简单便捷且行之有效的检验方法。
《同文算指》(右)转引《实用算术概要》(左)对加法使用弃九法检验图示
弃九法属于今天初等数论中的 同余理论 ,其中9是同余运算中的模数。今天,模数为10、11等的同余运算常被用于编码学中的校验码检验。
一般来说,一个含有校验码的编号,主体为源号码,源号码通过一系列的运算会得到一个校验码,将这个校验码接在源号码的末尾便组成一个含有校验码的新号码。如果源号码中某一位数字发生变化,按照相应的算法,末尾的校验码也会马上发生变化。校验码的这种自我纠错功能,可以说是利用一种简便的方法对源号码的正确性进行检验以避免出现更大的错误。我们日常在电脑或手机中输入身份证号码时,可能会出现某一位输入错误,或两位数字颠倒等情况,校验码都能起到非常有效的检验作用。
我国公民身份证号码前17位均有具体含义,第18位校验码的计算分三步:
①将前17位数字分别乘下列加权因子——7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2,然后将17个乘积相加;
②将上面的结果除以11,求出余数;
③余数的11种可能为——0,1,2,3,4,5,6,7,8,9,10,对应的校验码分别是1,0,X,9,8,7,6,5,4,3,2(其中X为罗马数字10)。
校验码在我们的生活中无处不在,除了日常生活中使用的身份证号码,图书的国际标准书号(International Standard Book Number,ISBN)也是校验码的典型应用。它的算法比身份证校验码更加简单直观。
2007年之前出版的图书,ISBN码大多是一个十位数,它的前几位数字表示该书的国别、出版社和书名,最后一位为校验码,通常采用
a
-
bcd
-
efghi
-
j
的形式,其中校验码
j
需要满足运算关系:令
s
=10
a
+9
b
+8
c
+7
d
+6
e
+5
f
+4
g
+3
h
+2
i
。
r
是
s
除以11所得的余数,若
r
不等于0或1,则规定
j
=11-
r
(若
r
=0,则规定
j
=0;若
r
=1,则规定
j
用
X
表示)。
若某书ISBN码的前九位源号码为730904547,现在按照上面的算法计算它的校验码。
①首先将源号码730904547加权相乘求和:
7×10+3×9+0×8+9×7+0×6+4×5+5×4+4×3+7×2=226
②因为226÷11=20……6,即 r =6。j=11-r=11-6=5,所以校验码为5,进而得到该书的ISBN码为7309045475。
若某人在电脑系统中输入该ISBN码时粗心将第一位7输成了8,则上述加权相乘求和得到236,此时得到的校验码6与原校验码5不同。即,若输入ISBN码为8309045475,系统就会立刻发现输入错误,这样就起到校验的作用了。
总之,我们日常生活中常用的条形码、信用卡卡号等都采用了校验码校验,而其中蕴含的用同余算法进行校验的数学思想已经有上千年的历史了。
1.用弃九法检验乘法运算:18467×2 678=49 454 626。
2.用弃九法检验除法运算:14443 572÷247=58476。