Euclid Algorithm-数学形式 105=525+(-1)·420 2415=945.2+525 =525+(-1)·[945+(-1)·525 945=525.1+420 =2.525+(-1).945 525=420.1+105 =2.2415+(-2)·945]+(-1)·945 420=105.4+0. =2.2415+(-5)945. b=ag1 +(ri ab的线性组合，小于b d=Tn a=T1922 ab的线性组合，小于r1 =Tn-2-Tn-19n T1=T293+T3 =Tn-2-9n(rn-3-gn-1rn-2) =-9nTn-3 (1+9ngn-1)rn-2 Tn-2 Tn-14n ab的线性组合，小于rn1 Tn-1=Tngn+1+C ra sb. ab的线性组合，=0 rn是a,b的最小的正的线性组合，也就是a, b的最大公因子Euclid Algorithm – 数学形式 ab的线性组合，小于b ab的线性组合，小于r1 ab的线性组合，小于rn-1 +0 ab的线性组合，=0 rn是a，b的最小的正的线性组合，也就是a，b的最大公因子