`
feiliboos
  • 浏览: 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')的形式

还有一种是联立两式时把系数化成一样,没试过,不知道行不行……

终于写完了……边写边又开始纠结……
分享到:
评论

相关推荐

    5解线性方程组的迭代法_计算方法_解线性方程组_

    解线性方程组的迭代法,实现线性方程组的迭代算法,易于理解

    非线性方程求根 matlab代码

    matlab函数,包含: 二分法 Newton迭代法 割线法 以上方法均提供求固定区间所有根的函数 解二元非线性方程组

    fsolve解方程_fsolve_非线性方程组_解方程_

    对非线性方程进行求解,包含文档进行解释,通俗易懂

    [MATLAB精品丛书][高清文字版]MATLAB语言常用算法程序集(第2版).pdf

    实现,包括插值、函数逼近、矩阵特征值计算、数值微分、数值积分、方程求根、非线性方程组求解、解线性方程组的直接法、解线性方程组的迭代法、随机数生成、特殊函数计算、常微分方程的初值问题、偏微分方程的数值...

    OpenSAL1.0

    数论算法:大数类(兼容浮点数、整数、与内置类型兼容运算)*、RSA加解密系统*、解同余方程*、孙子定理解同余方程组*、Miller_Rabin素数测试(产生大质数)*、随机数(实数、大数)*、欧几里得算法*。 计算几何算法:...

    C++开源算法库OpenSAL1.1(Open Standardized Algorithm Library) ——静态链接库

    数论算法:大数类(兼容浮点数、整数、与内置类型兼容运算)*、RSA加解密系统*、解同余方程*、孙子定理解同余方程组*、Miller_Rabin素数测试(产生大质数)*、随机数(实数、大数)*、欧几里得算法*。 计算几何算法:...

    C++开源算法库OpenSAL1.1(Open Standardized Algorithm Library)——动态链接库

    数论算法:大数类(兼容浮点数、整数、与内置类型兼容运算)*、RSA加解密系统*、解同余方程*、孙子定理解同余方程组*、Miller_Rabin素数测试(产生大质数)*、随机数(实数、大数)*、欧几里得算法*。 计算几何算法:...

    OpenSAL1.1算法导论开源算法库

    数论算法:大数类(兼容浮点数、整数、与内置类型兼容运算)*、RSA加解密系统*、解同余方程*、孙子定理解同余方程组*、Miller_Rabi n素数测试(产生大质数)*、随机数(实数、大数)*、欧几里得算法*。 计算几何算法...

    一类奇摄动半线性方程组的Robin问题 (2009年)

    研究了一类可作为化学反应模型的奇摄动半线性方程组的RDbin问题,在一定条件下利用边界函数法构造了所论问题一致有效的渐近解,同时讨论了该问题解的存在惟一性,并给出了余项估计。

    主要用matlab与R 实现数值分析、高等代数、数学分析中的问题

    在一般的数值分析教程中,我们学了基本的数值分析算法...线性方程组的求解(包括基础解系的部分)。 向量组的秩,矩阵的秩。 向量正交化(施密特正交化)。 多项式的带余除法。 多项式最大公因数的求法(欧几里得辗转相除法)。

    关于中国剩余定理 (2006年)

    给出了主理想整环上线性同余方程组有解的充要条件,以及求解这类方程组的一个简便算法。

    ACM算法竞赛常用代码

    数论(整除,集合论,关系,素数,进位制,辗转相除,扩展的辗转相除,同余运算,解线性同余方程,中国剩余定理) 指针(链表,搜索判重,邻接表,开散列,二叉树的表示,多叉树的表示) 按位运算(and,or,xor...

    ACM算法模版大集合

    同余方程组 线性方程组 高斯消元法 解mod 2域上的线性方程组 整系数方程组的精确解法 矩阵 行列式的计算 利用矩阵乘法快速计算递推关系 分数 分数树 连分数逼近 数论计算 求N的约数个数 求phi(N) ...

    zhongguo.rar_不互质情况

    中国剩余定理(不互质的情况) 对互质的情况,处理起来比较方便,可以直接套模板 ...方案:对于不互质的模线性方程组,可以进行方程组合并,求出合并后的方程的解,这样就可以很快地推出方程的最终解。

    二维定常不可压缩粘性流动N-S方程的数值流形方法 (2010年)

    将流形方法应用于定常不可压缩粘性流动N-S方程的直接数值求解,建立基于Galerkin加权余量法的N-S方程数值流形格式,有限覆盖系统采用混合覆盖形式,即速度分量取1阶和压力取0阶多项式覆盖函数,非线性流形方程组采用直接...

    论文研究-使用最速下降算法提高极大似然估计算法的节点定位精度.pdf

    阐述了最速下降算法求非线性方程组最优解的原理;提出在距离测量误差较大的情况下,使用最速下降算法优化极大似然估计算法所得的节点定位值,并通过模拟实验证实其可行性。实验结果表明,在无须多余通信代价的条件下...

    A new preconditioned Gauss-Seidel method for linear system

    解线性方程组的一种新的预条件方法,赵景余,张国凤 ,在这篇文章中,我们提出了一种新的预条件,在一定的条件下,我们给出了收敛定理和比较定理.最后数值例子也验证了定理的有效性.

    一类高维随机矩阵置乱变换的周期 (2010年)

    将实数域上线性代数的若干结果,推广到模素数有限域上,得到一类整数矩阵及其相关同余方程组之解的若干新性质;在此基础上将用于置乱的矩阵由2维扩展到任意高维,给出广泛一类高维随机整数矩阵 A决定的置乱变换,在任意...

Global site tag (gtag.js) - Google Analytics