A sampl dle run GCD(75,28) to=0, 75=2×28+19 28=1×19+9 °t2=0-2×t1=73mod75 19=2×9+1 t3=1-1×t2=3mod75 ·9=9×1 t4=73-2×t=67mod75 GCD(75,28)=1 tk=tk-2-qk- tk- modA sample run • GCD(75, 28) • 75 = 2  28 + 19 • 28 = 1  19 + 9 • 19 = 2  9 + 1 • 9 = 9  1 • GCD(75,28) = 1 • t0 = 0, • t1 = 1, • t2 = 0-2t1 = 73 mod 75 • t3 = 1-1t2 = 3 mod 75 • t4 = 73-2t3 = 67 mod 75 tk = tk-2 -qk-1 tk-1 mod r0