Number Theory - Extended Euclidean Algorithm

In our previous article we learned matrix exponentiation, modulo multiplicative inverse using Fermat’s little, so let’s continue with what is Extended Euclidean algorithm and how can we use it to get modulo multiplicative inverse.

So, be relaxed and keep reading as we will be making it super easy for you to understand this concept and absorb its easy implementation 😊

Note: If you have not read our previous article on Modular Arithmetic – 2,then we highly recommend you to first read that article as we will be using some concepts of that article here.

1. What is Extended Euclidean Algorithm?

Definition from Wikipedia: In arithmetic and computer programming , the extended Euclidean algorithm is an extension to the Euclidean algorithm , and computes, in addition to the greatest common divisor of integers a and b, also the coefficients of Bézout's identity , which are integers x and y such that:

Now let’s see some proof so that we can clearly understand how this work? And most important why this works?

Proof: Consider GCD(a,b) = ax + by we have to find x = ?, y = ?.

As we know that in terms of GCD, we can write (a,b) as (b % a , a) this is same as what we did in euclidean algorithm to calculate GCD.

let’s put this new form of ‘a’ and ‘b’ in our orignal equation so we get,

( b % a ) * x¹ + a * y¹ = GCD( b % a , a) let’s denote this expression by g.

here x¹ and y¹ are new instance of x and y, as in original equation.

( b % a ) * x¹ + a * y¹ = g …1

Now, by Donald Knuth Floored division co-efficient, we know that

b % a = b – ( (b/a) * a ) ….2

E.g. ( 16 % 5 ) = 16 – ( (16/5) * 5) = 1 which is same as 16 % 5 = 1

hence, from equation 1 and 2 we get,

g = ( b % a ) * x¹ + a * y¹ = ( b – ( ( b / a ) * a) * x¹ + a * y¹ …3

g = ( b * x¹) – ( ( b / a ) * a) * x¹ ) + a * y ¹

g = ( b * x¹) – a* ( ( b / a ) * x¹ ) + y ¹ ) …taking ‘a’ common from right side of minus.

Now, after rearranging above equation we get,

g = a* ( y¹ - ( b / a ) * x¹ ) + b * x ¹ …4

Comparing Eq.4 with GCD(a,b) = ax + by, we get

x = ( y¹ - ( b / a ) * x¹ ) and y = x¹

Voila !! we succesfully derived our ‘x’ and ‘y’ values in terms of ‘a’ and ‘b’.

So now it’s coding time, Below it the implementation have a look:

Time Complexity: O(Log a)



Now, you mind may ask you a question where is modulo multiplicative inverse in the picture, well above was the way how we can implement extended Euclidean algorithm and now we will see, how it can be used to calculate multiplicative inverse under mod m.

2. Extended Euclidean Algorithm as modulo multiplicative inverse:

By extended Euclidean algorithm we know that if two integers are co-prime we can write them as: ax + my = GCD(a, m) just replaced ‘b’ with ‘m’ to ease understanding.

As, we know that ‘a’ and ‘m’ are relatively prime, i.e. GCD( a , m) = 1, hence we can write our original equation as below:
a * x + m * y = 1

Now, taking modulo ‘m’ on both sides of above equation, we get

( a * x + m * y ) mod m ≡ 1 (mod m)

as, ( m * y ) mod m = 0, for any value of y since ( 7 * 10 ) % 7 = 70 % 7 = 0,
so above equation can be written as,

(a * x) mod m ≡ 1 (mod m) i.e. a * x ≡ 1 (mod m)

Dividing by ‘a’ on both sides in above equation, we get

x ( mod m) ≡ a^-1 i.e. a^-1 ≡ x ( mod m)

This is what we wanted right? i.e. a^-1 which is same as x ( mod m ) and we can calculate value of ‘x’ using Extended Euclidean Algorithm.

Below is implementation of above idea:

just add these cout statement in above code of extended Euclidean algorithm you will get a^-1 as expected.

Easy right?

It is always better to solve a question after you learn a new concept as it helps in making concrete concepts.

So, below are problems which are handpicked by Programmers Army to make your concept more solid which you learned.

We highly recommend to solve above problems if you got stuck read editorials for guidance.

Conclusion: We learned how to implemented modulo multiplicative inverse with use of Extended Euclidean Algorithm.

Below is short glimpse for quick revision.

So that’s it for this article we will be coming up with our next article on further topics of number theory very soon till then keep learning, keep coding, keep reading and keep improving !!

Happy Coding
By Programmers Army 😊