CODEWITHSUNDEEP
c++number-theorymodular-arithmetic
Pranav Venkata
Pranav Venkata

Reputation: 59

Trouble with modular exponentiation

I am trying to solve a problem where we have to output the the last digit of the given number n^p.

int modularExponentiation(int n, long long p, int m){
    if(p == 0) return 1;
    if(p & 1)
        return (n % m * modularExponentiation((n*n) % m, p / 2, m) % m) % m;//line 4
    return modularExponentiation((n*n) % m, p / 2, m) % m;
}

In this recursive code, here we are changing the temporary result by applying modulo in line 4. Will this not bring any change in the final answer? for example if at any intermediary stage the answer is 81^4, applying %10 at 81 and replacing it with 1, will it not change the final result?

Upvotes: 2

Views: 69

Answers (2)

Aplet123
Aplet123

Reputation: 35482

For modular addition and multiplication, you can take a mod at every step and it won't affect the result. In fact, that's how you're supposed to do modular exponentiation to avoid overflows. Therefore, your final function would look like this:

long long modExp(long long n, long long p, long long m) {
    if (p == 0) {
        // m could be 1 you never know
        return 1 % m;
    }
    n %= m;
    return (n * modExp(n, p - 1, m)) % m;
}

Upvotes: 0

MSalters
MSalters

Reputation: 179779

No, this does not affect the result, because (a*b)%m == ((a%m) * (b%m))%m. Exponentiation is of course just repeated multiplication, so the same principle applies.

(81^4)%10 is small enough to try this by hand. Go ahead, write it out.

Upvotes: 2

Related Questions