同余的性质毕业论文

100除以7的余数是2，意思就是说把100个东西七个七个分成一组的话最后还剩2个。余数有一个严格的定义：假如被除数是a，除数是b（假设它们均为正整数），那么我们总能够找到一个小于b的自然数r和一个整数m，使得a=bm+r。这个r就是a除以b的余数，m被称作商。我们经常用mod来表示取余，a除以b余r就写成a mod b = r。 如果两个数a和b之差能被m整除，那么我们就说a和b对模数m同余（关于m同余）。比如，100-60除以8正好除尽，我们就说100和60对于模数8同余。它的另一层含义就是说，100和60除以8的余数相同。a和b对m同余，我们记作a≡b(mod m)。比如，刚才的例子可以写成100≡60(mod 8)。你会发现这种记号到处都在用，比如和数论相关的书中就经常把a mod 3 = 1写作a≡1(mod 3)。 之所以把同余当作一种运算，是因为同余满足运算的诸多性质。比如，同余满足等价关系。具体地说，它满足自反性（一个数永远和自己同余）、对称性（a和b同余，b和a也就同余）和传递性（a和b同余，b和c同余可以推出a和c同余）。这三个性质都是显然的。 同余运算里还有稍微复杂一些的性质。比如，同余运算和整数加减法一样满足“等量加等量，其和不变”。小学我们就知道，等式两边可以同时加上一个相等的数。例如，a=b可以推出a+100=b+100。这样的性质在同余运算中也有：对于同一个模数m，如果a和b同余，x和y同余，那么a+x和b+y也同余。在我看来，这个结论几乎是显然的。当然，我们也可以严格证明这个定理。这个定理对减法同样有效。 性质：如果a≡b(mod m)，x≡y(mod m)，则a+x≡b+y(mod m)。 证明：条件告诉我们，可以找到p和q使得a-mp = b-mq，也存在r和s使得x-mr = y-ms。于是a-mp + x-mr = b-mq + y-ms，即a+x-m(p+r) = b+y-m(q+s)，这就告诉我们a+x和b+y除以m的余数相同。 容易想到，两个同余式对应相乘，同余式两边仍然相等： 如果a≡b(mod m)，x≡y(mod m)，则ax≡by(mod m)。 证明：条件告诉我们，a-mp = b-mq，x-mr = y-ms。于是(a-mp)(x-mr) = (b-mq)(y-ms)，等式两边分别展开后必然是ax-m(…) = by-m(…)的形式，这就说明ax≡by(mod m)。 现在你知道为什么有的题要叫你“输出答案mod xxxxx的结果”了吧，那是为了避免高精度运算，因为这里的结论告诉我们在运算过程中边算边mod和算完后再mod的结果一样。假如a是一个很大的数，令b=a mod m，那么(a * 100) mod m和(b * 100) mod m的结果是完全一样的，这相当于是在a≡b (mod m)的两边同时乘以100。这些结论其实都很显然，因为同余运算只关心余数（不关心“整的部分”），完全可以每一次运算后都只保留余数。因此，整个运算过程中参与运算的数都不超过m，避免了高精度的出现。 在证明Fermat小定理时，我们用到了这样一个定理： 如果ac≡bc(mod m)，且c和m互质，则a≡b(mod m) （就是说同余式两边可以同时除以一个和模数互质的数）。 证明：条件告诉我们，ac-mp = bc-mq，移项可得ac-bc = mp-mq，也就是说(a-b)c = m(p-q)。这表明，(a-b)c里需要含有因子m，但c和m互质，因此只有可能是a-b被m整除，也即a≡b(mod m)。

