数论关于欧几里德的运用广义欧几里得除法求整数s,t,使得sa+tb=(a,b),其中,a=3589,b=1613.

Question

数论关于欧几里德的
运用广义欧几里得除法求整数s,t,使得 sa+tb=(a,b),其中,a=3589,b=1613.

Answer 1

1、 3589= 2*1613+363,
1613= 4*363+161,
363= 2*161+41,
161=3*41+38,
41=1*38+3,
38=12*3+2,
3=1*2+1,
2=2*1.
所以他的最大公因数是1.
则：1=3-2*1=3-（38-12*3）=-38+（41-1*38）*13=41*13-14*（161-3*41）=-14*161+（363-2*161）*55=363*55-（1613-4*363）*124=-1613*124+（3589-2*1613）*551=551*3589*-1226*1613即s=551,t=1226.