同余式x^2=29(mod 35)的所有解怎么求?如题,这个题的解跟29mod5 和 29mod7的逆有什么关系?_百度作业帮
同余式x^2=29(mod 35)的所有解怎么求?如题,这个题的解跟29mod5 和 29mod7的逆有什么关系?
同余式x^2=29(mod 35)的所有解怎么求?如题,这个题的解跟29mod5 和 29mod7的逆有什么关系?
妙妙520頢味
这个方程等价于同余方程组:x² ≡ 29 (mod 5),x² ≡ 29 (mod 7).因为若x满足x² ≡ 29 (mod 35),易见x也满足上述方程组.反过来,若x满足上述方程组,则x²-29被5和7整除,于是被35整除,即有x² ≡ 29 (mod 35).分别求解方程组中的两个方程.x² ≡ 29 ≡ 4 (mod 5),即5 | x²-4 = (x-2)(x+2),得x ≡ ±2 (mod 5).x² ≡ 29 ≡ 1 (mod 7),即7 | x²-1 = (x-1)(x+1),得x ≡ ±1 (mod 7).于是只需求解以下4个线性同余方程组(其实只需解前两个,后两个取负号):x ≡ 2 (mod 5),x ≡ 1 (mod 7);x ≡ 2 (mod 5),x ≡ -1 (mod 7);x ≡ -2 (mod 5),x ≡ 1 (mod 7);x ≡ -2 (mod 5),x ≡ -1 (mod 7).解得x ≡ ±8,±13 (mod 35).总结起来,需要解两类方程.一类是mod质数(方幂)的二次同余方程.对较小的质数可以枚举求解,上面也是这么做的(两个方程的解都可以直接看出来).对较大的质数可利用借助Fermat小定理构造解,但是手算比较困难.另一类是中国剩余定理型的线性同余方程组.这个也有系统的方法,你应该也了解吧.
扫描下载二维码求方程：的解个数
分析：设，那么上述方程解的个数就与同余方程组：的解等价。
设同于方程的解分别是：，那么原方程的解的个数就是
所以现在的关键问题是求方程：的解个数。
这个方程我们需要分3类讨论：
第一种情况：
对于这种情况，如果方程的某个解设为，那么一定有，可以得到，即
所以方程的解个数就是：，也就是
第二种情况：
这样也就是说p|B，设，，本方程有解的充要条件是A|t，
那么我们设t=kA，
所以进一步有：，因为，这样又转化为第三种情况了。
第三种情况：
那么我们要求指标；求指标的话又要求原根。并且奇素数p的原根也是p^a的原根，所以说求个p的原根就好了。
且如果有解，则解的个数为(A,&(p^a))。
求指标的话就是要解决A^x & B (mod p^a)的问题。由于本情况保证了(p^a, B)=1，用个Baby-step-Giant-step就
能解决问题。
方程x^A & B (mod p^a)有解，当且仅当(A,&(p^a))|ind B。ind B表示B对于p^a的任一原根的指标。
如果不知道原根与指标的现在就补一下吧：
原根部分：
定义一：设m&1,(a,m)=1,则使得成立的最小正整数r，称为a对模m的指数，或者a对模m的阶，记为
定理一：若m&1，(a,m)=1,,则
定义二：若，则a是模m的原根。
定理二：如果大于1的正整数m有原根，那么它一共有个不同的原根。
定理三：模m有原根的必要条件是m=2，4，p^a或者2p^a，其中p是奇素数。
定理四：设m&1,所有不同的奇因数是，(g,m)=1，则g是模m的原根的充要条件是：
& &1&=i&=k
指标，n次剩余部分：
现在我们来研究同余式& (a,m)=1，有解的条件以及解数，注意现在的m=p^a或者2p^a，，g是模m的一个原根。
若(n,c)=d ,(a,m)=1，则上述同余式有解的充要条件是d|inda，并且在有解的条件下，解数为d。
在模m的一个简化剩余系中，n次剩余的个数是
定理一：若r通过模c的最小非负完全剩余系，则g^r通过模m的一个简化剩余系。
证明：g是模m的一个原根，则对模m两两不同余，又因为(g,m)=1，所以(g^r,m)=1
因此是模m的一个简化剩余系。
定理一：设a是一整数，(a,m)=1，若对模m的一个原根g，有一整数r存在使得下式
成立，则r就叫做以g为底的a对模m的一个指标,记为r=inda。
阅读(...) 评论()高阶同余方程的解法x^3+5*x^2+9==0 mod 567我会解mod 7和mod 81,但是这个合数怎么解?_百度作业帮
高阶同余方程的解法x^3+5*x^2+9==0 mod 567我会解mod 7和mod 81,但是这个合数怎么解?
高阶同余方程的解法x^3+5*x^2+9==0 mod 567我会解mod 7和mod 81,但是这个合数怎么解?
若a ≡ b (mod mi) (i=1,2...n) 则 a ≡ b (mod [m1,m2,...mn]) 你这儿7和81互质,那直接{x1} ≡ 0 (mod 7) ,{x2} ≡ 0 (mod 81) 则 {x1}∩{x2} ≡ 0 (mod 567) 嘛!注意,每个同余方程的解都是一个解集,不妨设{x1}中的元素满足x10+7p（x10为{x1}中任意一解,称为特解）{x2}中的元素满足x20+81q那么它们的交集即为x10+7p=x20+81q,再用同余去解这个不定方程吧!x10+7p≡x20+81q （mod7）x10≡x20+4q （mod7）继续这么解就能求出最小的p、q值.此时即为交集的一个特解,不妨设为{x∩}的一个特解,设为x∩0那么这个方程的最终解即为x∩0+567n对了,7和mod 81时似乎只要套用缩系就可以了!【经济数学团队为你解答!】
扫描下载二维码同余方程组求解!解同余方程组：x≡6(mod11) x≡3(mod 8 ) x≡11(mod20)急,收到请速回复谢谢!_百度作业帮
同余方程组求解!解同余方程组：x≡6(mod11) x≡3(mod 8 ) x≡11(mod20)急,收到请速回复谢谢!
同余方程组求解!解同余方程组：x≡6(mod11) x≡3(mod 8 ) x≡11(mod20)急,收到请速回复谢谢!
解同余方程组：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
@5==-3/2==(-3+11)/2=4 @ 11-3 @ 8(1+5)/3=2 @ 5==4 @ 11-3 @ 82 @ 5==4*8-3*11 @ 8*112 @5==-1 @ 882 @ 5==176-5 mod 88*5==171 mod 440 理解了这种方法,对中国剩余定理的本质就更深入一步了.更多资料,请百度搜索wsktuuytyh
模积计数法或wsktuuytyh 洪伯阳同余表示或wsktuuytyh
不定方程 (注：其中来源我的现有姓名何冬州的五笔编码) 事实上,容易看出等效于x==6 mod 1111 mod 811 mod 20==6 mod 1111 mod 40==11+(y==-5 mod 110 mod 40) y==-5/40 @ 110/11 @ 40==6/-4 @ 110 @ 40==4 @ 110 @ 40==160X==11+Y==171 MOD 440
本题应该这样求解，
计算 8和20的公倍数里面，120，mod11，余数为6。
然后计算 11与20的公倍数里面的要么是220*n， mod8 余数为 4，8，不能出现1，所以这个题根本没有解。
原方程组等价于x=6(mod11) ,x=3(mod 8),x=11(mod4) ,x=11(mod 5）注意到x=3(mod 8)是x=11(mod4)的解的真子集，故等价于x=6(mod11) ,x=3(mod 8),x=11(mod 5）由于11,8,5两两互质，所以剩下的工作交给中国剩余定理最后得到171是一个解，故通解为x=171(mod440)<...
扫描下载二维码如何解如下同余方程组：4=（3a+14b）(mod 26) (1) 13=(13a+19b) (mod 26) (2)_百度作业帮
如何解如下同余方程组：4=（3a+14b）(mod 26) (1) 13=(13a+19b) (mod 26) (2)
如何解如下同余方程组：4=（3a+14b）(mod 26) (1) 13=(13a+19b) (mod 26) (2)
这是一个线性方程组,可以类比一般的线性方程组进行求解,只是要在mod 26的剩余类环上运算.用消元法.由(2)-4·(1)得a-11b = -3 (mod 26) (3).(1)-3·(3)得-5b = 13 (mod 26),乘以5得b = 13 (mod 26).代回(3)得a = 10 (mod 26).这种解法不是很系统.如果学了矩阵,可以写出方程组的系数矩阵A =3 1413 19行列式3·19-13·14 = 5 (mod 26).由5·(-5) = 1 (mod 26),5 (mod 26)的倒数就是-5 (mod 26).系数矩阵的伴随矩阵A* =19 -14-13 3系数矩阵的逆矩阵为A^(-1) = |A|^(-1)·A* =9 1813 11于是向量(a,b)^T = A^(-1)·(4,13)^T = (10,13)^T.即方程组的解为a = 10 (mod 26),b = 13 (mod 26).
扫描下载二维码