__Number Theory - Extended Euclidean Algorithm__

__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:

**
ax + by = GCD( a , b ) where a and b are co-prime with each other.
**
In, simple words Extended Euclid’s Algorithm is just an extension to
Euclid’s Algorithm, In this we not only get GCD of two numbers but also two
coefficients ‘x’ and ‘y’ such that ax + by = GCD( a, b)

Note: GCD(a,b) has a special property that it can always be represented in the form of an equation, i.e., ax + by = GCD(a, b) as stated by Bézout's identity .

E.g. **a = 35, b = 15** and GCD(a,b) = GCD(35,15) = 5 with x =
1, y = -2 i.e. we can get 35 * (1) + 15 * (-2) = 5.

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**let’s denote this expression by g.

^{1}+ a * y^{1}= GCD( b % a , a)here x

^{1 }and y

^{1}are new instance of x and y, as in original equation.

**( b % a ) * x**

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

^{1}+ a * y^{1}= g …1**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

^{1}+ a * y

^{1}= ( b – ( ( b / a ) * a) * x

^{1}+ a * y

^{1}…3

g = ( b * x

^{1}) – ( ( b / a ) * a) * x

^{1 }) + a * y

^{1}

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

Now, after rearranging above equation we get,

**
g = a* ( y ^{1} - ( b / a ) * x^{1 }) + b * x ^{1}
**
…4

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

**x = ( y**

^{1}- ( b / a ) * x^{1 }) and y = x^{1}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**

This is what we wanted right? i.e.

^{-1}≡ x ( mod m)**a**which is same as

^{-1}**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.

1. **Problem from Hackerrank: **
https://www.hackerrank.com/contests/
test-contest-47/challenges/m158-multiple-euclid

2. **Problem from CodeForces:**
https://codeforces.com/problemset
/problem/687/B

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.

**
**

ax + by = GCD( a , b ) where a and b are co-prime with each other.

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 **
**😊**