Modular exponentiation of a fraction

Question

Modular of a rational number ie a/b where a,b belong to set of integers can be found by calculating modular inverse of b.mod(m) = b^-1. Finally a*b^-1mod(m) gives us the required result. How can we find modular of (a/b)ⁿ efficiently? Given n is of the order of 1e9, is there an efficient method to calculate the result keeping in mind the overflow of values? I tried something like this as below.

const int modular = 1e9+7;


int modular_inverse(long long base) {
    long long result = 1;
    int power = modular-2;
    int MOD = modular;
    while(power > 0) {

        if(power & 1) {
            result = (result*base) % MOD;
        }
        base = (base * base) % MOD;
        power >>= 1;
    }
    return result;
}

int main() {
    int a = 27;
    int b = 2048;
    int A = a;
    int B = b;

    for(int i = 0; i < 1e9-1; ++i) {
        A *= a;
        B *= b;
        A = A%modular;
        B = B%modular;
    }
    int B_inv = modular_inverse(B);
    long long res = A*B_inv;
    res = res%mod;
    cout << res << endl;
}

Answer 1

You can calculate (ab^-1)ⁿmod(M) using fast exponentiation

Note that you actually implemented fast exponentiation in the modular_inverse function where you calculate base^-1mod(M) which is equal to base^M-2mod(M) if M is a prime number.

So you need to calculate b^-1 (which you already do), then calculate (ab^-1)mod(M) . Then raise the result to the power of n using fast exponentiation, doing all your operations modulo M.