(1859,1573) 1a=1859 1573=b1859=1×1573+286 1573 1=q4 1573=5×286+143 1573 286=n 286=2×143 1430 5=q 所以(-1859,1573)=143 286143= 2862=4 0=乃 例2a=169,b=121 169 121 169=1×121+48 121 1 121=2×48+25 121 48 48=1×25+23 % 2 25=1×23+2 4825 23=11×2+1 1 2=2×1 23 所以(169,121)=1 1 32 11 1 0 ·7·(1859, 1573 ) . | a | = 1859 { 1573 1573 = b 1 = q1 1859 = 1×1573 + 286 1573 = 5×286 + 143 1573 7 1430 286 = r1 I 5 = q2 286 = 2×143 所以( - 1859 ,1573) = 143 . 286 286 143 = r2 2 = q3 0 = r3 # 例 2 a = 169, b = 121 . 169 + 121 121 s 1 169 = 1×121 + 48 121 = 2×48 + 25 121 S 96 48 e 2 48 = 1×25 + 23 25 = 1×23 + 2 48 { 25 25 1 23 = 11×2 + 1 2 = 2×1 25 23 23 1 所以( 169, 121) = 1 . 23 22 2 11 2 2 1 2 0 · 7 ·