How to evaluate last nine digits of $(2^{120} - 1) / 3$ without any intermediate value exceeding $2^{32}$ Here's what I know:


*

*The modular inverse of 3 for the modular base of $10^9$ is 666,666,667

*The last nine digits of $2^{120}$ is 280,344,576.

*The product of the two exceeds $2^{32}$ (it is around $2^{57.375}$)

*$2^{120}$ - 1 is divisible by 3, but 280,344,575 is not.


I'd appreciate some clues on how to determine the last nine digits of $(2^{120} - 1) /3$ without any intermediate value exceeding $2^{32}$
 A: Suppose you are dividing by hand $2^{120}-1$ by $3$ by the usual algorithm: when you get to the last 9 digits, you'll have on the left the remainder carried over from the preceding division, and that remainder can be $0$, $1$ or $2$. But since we know the division is exact, the only possibility is $1$ and the answer therefore is 
$$1,280,344,575/3=426781525.$$
A: $3=2^2-1$, so
$$
\frac{2^{120}-1}{2^2-1}=1+2^2+2^4+2^6+\cdots+2^{118}.
$$
This suggests one way of achieving your goal. You can calculate the remainders of all of $2^{2n}$ modulo $10^9$ without ever needing intermediate results in excess of $4\cdot 10^9<2^{32}$. If you have already calculated the remainder  $2^{2k}\equiv r_k\pmod{10^9}$, then you can calculate the next remainder $2^{2(k+1)}\equiv 4r_k\equiv r_{k+1}\pmod{10^9}$.
As the last step you just calculate the sum $r_0+r_1+\cdots+r_{59}$. Whenever you overflow $>10^9$ just subtract $10^9$ from the intermediate result.
A: $$\frac{280344575}{3} \equiv \frac{280344576}{3}-\frac13 \equiv 93448192 - 666666667 \equiv 426781525 \pmod{10^9} $$
and you can then check that
$$ 426781525 \cdot 3 \equiv 280344575 \pmod{10^9} $$
