数论与有限域-第七章.pptVIP

第七章 数论与有限域的应用 第一节 同余式的简单应用 一、正整数能否被除尽 二、弃九法 三、计算星期几 四、循环比赛 一、正整数能否被除尽 定理7.1.1 设正整数m的十进制表示为(m)10=(an,an-1,...,a1,a0)10，则仅当an+an-1+ ...+a0能被3除尽时，m才能被3除尽。 证明：这是由于m=an×10n+an-1×10n-1+ ...+a0，而 10≡1(mod3)，100≡1(mod3)，…，10n≡1(mod3)， 所以 m≡an+an-1+ ...+a0 (mod 3)， 故若an+an-1+ ...+a0能被3除尽，即 an+an-1+ ...+a0≡0(mod 3)，则 m≡0(mod 3)，即m能被3除尽。 若an+an-1+ ...+a0不能被3除尽，则m不能被3除尽。 一、正整数能否被除尽 定理7.1.2 正整数m的千进制表示为(m)1000=(an,an-1,...,a1,a0)1000，即 m=an×1000n +an-1×1000 n-1 + ... +a1×1000+a0， 其中0≤ai1000， 则m被7（或11或13）除尽的充要条件是(a0+a2+a4+...)-(a1+a3+a5+...)能被7（或11或13）除尽。 证明：由于10002被7除余1，1000被7除余-1，则易知一般地有1000 2k被7除皆余1，1000 2k+1被7除皆余-1，所以 m≡(a0+a2+a4+...)-(a1+a3+a5+...)(mod 7)， 即仅当(a0+a2+a4+...)-(a1+a3+a5+...)被7除尽时，m才能被7除尽。 一、正整数能否被除尽 例如由于123456789的数字和为 1+2+3+4+5+6+7+8+9=45， 所以123456789可以被3除尽。 又例如 123456=123×1000+456， 而 456-123=333不能被7（或11或13）除尽，所以123456也不能被7（或11或13）除尽。 二、弃九法 弃九法是一种验算正整数的计算结果正确与否的方法，在发明计算机之前，会计人员常常用弃九法来检查很大数目的和、差、积和商。 例如：假若用正整数a减b得到c，这个结果可以作下面验算： 首先，将a，b及c的各位数字相加各自得到一个和， 再把各个和的各位数字相加又得到三个新的和， 再继续作数字和， 直到最后的数字和是个位数为止， 这最后的得到的三个个位数称为a，b及c的“数字根”； 随后，把a的数字根减去b的数字根，看看差是否等于c的数字根， 如果数字根的差不等，则会计员就知道他算错了。 这种检验方法可同样应用于数字的加、乘和除上。 二、弃九法 下面具体介绍上述弃九法的原理。假设已经使用普通的乘法运算求出了正整数a与b的乘积c，并令a，b及c的十进制表示如下 a=an×10n + an-1×10 n-1 + ...+ a0，其中0≤ai10 b=bm×10m +bm-1×10 m-1 +...+ b0，其中0≤bj10 c=cl×10l +cl-1×10 l-1 +...+ c0，其中0≤ck10 则显然有 a≡an+an-1+ ...+a0 (mod 9) b≡bm+bm-1+...+b0 (mod 9) c≡cl+cl-1+...+c0 (mod 9) 二、弃九法 而ab=c，故ab≡c(mod 9)，进而由上述三式得到 (an+ an-1 + ...+ a0)(bm+bm-1 +...+ b0) ≡cl+cl-1 +...+ c0 (mod 9) 如此：若(an+ an-1 + ...+ a0)(bm+bm-1 +...+ b0)?cl+cl-1 +...+ c0 (mod 9)，则所求得的乘积是错误的。 在实际验算时，由于9≡0(mod 9)，因而若an, an-1, …, a0, bm, bm-1, …, b0, cl, cl-1, …, c0中有9出现，还可以把9去掉， 因而求一个数的数字根最快的方法是在加原数的数字时把9舍去， 例如，最初两个数字是6和8，二者相加成14，再将1加4，结果是5。 二、弃九法 例7.1.1 a=1234，b=5678，问ab否正确？ 解：由于 1+2+3+4=10；5+6+7+8=26 1+2+3+4+5+6+7+8=36；10×26=260 而260?36 (mod 9)，所以ab正确。 例7.1.2 求证28997×39459≠1144192613。 证明：由于 28997≡2+8+7≡8 (mod 9)，39459≡3+4+5≡3 (mod 9) 1144192613≡1+1+4+4+1+2+6+1+3