本科毕业论文同余方程求解

一次同余方程亦称线性同余方程，是一类简单的同余方程，指未知数仅出现一次幂的同余方程。若a,b都是整数，m是正整数，当a≢0 (mod m)时，把ax=b (mod m)称为模m的一元一次同余方程，简称一次同余方程。一次同余方程亦称线性同余方程，是一类简单的同余方程，指未知数仅出现一次幂的同余方程。最简单的一次同余方为 (mod n)，此处整数 (mod n)及 b 为给定整数，求解 x。这相当于求解一次不定方程（indefinite equation）或一次丢番图方程（Diophantine equation） ，其中，a，b，n为已知整数，求整数解x，y。这一方程有解的充要条件为(a，n)|b。当 时，同余方程有唯一的解 。当 时，只有当d|b时有解，这时命 为 唯一的解， 。则原方程共有 d 个关于模 n 互不同余的解： 。一般的一次同余方程 有解 的充要条件为 。若此条件成立，则共有 组互不同余的解，mod n。关于一次不定方程，中国古代早有研究，如张丘建的“百鸡问”等。关于一次同余方程的解法和性质有下述定理：1.设(a, m) = 1，m>0，则同余式ax≡b(mod m)恰有一个解；2.设(a, m) = d，m>0，则同余式ax≡b(mod m)有解的充分必要条件是d|b，此时恰有d个解。根据以上两个定理，同余方程ax≡b (mod m)在a≢0且(a,m)|b的条件下，必有(a,m)个关于模m互不同余的解。又根据最大公约数的性质，必有二整数x、y，能使ax+my=(a,m)。由于(a,m)|b，所以有 ， ，使 ，由此即可得到原方程的(a,m)个关于模m互不同余的解为。

x≡1(mod6)x≡4(mod9)x≡7(mod15)解：以下同余号≡也用==表示。x≡1(mod6)等价于x==1mod2且x==1mod3x==7mod15等价于x==1mod3且x==2mod5x==4mod9蕴含了x==1mod3于是原同余式组等价于x==1mod2x==4mod9x==2mod5下面是中国剩余定理的等价解法。令x==9*5a+2*5b+2*9cmod2*9*5亦即x=9*5a+2*5b+2*9c+2*9*5k代入原同余式组，得a==1mod2,b==4mod9,c==-1mod5取其代表值即可。如a=1,b=4,c=-1，得到x==67mod90外一则：我的计算过程：x==1@24@9-1@5=>17@18或-1@18=67mod90或-23mod90注：这里的@表示模积计数表示，是我的一种特殊算法，可以方便的计算这类表达式。详见我的相关答题或空间中关于中国剩余定理的文章。楼上几位朋友们则是通过观察找到了快速解法。也可以阐述如下：x≡1(mod6)x≡4(mod9)x≡7(mod15)解：易见x==-5mod6x==-5mod9故x==-5modlcm[6,9]注：lcm表示最小公倍数。即x==-5mod18又观察到x==-23mod18x==-8==-23mod5故x==-23modlcm[18,5]即x==-23==67mod90

由上面的同余方程可知，x+23可以被6，9和15整除，所以有x+23=（6，9，15）*n，其中（a,b,c）表示a,b,c的最小公倍数，n是任意整数；即x=90*n-23

dennis_zyp|十七级 已经出很好的方法。我补充一下。求x^2+8x-13≡0(mod 28)的解和解数解：配方得(x+4)^2==1 mod 4*7解之得x==-3或-5 mod 4且x==-3或-5 mod 7.于是得到：x==-3或-5 mod 28即x==25, 23.及x==-3 mod 4==1==-5 mod 7==2即x==9 mod 28 及x==-5 mod 4==3==-3 mod 7==4即x==11 mod 28.综上，共四解：x==9,11,23,25 mod 28 当然，注意到原同余式组等效于x^2==1 mod 4,等效于x==1 mod 2则简化了：与x==-5, -3 mod 7联立得x==9,-3 mod 14. （注：在-5上加上7*2的倍数立即得9）转化模为28则是x==9,-3, 9+14, -3+14 mod 28即x==9，25，23，11 此外，还可以用y=x+4==1,-1 mod 4,7算出y，再得到x，计算起来也更便捷y==1或-1 mod 4 且y==1或-1 mod 7即y==1 mod 2且y==1或-1 mod 7即y==1 mod 2且y==1 mod 7 或y==1 mod 2且y==-1 mod 7 即y==1或13 mod 14 转化为模28，即y==1, 15, 13, 27 mod 28于是x=y-4==25,11,9,23 mod28

解同余方程组：x≡6(mod11) x≡3(mod 8 ) x≡11(mod20) 等效于同余式组 ( x==6 mod 11 (#1#) x==3 mod 8 (#2#) x==11 mod 4 (#3#) x==11 mod 5 (#4#) 其中,用==表示同余号. ) 即求他们的解集的交集. 其中 (#2#)的解集是(#3#)的解集的真子集.故原同余式组等效于 ( x==6 mod 11 (#1#) x==3 mod 8 (#2#) x==1 mod 5 (#4#转化而来) ) 后文详解得答案为 x==171 mod 440. 过程如下： x== (6/ (8*5) mod 11) *8*5+ (3/ (11*5) mod 8) *11*5+ (1/ (11*8) mod 5) *11*8 （ 注1：其中 x== b/a mod m 用来简化表示 ax == b mod m.我首次见到是在洪伯阳先生的著作中,我常称之为洪伯阳同余表示.在其分子与分母上可以使用同余性质、比例性质、带分数性质即作为假分数、带分数来处理等等.后来发现其他著作中也有,时间先后我没有考证. 下面为表达与计算上的方便,采用我个人引入的模积表示法.我察觉到其形式的对称性,并考虑到了计算的对称性及其同余本质,十分方便计算.以下使用模积表示式进行计算. 注2：上式简化表示为以下形式,称为模积表示.为方便理解写了很多.实际上,有很多过程用心算来完成,可以快速得解. ( 6/ (8*5) @ 11) 3/ (11*5) @ 8) 1/ (11*8) @ 5 ) ） == 6/ -4 @ 11 3/-1 @ 8 1/3 @5 == -3/2==(-3+11)/2=4 @ 11 -3 @ 8 (1+5)/3=2 @ 5 == 4 @ 11 -3 @ 8 2 @ 5 == 4*8-3*11 @ 8*11 2 @5 == -1 @ 88 2 @ 5 == 176-5 mod 88*5 ==171 mod 440 理解了这种方法,对中国剩余定理的本质就更深入一步了. 更多资料,请百度搜索 wsktuuytyh 模积计数法 或 wsktuuytyh 洪伯阳同余表示 或 wsktuuytyh 不定方程 (注：其中来源我的现有姓名何冬州的五笔编码) 事实上,容易看出等效于 x== 6 mod 11 11 mod 8 11 mod 20 == 6 mod 11 11 mod 40 == 11+ (y== -5 mod 11 0 mod 40 ) y== -5/40 @ 11 0/11 @ 40 == 6/-4 @ 11 0 @ 40 == 4 @ 11 0 @ 40 ==160 X==11+Y==171 MOD 440