矩阵变换在扩展EUCLID算法中的应用

摘要：对于给定的两个正整数a,b,如何确定两个整数u,v,使得 au+bv=gcd(a,b),这里gcd(a,b)表示a,b的最大公约数？本文利用矩阵变换给出两个算法用于求解u,v.

众所周知，对于给定的两个正整数a,求a,b的最大公约数可使用EUCLID算法，其依据是下面的引理。 为了表述方便,下面均用 a/b表a 除以b的商,a%b表a 除以b的余数.

引理1: 设a,b是两个给定的正整数,a>b. 则 gcd(a,b)=gcd(b,a%b).

引理1的证明可参见文献[1],这里略去.

我们称 为关于正整数a,b 的变换矩阵。注意到

=

记 a₁=b,b₁=a%b. 若b₁≠0,则继续对 进行变换，

= =

记 a₂= b₁,b₂=a₁%b₁. 若b₂≠0,则继续对 进行变换，

… …

… = （1）

直到 a_k%b_k=0为止。

如此便可得到 gcd(a,b)=b_k。记矩阵 … 为 。由等式（1）可得 = ， 即ua+vb=b_k=gcd(a,b) 。因此只需计算出矩阵 ，…， ， 的乘积，便可求出u,v。

初始化 u₀=0,v₀=1,p₀=1,q₀=-a/b。若已求出 ，…， ， 的积为 ， 则 = … = = ,即u_k=p_k-1,v_k=q_k-1,p_k=u_k-1+(-a_k/b_k)p_k-1,q_k= v_k-1+(-a_k/b_k)q_k-1。

对于给定的两个正整数a, 从上面的讨论，我们可给出一个非递归的算法来求出两个整数u,b)。

int gcd(int a,int b,int *u,int *v )

/* 不妨设 a>b>0,用*u,*v返回所求的两个整数,函数将返回 gcd(a,b) */

{int tempu,tempv,tempa,p,q;

*u=0,*v=1,p=1,q=-a/b; /*初始化 *u,*v,q的值*/

while(1)

{ tempa=a; a=b; b= tempa%b; if (b==0)break;

tempu=*u,tempv=*v;

*u=p,*v=q,p= tempu +(-a/b)*p,q= tempv+(-a/b)*q;

}

return a;

}

int gcd(int a,int *v ) /* 不妨设 a>b>0,用*u,*v返回所求的两个整数,<a href="/tag/hanshu/" target="_blank" class="keywords">函数</a>将返回 gcd(a,b) */ { int tempu,q; *u=0,q=-a/b; /*初始化 *u,q的值*/ while(1) { tempa=a; a=b; b= tempa%b; if (b==0)break; tempu=*u,tempv=*v; *u=p,p=tempu +(-a/b)*p,q= tempv+(-a/b)*q; } return a; }

这个扩展欧几里德在剩余定理里计算M的逆时有所运用。