Computing Multiplicative Inverse ri- mod ro exists iff GCD(ro, r)=1 Would like to fine t such that r t=l mod ro R ecursiy rely find r tk= k mod r °t6=0,t1=1,and °tk=t2-qktr1 mod roComputing Multiplicative Inverse • r1 -1 mod r0 exists iff GCD(r0 , r1 ) = 1 • ==> rm= 1 • Would like to fine t such that r1 t = 1 mod r0 • Recursively find r1 tk = rk mod r0 • t0 = 0, t1 = 1, and • tk = tk-2 -qk-1 tk-1 mod r0