# Extended Euclidean Algorithm in C++

«
»
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.

1. `/*`
2. ` * C++ Program to Implement Extended Eucledian Algorithm`
3. ` */`
4. `#include <iostream>`
5. `#include <utility> `
6. ` `
7. `using namespace std;`
8. `/* return the gcd of a and b followed by the pair x and y of `
9. `  equation ax + by = gcd(a,b)`
10. `*/`
11. `pair<int, pair<int, int> > extendedEuclid(int a, int b) `
12. `{`
13. `    int x = 1, y = 0;`
14. `    int xLast = 0, yLast = 1;`
15. `    int q, r, m, n;`
16. `    while (a != 0) `
17. `    {`
18. `        q = b / a;`
19. `        r = b % a;`
20. `        m = xLast - q * x;`
21. `        n = yLast - q * y;`
22. `        xLast = x; `
23. `        yLast = y;`
24. `        x = m; `
25. `        y = n;`
26. `        b = a; `
27. `        a = r;`
28. `    }`
29. `    return make_pair(b, make_pair(xLast, yLast));`
30. `}`
31. ` `
32. `int modInverse(int a, int m) `
33. `{`
34. `    return (extendedEuclid(a, m).second.first + m) % m;`
35. `}`
36. ` `
37. `//Main`
38. `int main()`
39. `{`
40. `    int a, m;`
41. `    cout<<"Enter number to find modular multiplicative inverse: ";`
42. `    cin>>a;`
43. `    cout<<"Enter Modular Value: ";`
44. `    cin>>m;`
45. `    cout<<modInverse(a, m)<<endl;`
46. `}`

```\$ g++ eucledian.cpp
\$ a.out

Enter number to find modular multiplicative inverse: 133
Enter Modular Value: 135
67

------------------
(program exited with code: 1)

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