Math-数学拓展欧几里德算法
Posted by houbb on August 23, 2017
拓展欧几里得算法
对于不完全为 0 的非负整数 a,b,gcd(a,b)表示 a,b 的最大公约数,必然
存在整数对 x,y ,使得 gcd(a,b)=ax+by.
求解过程
求解 x,y的方法及证明 (设 a>b)
1,显然当 b=0,gcd(a,b)=a.此时 x=1,y=0;
2,a>b>0 时,设 ax1+ by1= gcd(a,b);
bx2+ (a mod b)y2= gcd(b,a mod b);
根据朴素的欧几里德原理有 gcd(a,b) = gcd(b,a mod b);
则: ax1+ by1=