Greatest Common Divisor + Power + Inverse Modulo

gcds.cpp

ll modularExponentiation(ll x,ll n,ll M)
{
    ll result=1;
    while(n>0)
    {
        if(n % 2 ==1)
            result=(result * x)%M;
        x=(x*x)%M;
        n=n/2;
    }
    return result;
}


ll d, x, y;
void extendedEuclid(ll A, ll B) {
    if(B == 0) {
        d = A;
        x = 1;
        y = 0;
    }
    else {
        extendedEuclid(B, A%B);
        ll temp = x;
        x = y;
        y = temp - (A/B)*y;
    }
}

ll modInverse(ll A, ll M)
{
    extendedEuclid(A,M);
    return (x%M+M)%M;    //x may be negative
}

int main( ) {
  extendedEuclid(16, 10);
  cout << ”The GCD of 16 and 10 is ” << d << endl;
  cout << ”Coefficients x and y are ”<< x <<  “and  “ << y << endl;
  return 0;   
}