Extended Euclidean Algorithm and find modular inverse

extended_euclidean.cc

// return <gcd(a, b), <x, y>> such that ax + by = gcd(a, b)
pair< int, pair<int, int> > extended_euclidean(int a, int b) {
    if (b == 0) return make_pair(a, make_pair(1, 0));
    pair< int, pair<int, int> > next = extended_euclidean(b, a % b);
    int y = next.second.first, x = next.second.second;
    y = y - (a / b) * x;
    return make_pair(next.first, make_pair(x, y));
} 

// p is prime, return b such that a * b = 1 (mod p)
int modular_inverse(int a, int p) {
    pair< int, pair<int, int> > tuple = extended_euclidean(a, p);
    if (tuple.first != 1) return -1;
    int ret = tuple.second.first;
    while (ret < 0) ret += p;
    return ret;
}