C++ Division with modulo

Question

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.

Answer 1

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.

Answer 2

It depends on what you mean by division by 3. If it is normal integer division, it seems that @interjay answered this. If it is a division by 3 in the ring of integers modulo p, than you should find the inverse of 3 modulo p, if it exists.