Search code examples
c++divisionmoduloexponentiation

C++ Division with modulo

I want to calculate result of this equation

[(pow(4, p) - 1) / 3] % q

I wrote a function pow that returns p-th power of 4 mod q, but I can't apply it here. How can I do it?

p, q are integers and could be large - up to 1 000 000 000.

Thanks in advance.

Solution

  • Calculate pow(4, p) - 1 modulo 3*q, and divide the result by 3. To do the exponentiation, use a Modular exponentiation algorithm.

    Edit: This will give you integer division (i.e. rounding down the result). See @lisyarus's answer for division in the ring of integers modulo q.

    If q is not divisible by 3 then both answers should give the same result, because pow(4, p) - 1 is always divisible by 3 so the rounding-down of integer division won't come into play. If q is divisible by 3 then there is no multiplicative inverse and only this method can be used.