锐客网

  1. 首页 > it技术 > >

扩展欧几里得|扩展欧几里得算法求解不定方程||中国剩余定理

数论扩展欧几里得同余方程

对于
a x + b y = g c d ( a , b ) ax+by=gcd(a,b) ax+by=gcd(a,b)
这样的方程，可以用扩展欧几里得算法exgcd求出一组通解。
根据欧几里得求gcd：
g c d ( a , b ) = g c d ( b , a % b ) gcd(a,b)=gcd(b,a\%b) gcd(a,b)=gcd(b,a%b)
可得
b x + ( a % b ) y = g c d ( b , a % b ) bx+(a\%b)y=gcd(b,a\%b) bx+(a%b)y=gcd(b,a%b)
根据
a % b = a ? ( a / b ) ? b a\%b=a-(a/b)*b a%b=a?(a/b)?b
可得
b x + a y ? ( a / b ) b ? y = g c d ( b , a % b ) bx+ay-(a/b)b*y=gcd(b,a\%b) bx+ay?(a/b)b?y=gcd(b,a%b)
化简得
a y + b ( x ? ( a / b ) y ) = g c d ( b , a % b ) ay+b(x-(a/b)y)=gcd(b,a\%b) ay+b(x?(a/b)y)=gcd(b,a%b)
令
x ′ = y , y ′ = ( x ? ( a / b ) y ) x' = y , y' = (x-(a/b)y) x′=y,y′=(x?(a/b)y)
可得
a x ′ + b y ′ = g c d ( b , a % b ) < = > a x + b y = g c d ( a , b ) ax' +by' =gcd(b,a\%b) < => ax+by=gcd(a,b) ax′+by′=gcd(b,a%b)<=>ax+by=gcd(a,b)
根据
g c d ( a , 0 ) = a gcd(a,0)=a gcd(a,0)=a a x + b y = a ax+by=a ax+by=a
可以得出一组平凡解
x = 1 , y = 0 x=1,y = 0 x=1,y=0
【扩展欧几里得|扩展欧几里得算法求解不定方程||中国剩余定理】所以一直递归下去可以得出一组平凡解，然后再往回带得出 a x + b y = g c d ( a , b ) ax+by=gcd(a,b) ax+by=gcd(a,b)的一组解。
泛化来看不定方程
a x + b y = c ax+by=c ax+by=c
只有满足 c % g c d ( a , b ) = = 0 c\%gcd(a,b) == 0 c%gcd(a,b)==0才有解。
求解同余方程
a x ≡ bm o dn ax \equiv b\ mod\ n ax≡b mod n
a x = b + n y ax = b+ny ax=b+ny
令 y = -y
a x + n y = b ax+ny = b ax+ny=b
就转变成了上述形式
中国剩余定理
https://blog.csdn.net/niiick/article/details/80229217
https://www.cnblogs.com/freinds/p/6388992.html

    推荐阅读


    上一篇：Java_集合—List

    下一篇：我读|我读 琅琊榜