同余这个概念最初是由德国伟大的数学家高斯发现的，有这样的几个定理:对于两个整数A和B，如果他们除以同一个自然数M的余数相同，就说A、B对于模M同余。比如说:12除以5，47除以5，他们有相同的余数2，这时我们就说对于除数5，12和47同余。记作12≡47(mod5)同余的性质主要有:(1)对于同一个除数，两数的和(或差)于他们余数的和(或差)同余数。(2)对于同一个除数，两数的乘积与他们余数的乘积同余。(3)对于同一个除数，如果两个整数同余，那么他们的差就一定能被这个数整除。(4)对于同一个除数，如果两个整数同余，那么他们的乘方仍然同余。解答同余类型题目的关键是灵活运用性质，把求一个比较大的数字除以某数的余数问题转化为求一个较小数除以这个数的余数，使复杂的问题变得简单化。例1:求1992×59除以7的余数。根据性质2，不用计算两个数的乘积，可以转化位分别求出1992÷7和59÷7的余数的积，使计算简单化。第一个余数是4，第二个余数是3.余数的乘积是12，除以7后的余数是5，所以1992×59除以7的余数是5.简单记做因为1992×59≡4×3≡5(mod7),所以余数是5.例2:求2001的2003次方除以13的余数。根据性质4来解决。2001除以13的余数等于12，12除以13的余数也是12，可以说2001的2003次方与12的2003次方对于除数13同余。但是12的2003次方仍然是一个很大的数字，求余数仍然比较困难。这时的关键找出12的几次方对于13与1同余，经过试验知道12的平方≡1(mod13),而2003=2的1001次方+1，所以12平方的1001次方≡1的1001(mod13).根据同余的性质12的2002次方×12≡1×12=12(mod13),所以余数等于12。例3:自然数16520、14903、14177除以m得到相同的余数，m最大的数值等于多少?三个数字比较大，但是他们对于m同余，那么当中任意两个数字的差必然是m倍数，要求m的最大的数值可以转化位求他们的三个差的最大公约数，从而降低计算的难度。16520-14903=1617=3×7的平方×11，16520-14177=2343=3×11×71，14903-14177=726=2×3×11的平方，三个差的最大公约数是3×11=33,m的最大数字等于33.练习:1)879×4376×5283除以19的余数。2)已知2001年的国庆节是星期一，求2008年的国庆节是星期几?3)求16的200次方除以21的余数?4)一个整数除226、192、141都得到相同的余数，并且余数不等于0，这个整数最大是多少?

1 反身性 a≡a (mod m)2 对称性 若a≡b(mod m)，则b≡a (mod m)3 传递性 若a≡b (mod m)，b≡c (mod m)，则a≡c (mod m)4 同余式相加 若a≡b (mod m)，c≡d(mod m)，则a+-c≡b+-d (mod m)5 同余式相乘 若a≡b (mod m)，c≡d(mod m)，则ac≡bd (mod m)【证明】上述性质很容易证明,下面仅证明(3).∵a≡b(mod m)∴m|(a-b) 同理m|(b-c),∴m|[(a-b)+(b-c)]∴m|(a-c).故a≡c(mod m).4 线性运算如果a ≡ b (mod m)，c ≡ d (mod m),那么(1)a ± c ≡ b ± d (mod m)，(2)a * c ≡ b * d (mod m)【证明】(1)∵a≡b(mod m),∴m|(a-b) 同理 m|(c-d)∴m|[(a-b)±(c-d)]∴m|[(a±c)-(b±d)]∴a ± c ≡ b ± d (mod m)(2)∵ac-bd=ac-bc+bc-bd=c(a-b)+b(c-d)又 m|(a-b) , m|(c-d)∴m|(ac-bd)∴a * c ≡ b * d (mod m) 5 除法若ac ≡ bc (mod m) c≠0 则 a≡ b (mod m/gcd(c,m)) 其中gcd(c,m)表示c,m的最大公约数特殊地 ,gcd(c,m)=1 则a ≡ b (mod m)6 幂运算如果a ≡ b (mod m)，那么a^n ≡ b^n (mod m)7 若a ≡ b (mod m)，n|m,则 a ≡ b (mod n)8 若a ≡ b (mod mi) (i=1,2...n) 则 a ≡ b (mod [m1,m2,...mn]) 其中[m1,m2,...mn]表示m1,m2,...mn的最小公倍数9 欧拉定理设a,m∈N,(a,m)=1,则a^(φ(m))≡1(mod m)(注:φ(m)指模m的简系个数， φ(m)=m-1, 如果m是素数；φ(m=q1^r1 * q2^r2 * ...*qi^ri)=m (1-1/q1)(1-1/q2)...(1-1/qi))推论: 费马小定理: 若p为质数，则a^p ≡ a (mod p) 即a^(p-1) ≡ 1 (mod p)（但是当p|a时不等价）10 中国剩余定理设整数m1,m2,m3,......,mn 两两互素，令m=m1m2m3m4m5...mn（mi的连乘）。则对于任意的J在（1,n)整数，下列联立的同余式有解：{xj≡1(mod mj){xj≡0(mod mi) i不等于j令x为从1到najxj的和，则x适合下列联立同余式x≡aj（mod mj）, j=1,2,3,.....,n另：求自然数a的个位数字，就是求a与哪一个一位数对于模10同余