弃九法，数论同余学习笔记
在数论里面有这么一个方法能简单的判断一下两个数相乘以后得到的结果是否是正确的，而这个方法就是弃九法。弃九法归根结底还用了同余的一些基本性质。
那什么是弃九法呢？先从两个数相乘说起吧。比如说 28997*29459 = 11441912613这个结果对吗？由于弃九法用到了很多的同余方面的只是。那么先就说一下有关同余的概念。
什么是同余呢？
同余的概念是这样说的，如果a，b都为整数，m是一个固定的正整数。则当m|(a-b)，即当m 能把（a - b）整除的时候，我们说a，b，对m同余记作a ≡ b(mod m)，其实也可以简单的理解就是a mod m = b mod m,mod表示取余。很快的我们得出b ≡ a(mod m).且还有 ak ≡ bk(mod m).
我们还可以很快的推出
a ≡ b(mod m), b ≡ c(mod m)则就有a ≡ c(mod m)即同余性质具有传递性。
下面只简单的证明一下传递性质。
证明如下： 因为a ≡ b(mod m)，根据定义有 a - b = mt (1),t为一个整数。 因为b ≡ c(mod m)， 根据定义有b - c = ms (2),s为一个整数。 由（1） + （2）得到：a - c = m(s+t) = mk,k为一个整数。 所以：a ≡ c(mod m)。得证。
下面说一下下面的几条重要的性质。
如果a ≡ b (mod m), c≡ d(mod m),则有a+c = b+d(mod m)、a - c ≡ b - d(mod m)和ac ≡ bd(mod m)。
a+c = b+d(mod m)、a - c ≡ b - d(mod m)证明方法类似上面。ac ≡ bd(mod m)证明方法如下。
因为a≡b(mod m),则ac≡ bc(mod m)。
因为c≡d(mod m),则bc ≡ bd(mod m)。
所有 ac - bc = mt,bc - bd = mk,t、k为整数。
两式相加得到ac - bd = m(t + k) = ml,l为整数。
所以ac ≡ bd(mod m).得证。所以由a ≡ b(mod m),和ac ≡ bd(mod m)知道，当a = c，b= d的时候，有a^2 =b^2(mod m),用数学归纳法可以很轻松的证明有：
a^n ≡ b^n(mod m),n为一个非负整数。
另当n = 0时,1 ≡ 1(mod m)很显然成立。因为 10 ≡ 1(mod 9),可以知道10 ^ n ≡1( mod 9),n为一个非负整数，这也就说明10^n - 1能整除9直接能用数学语言证明出来了。而不用很麻烦的叙述了。现在说一下正题弃九法。
因为任意的n和k位的十进制整数a,b都可以表示成权与对应基的幂次方的乘积的形式。
即a = ∑ai10^i，i = 0,1,2,3,4,5...n b = ∑bi10^i ， i = 0,1,2,3,4,5....k 设c = ab = ∑ci10^i,i = 0,1,2,3,...q.
有上面的性质得：
因为10 ^ n ≡1( mod 9) { = 10 ^ n( mod 9)},
所以有ai10^i(mod 9) = ai(mod 9) * 1(mod 9) = ai(mod 9)故：
a≡(an+ an-1+.....a1+a0)(mod 9)。同理b、c都可以写成这种形式。
因为c = ab，所以有：
c=ab ≡ (an+ an-1+.....a1+a0)*(bn+bn-1+.....b1+b0) (mod 9)
≡(cn+cn-1+.....c1+c0)(mod 9)
所以 (cn+ cn-1+.....c1+c0)≡(an+ an-1+.....a1+a0)*(bn+ bn-1+.....b1+b0) (mod 9)。
呵呵： 这样28997*29459 = 11441912613这个结果就可以用上面的法子检查一下了。
因为2+8 + 9+ 9+ 7 = 35，2 + 9 + 4+ 5 + 9 = 29，1+1+4+4+1+9+1+2+6+1+3 = 33
这时只要判断35 * 29 ≡ 33 (mod 9)正确与否可以快速的检查一下是否结果正确。
根据第二种形式只要判断35 * 29 mod 9 = 33 mod 9即可了。
因为35 * 29 mod 9 = (35 mod 9)* (29 mod 9)mod 9 = 8 * 2 mod 9 = 7≠ 33mod 9 = 6。所以结果是算错了。
但是上面 的判断方法只是结果算对的一个必要非充分条件。
例如上面的结果算的实际应为2899729459 = 11441912623，如果算成：2899729459 = 11441912533就可以判断出上面的方法不灵了。检查不出结果是错的。
