Mersenne numbers are of the form $2^{p} - 1$, $p$ is a prime.
Last $3$ digits can be obtained from $2^{p} - 1 \equiv x \pmod {1000}$.
This is equivalent to $$2^{p} - 1 \equiv x_1 \pmod 8\tag1$$ and $$2^{p} - 1 \equiv x_2 \pmod {125}\tag 2.$$
Congruence $(1)$ is easy since $2^{3} \equiv 0 \pmod 8$.
Congruence $(2)$ is more difficult since it is not easy to find $2^{x_3} \equiv 1 \pmod {125}$.
In this part it is possible to use Euler phi since $\gcd(2, 125)=1$.
I am looking for a method that does not require phi so that solution is possible by chinese remainder theorem. Or such that use of special functions is minimal.
An example number $2^{1279} - 1$.
Here's a hint, though I admit I don't know how to show this more elegantly.
I brute-forced (with Excel's help) that $2^{100} \equiv 1$ (mod $125$).
Does this help?