求模乘法逆元

2019-04-13 21:04发布

站内文章 / 模拟电子
17636 0 1604
一、(解存在判定原理) 有限域Z（b）(b>0)，对于任意整数a，若gcd(a,b)=1,则a在有限域中存在唯一的逆元x（a^-1)即a*x=1(mod b),求x 二、对于任意不同时为零的正整数a,b 求满足方程a*x+b*y=gcd(a,b)的解（x,y)。 这两种描述其实是等价的。 对于方程a*x+b*y=gcd(a,b),我们可以这样方程两边同除以gcd(a,b)得 a1*x+b1*y=1;其中a1=a/gcd(a,b) , b= b/gcd(a,b). 则gcd(a1,b1)=1; a1*x=1-b1*y----->a1=1(mod b1) 反之亦然。   a*x+b*y=1( gcd(a,b)=1) 的通解为 x=x0+b*i y=y0-a*i 证明： 设（x1,y1),(x2,y2)为方程的两组解 则a*x1+b*y1=a*x2+b*y2 ->a*(x1-x2)=b*(y2-y1) ->b|[a*(x1-x2)] , gcd(a,b)=1
 ->b|(x1-x2) ->x2=x1+b*i;
x2代入原方程,要使方程恒立则 y2=y1-a*i; 一般化的方程a*x+b*y=c   (gcd(a,b)|c)通解为 x=x0+b/gcd(a,b)*i y=y0-a/gcd(a,b)*i x0,y0为a1*x+b1*y=c1的特解扩大c/gcd(a,b)倍 a1,b1,c1是a,b,c除以gcd(a,b)的结果。
exgcd()求解过程： 因为 d=gcd(a,b)=gcd(b,a%b),d=a*x+b*y d=b*x1+(a-int(a/b)*b)*y1=a*y1+(x1-a/b*y1) 所以 x=y1 y1=x1-a/b*y1
 求解模乘法逆元的代码：   实例：poj1061  

热门文章