用线性组合表示两个数的最大公约数

用辗转相除法就OK了

举个例子求(42,15)并用42和15线性表示(42,15)

解：利用辗转相除法

42=15*2+12①

15=12*1+3②

12=3*4③

所以(42,15)=(15,12)=(12,3)=3

由①有12=42-15*2代入②得3=15-12=15-(42-15*2)=-42+15*3

所以(42,15)=-42+15*3=3即为所求


一般地设整数a和b,有辗转除法

a=bq1+r1(0<r1<b)

b=r1q2+r2(0<r2<r1)

r1=r2q3+r3(0<r3<r2)

……

rk-2=rk-1qk+rk(0<rk<rk-1)

……

rn-2=rn-1qn+rn

rn-1=rnqn+1

则(a,b)=(b,r1)=(r1,r2)=……=(rk-1,rk)=……=(rn-1,rn)=rn

设Q0=0，P0=1,Q1=1,P1=q1,Qk=qkQk-1+Qk-2,Pk=qkPk-1+Pk-2(k>=2)

则有aQk-bPk=(-1)^(k-1)*rk(k=1,2,……,n)