Extended euclidian gcd Algorith The algorithm Inverse( a, n)is given by 9o=nu=1v=0 g1=au1=0v1= -let y=gm-1 div gi g+1=g1-y gi= gm-1 mod g 1=u-1-y"u1 1= Vi-1-yVi when gi=0 then inverse(a, )=Vi-1Extended Euclidian GCD Algorithm • The algorithm – Inverse(a,n) is given by: – g0=n u0=1 v0=0 – g1=a u1=0 v1=1 – let • y = gi-1 div gi • gi+1 = gi-1 – y*gi = gi-1 mod gi • ui+1 = ui-1 – y*ui • vi+1 = vi-1 – y*vi – when gi=0 then inverse(a,n) = vi-1