It Starts with 4

The problem is equivalent to solving the congruence $2^{77232917} - 1 \mod 1000$ . We can break down $1000 = 2^3 5^3$ and solve for both factors separately. It is clear that $2^{77232918} \equiv 0 \mod 2^3$ so the number is congruent with $-1 \mod 8$ . To solve the congruence $\mod 5^3$ first compute $\phi(125) = 125 \times (1 - \frac{1}{5}) = 100$ to simplify $2^{77232917} \equiv 2^{17} \mod 5^3$ . And $2^{17}$ is just $131072$ which is congruent to $72 \mod 5^3$ so the number is congruent to $71 \mod 125$ .

The Chinese Remainder Theorem tells us that there is a class $\mod 1000$ that satisfies both of those congruences, but simply notice that $71 \equiv -1 \mod 8$ so the class $71 + 1000n$ satisfies both congruences, which tells us that the last 3 digits are $071$ .