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

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