如何用线性组合表示最大公约数

用辗转相除法就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)

线形组合不好表示的,不过可以用以下的质因数分解式表示两个数的最大公约数.
设两数为A1,A2
假设Ai=∏pj^kji
j>=1,i=1,2,pj均为质数,上式即质因数分解式.
那么(A1,A2)==∏pj^min(kj1,kj2)