This C++ Program demonstrates the implementation of Extended Eucledian Algorithm. For the modular multiplicative inverse to exist, the number and modular must be coprime.

Here is source code of the C++ Program to implement Extended Eucledian Algorithm. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

`/*`

`* C++ Program to Implement Extended Eucledian Algorithm`

`*/`

`#include <iostream>`

`#include <utility>`

using namespace std;

`/* return the gcd of a and b followed by the pair x and y of`

`equation ax + by = gcd(a,b)`

`*/`

pair<int, pair<int, int> > extendedEuclid(int a, int b)

`{`

int x = 1, y = 0;

int xLast = 0, yLast = 1;

int q, r, m, n;

while (a != 0)

`{`

q = b / a;

r = b % a;

m = xLast - q * x;

n = yLast - q * y;

xLast = x;

yLast = y;

x = m;

y = n;

b = a;

a = r;

`}`

return make_pair(b, make_pair(xLast, yLast));

`}`

int modInverse(int a, int m)

`{`

return (extendedEuclid(a, m).second.first + m) % m;

`}`

`//Main`

int main()

`{`

int a, m;

cout<<"Enter number to find modular multiplicative inverse: ";

cin>>a;

cout<<"Enter Modular Value: ";

cin>>m;

cout<<modInverse(a, m)<<endl;

`}`

$ g++ eucledian.cpp $ a.out Enter number to find modular multiplicative inverse: 133 Enter Modular Value: 135 67 ------------------ (program exited with code: 1) Press return to continue

**Sanfoundry Global Education & Learning Series – 1000 C++ Programs.**

If you wish to look at all C++ Programming examples, go to C++ Programs.