C++ Program to Implement Extended Eucledian Algorithm

Code:

#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 > 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<
}


Output:

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

------------------
(program exited with code: 1)
Press return to continue



More C++ Programs: