给定两个正整数m和n,我们计算它们的最大公因子d和两个整数a和b,使得a*m+b*n=d 算法流程 　　E1.置a'=b=1;a=b'=0;c=m,d=n; 　　E2.计算d和r,使得c=q*d+r; 　　E3.若r==0;则退出,当前已有a*m+b*n=d; 　　E4;c=d;d=r;t=a';a'=a;a=t-q*a;t=b';b'=b;b=t-q*b;返回E2. 证明 　　对于已有的m和n,假设m>n;如果刨除变量a,b,a',b';算法与欧几里得算法完全一样,为计算最大公约数的算法. 　　最终要求的为a*m+b*n=d=GCD(m,n);如果改式子成立由欧几里得算法可推出a'*n+b'*(m%n)=GCD(n,m%n); 　　因为GCD(m,n)=GCD(n,m%n); 　　所以a*m+b*n=a'*n+b'*(m%n) 　　　　　　　　=a'*n+b'*(m-(m/n)*n) 　　　　　　　　=a'*n+b'*m-b'*(m/n)*n 　　　　　　　　=b'*m+(a'-b'*(m/n))*n 　　所以a=b';b=a'-b'*(m/n); 　　可以推出根据a‘、b'可以计算a、b。 代码实现