As the modulus, m, increases in size it quickly becomes impractical to use multiplication tables or trial and error to find inverses. The Extended Euclidean Algorithm provides a significantly more efficient method for determining the inverse of an integer a modulo m, when it exists.
We first show how the Extended Euclidean algorithm can be used to write the GCD of two integers a and m as a linear combination of these integers. If we define d = gcd(a, m) we seek integers x and y such that ax + my = d. In the special case when d = 1 we show how the value of x in the linear combination represents the inverse of a modulo m.
Lists
Lists
Loading previews...
