毕业论文同余方程的解法

我写个简例吧：AAA解法：解同余式组:x≡1(mod5) x≡2(mod11)解：中国剩余定理的等效解法令x=5a+11b +55t 亦即 x==5a+11b mod 5*11代入原同余式组得11b==1 mod 55a==2 mod 11解得b==1 mod 5, a=-4==7 mod 11取任意一组特解如b=1,a=7代入得x==5*7+11*1=46 mod 55 BBB解的数量之判定法：对于多个模并非两两互质的情况，可以先确立一组两两互质的分解基数集（质数集是一个常用的特例），将这些模用分解基数表示成为多个因数项，将其中相关于同一个分解基数的项进行归并。如果有矛盾，则无解。否则有解。例：同余式组x=2 mod 16x=3 mod 5x=6 mod 12取4, 3, 5作为分解基。变成x=2 mod 4^2x=3 mod 5x=6 mod 4x=6 mod 3其中相关于同一个分解基数的情况，仅有x=2 mod 16与x=6 mod 4是相关于分解基数"4"的,它们没有矛盾。取两相容解集的交集，即其中解集较小的那个：x=2 mod 16.再与x=3 mod 5及x=6==0 mod 3联立求解。另例：x=2 mod 18x=8 mod 12以3,2为分解基。相关于分解基数3的转化式有x=2 mod 3^2, x=2 mod 3, 取前者。相关于分解基数2的转化式有x=0 mod 2, x=0 mod 4, 取后者。 另例：同余式组x=3 mod 12x=2 mod 18以2,3为分解基集，于是原同余式组变成x==3 mod 2^2x==3 mod 3x==2 mod 3^2x==2 mod 2矛盾。故此同余式无解。如果是形如ax=b mod m形状的同余式联立的，则可能出现无解、一解、多解的情况。一个基本的例子如下：12x=18 mod 27 注：相当于12x=9+18k自然就等价于同余式4x=3 mod 9解得x=3 mod 9, 转化为模27的同余式，为x=3,12,21 mod 27 AAAAAA快速计算法例如同余式组(以下用==表示同余号)x==2 mod 5-2 mod 6-3 mod 7对中国剩余定理一个简单的改进可以是这样：令x=5*6*7*(a/5+b/6+c/7) mod 5*6*7即x=6*7*a+5*7*b+5*6* c+ 5*6*7 t代入原题即得6*7*a==2 mod 55*7*b==-2 mod 65*6*c==-3 mod 7求得a==1 mod 3, 或者说是形如-1+3u的任意整数。b=2 mod 5, ...c=2 mod 7剩下的就是如果计算出x来了。下面也给了简化方法。从下面这个式子上看x=5*6*7*(a/5+b/6+c/7) mod 5*6*7=5*6*7*(a/5+b/6+c/7 mod 1) 注意，这个式子极具有启发性！我们看到，我们需要的x的值，只要取以5*6*7作分母时的分数(a/5+b/6+c/7) 的分子就行了，如果我们将 a/5+b/6+c/7表示成带分数，即整数加真分数的形式。还可以发现，如果要取最小正整数解，就取这个真分数的分子就形子。。在计算过程中，任意加减一个整数，造成数的增大和变小，并不影响我们的结果。同时，任意交换加项，也不影响。下面我们来计算：1/5+2/6+2/7 mod 1=16/30+2/7=172/210 再例：这是我刚答的一道题，讲的较为明确精炼，请参考。一个数÷5余1，÷7余3，÷9余2，这个数最小是几？题目转化为同余式组x==1 mod 5x==3 mod 7x==2 mod 9解：令x==7*9*a+5*9*b+5*7*c mod 5*7*9即x=7*9*a+5*9*b+5*7*c+5*7*9*t即x==5*7*9*(a/5+b/7+c/9 mod 1)即x=5*7*9*(a/5+b/7+c/9+t)代入原同余式组得7*9*a==1 mod 5 , 于是a==2 mod 5, 取其特值2为代表。5*9*b ==3 mod 7，于是b==1 mod 7,取其特值1为代表。5*7*c==2 mod 9,于是c==-2 mod 9,取其特值-2为代表。再以x==5*7*9*(a/5+b/7+c/9 mod 1)为求值式，进行计算。先计算（a/5+b/7+c/9 mod 1)注意，计算过程中，任一个加项或整体值上可以加减任一个整数，不影响。同时，在计算时，可以充分运用加法的交换律与结合律，随意调整加法项的位置与加法过程的顺序。其中，mod 1这个提法一定要理解，这样可以为解同余式组带来极大的方便。mod 1表示两个对象相差一个整数值。如果mod用来表示求余，则表示求一个数的小数部分；如果N==0 mod 1，即说明N为整数。2/5+1/7-2/9 mod 1 ==2/5-2/9+1/7==8/45+1/7==101/45*7==101/315于是x==101 mod 315这个数最小为 101