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}$

$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.
