$(3^n -1)/2 \% c$ where $c$ is a multiple of $2$

Question

Range of $n\le 10^{18},c\le 10^9$

We cannot calculate directly as the numerator is large. I know modulo inverse concept but this can only be applied when denomenator and mod are coprime

Answer 1

Let $a := (3^n -1)/2$. Write $a = qc + r$ where $0 \leq r < c$, so that $r$ is the solution you are looking for. Then we have $2a = q(2c) + 2r$ with $0 \leq 2r < 2c$, so that $2r$ is the solution to $$3^n -1 \mod{2c}.$$

Solve this equation, divide the solution by two and you are done.