数论关于欧几里德的运用广义欧几里得除法求整数s,t,使得 sa+tb=(a,b),其中,a=3589,b=1613.
2020-04-10
数论关于欧几里德的
运用广义欧几里得除法求整数s,t,使得 sa+tb=(a,b),其中,a=3589,b=1613.
优质解答
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.
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.