`
- 浏览:
659530 次
-
前几天纠结了差不多一个多小时,终于把线性同余方程组的求解纠结清楚了……果然还是写下来怕自己忘记……其实qzone不适合写这种文章……不过反正也只有自己看就无所谓了……嗯……归纳一下线性同余方程ax≡b(mod n)是一个同余方程,表示ax mod n=b(or (b mod n)),求解这样一个x存在这样的x当且仅当gcd(a,n)|b那么所有的解可以表示为{x0+kn/d}
(d=gcd(a,n))在n的完系中,共有d个解那么怎样找到这样一个x0呢若这个方程有解,d=gcd(a,n),根据裴蜀定理,存在整数对(y,z),使得ay+nz=d①,这个整数对可以由ext_gcd求得我们发现ax mod n=b 可以表示为ax+ny‘=b②,他与①式非常相像实际上,由于d|b,把①式乘一个b/d,即可得到ay*b/d+nz*b/d=b③②式右边=③式右边,∴x=y*b/d因为y已知,所以求得了这样一个x0,得到了整个方程的解线性同余方程组//设c=m2-m1,d=gcd(b1,b2)先讨论两个线性同余方程的情况x≡b1(mod m1)①x≡b2(mod m2)②①式等价于x=b1*y+m1,②式等价于x=b2*z+m2将两式联立,整理可得b1y-b2z=c这又是二元一次补丁方程ax+by=c的形式,根据裴蜀定理,有解的条件是d|(m2-m1)所以可用ext_gcd解出y',z'得到b1y'+b2z'=d③③式乘一个c/d,得b1y'*c/d+b2z'*c/d=m2-m1④x=y'*c/d*b1+m1,得解显然y'有可能是负数,回代会造成x的大小无法控制,如果要得到最小非负整数解怎么办呢二元一次不定方程ax+by=c的通解为x=x0+kb y=y0-ka (gcd(a,b)=1)⑤而这里的a=b1*c/d,b=b2*c/d,c=m2-m1所以我们可以把y’的范围控制在(0,b2/d)内为什么是b2/d而不是b2*c/d呢,因为gcd(a,b)=c≠1,按照⑤式的出来的解是通解的真子集,所以在枚举时要除以一个d所以我们可以把y'做这样的处理y'=(y' mod (b2/d)+(b2/d)) mod (b2/d)这样得到的y'是最小的非负整数y',从而可解得最小的x当线性同余方程组不止两个式,可采用上述解法先求得两个方程的解xs然后构造出新的方程x≡xs(mod lcm(m1,m2))(若x有大于xs的解,那么他至少大于等于lcm(m1,m2))然后与第三个式子联立,递推求解若m1,m2,m3……mn两两互素,即lcm(mi,mj)=mi*mj,此时可使用中国剩余定理以上讨论的是x不带系数的方程组求解若x带系数,即构成aix≡bi(mod mi)这种形式有两种做法一是两边同除以gcd(ai,mi),变成ai'x≡bi'(mod mi') gcd(ai',mi')=1此时可求ai'关于mi'的逆元e,最后化得x≡bi'*e(mod mi')的形式还有一种是联立两式时把系数化成一样,没试过,不知道行不行……终于写完了……边写边又开始纠结……
分享到:
Global site tag (gtag.js) - Google Analytics
相关推荐
解线性方程组的迭代法,实现线性方程组的迭代算法,易于理解
matlab函数,包含: 二分法 Newton迭代法 割线法 以上方法均提供求固定区间所有根的函数 解二元非线性方程组
对非线性方程进行求解,包含文档进行解释,通俗易懂
实现,包括插值、函数逼近、矩阵特征值计算、数值微分、数值积分、方程求根、非线性方程组求解、解线性方程组的直接法、解线性方程组的迭代法、随机数生成、特殊函数计算、常微分方程的初值问题、偏微分方程的数值...
数论算法:大数类(兼容浮点数、整数、与内置类型兼容运算)*、RSA加解密系统*、解同余方程*、孙子定理解同余方程组*、Miller_Rabin素数测试(产生大质数)*、随机数(实数、大数)*、欧几里得算法*。 计算几何算法:...
数论算法:大数类(兼容浮点数、整数、与内置类型兼容运算)*、RSA加解密系统*、解同余方程*、孙子定理解同余方程组*、Miller_Rabin素数测试(产生大质数)*、随机数(实数、大数)*、欧几里得算法*。 计算几何算法:...
数论算法:大数类(兼容浮点数、整数、与内置类型兼容运算)*、RSA加解密系统*、解同余方程*、孙子定理解同余方程组*、Miller_Rabin素数测试(产生大质数)*、随机数(实数、大数)*、欧几里得算法*。 计算几何算法:...
数论算法:大数类(兼容浮点数、整数、与内置类型兼容运算)*、RSA加解密系统*、解同余方程*、孙子定理解同余方程组*、Miller_Rabi n素数测试(产生大质数)*、随机数(实数、大数)*、欧几里得算法*。 计算几何算法...
研究了一类可作为化学反应模型的奇摄动半线性方程组的RDbin问题,在一定条件下利用边界函数法构造了所论问题一致有效的渐近解,同时讨论了该问题解的存在惟一性,并给出了余项估计。
在一般的数值分析教程中,我们学了基本的数值分析算法...线性方程组的求解(包括基础解系的部分)。 向量组的秩,矩阵的秩。 向量正交化(施密特正交化)。 多项式的带余除法。 多项式最大公因数的求法(欧几里得辗转相除法)。
给出了主理想整环上线性同余方程组有解的充要条件,以及求解这类方程组的一个简便算法。
数论(整除,集合论,关系,素数,进位制,辗转相除,扩展的辗转相除,同余运算,解线性同余方程,中国剩余定理) 指针(链表,搜索判重,邻接表,开散列,二叉树的表示,多叉树的表示) 按位运算(and,or,xor...
同余方程组 线性方程组 高斯消元法 解mod 2域上的线性方程组 整系数方程组的精确解法 矩阵 行列式的计算 利用矩阵乘法快速计算递推关系 分数 分数树 连分数逼近 数论计算 求N的约数个数 求phi(N) ...
中国剩余定理(不互质的情况) 对互质的情况,处理起来比较方便,可以直接套模板 ...方案:对于不互质的模线性方程组,可以进行方程组合并,求出合并后的方程的解,这样就可以很快地推出方程的最终解。
将流形方法应用于定常不可压缩粘性流动N-S方程的直接数值求解,建立基于Galerkin加权余量法的N-S方程数值流形格式,有限覆盖系统采用混合覆盖形式,即速度分量取1阶和压力取0阶多项式覆盖函数,非线性流形方程组采用直接...
阐述了最速下降算法求非线性方程组最优解的原理;提出在距离测量误差较大的情况下,使用最速下降算法优化极大似然估计算法所得的节点定位值,并通过模拟实验证实其可行性。实验结果表明,在无须多余通信代价的条件下...
解线性方程组的一种新的预条件方法,赵景余,张国凤 ,在这篇文章中,我们提出了一种新的预条件,在一定的条件下,我们给出了收敛定理和比较定理.最后数值例子也验证了定理的有效性.
将实数域上线性代数的若干结果,推广到模素数有限域上,得到一类整数矩阵及其相关同余方程组之解的若干新性质;在此基础上将用于置乱的矩阵由2维扩展到任意高维,给出广泛一类高维随机整数矩阵 A决定的置乱变换,在任意...