Extended Euclidian gcd Algorithm Example Find inverse of 3 mod 460 u 0 4601 0 3 0 21531 153 33 0 3460 So,31mod460=-153mod460=307mod460Extended Euclidian GCD Algorithm • Example: – Find inverse of 3 mod 460 i y g u v 0 - 460 1 0 1 - 3 0 1 2 153 1 1 -153 3 3 0 -3 460 – So, 3-1 mod 460 = -153 mod 460 = 307 mod 460