# Last 3 digits of Mersenne numbers

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

• It is Mersenne.
– quid
Feb 2, 2016 at 20:09
• "I am looking for a method..." a method for what? For finding the last 3 digits? Feb 2, 2016 at 20:53
• Which of the following are you talking about? Mersenne numbers are of the general form $M_n = 2^{n} - 1$, where $n$ can be any nonnegative integer, composite or prime. Whereas n being prime gives a subset of Mersenne numbers, and n being prime is a necessary but not sufficient condition for $M_p$ to be prime.
– smci
Mar 25, 2019 at 5:04

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?

• Thats what the Euler Totient Function does. OP asked for a solution without that, and I don't think he meant brute-forcing Feb 2, 2016 at 21:09
• I'm guessing, though, that there's some way to find $100$ without doing an exhaustive search like I did. It seems too ... clean. I was a bit surprised that it was $100$ when I found it. But now that we have $x_3$, the OP can "do an end run" to find a clever way that it can be calculated, and that would be a good answer, no?
– John
Feb 2, 2016 at 21:19
• Read this page. You'll see $\phi(125)=100$, so $2^{100}\equiv 1\mod 125$. There's really no reason to brute-force this. Feb 2, 2016 at 21:20
• I guess I didn't know that this result followed from the Totient function, so I learned something. But it also tells me that it's questionable that it's "not so easy to find $2^{x_3} \equiv 1$ (mod $125$)" if one only needs to calculate $\phi(125)$. $125=5^3$ so all of the relatively prime numbers $125$ or below are the ones without any factors of $5$, so ... $100$ of them! Seems pretty easy, anyway.
– John
Feb 2, 2016 at 21:28
• Right. In fact, when writing $N=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$ where all $p_i$ are distinct primes and $e_i>0$, then $$\phi(N)=(p_1-1)p_1^{e_1-1}\cdot (p_2-1)p_2^{e_2-1}\cdots(p_k-1)p_k^{e_k-1}$$So in fact, we don't even have to count the number of numbers coprime to $N$, even if the prime factorization of $N$ is more complicated (but known). Note that with that formula, it only takes a second to see $\phi(5^3)=(5-1)5^2=100$. Feb 2, 2016 at 21:33

You could find $$2^{1279}\mod 125$$ without invoking Euler's totient function if you know that

$$2^7=128\equiv3\bmod125$$ and $$3^7=2187\equiv62\bmod125$$:

these imply that $$2^{49}=(2^7)^7\equiv3^7\equiv62\bmod125$$, so $$2^{50}\equiv2\times62\equiv-1\bmod125$$.

Then $$2^{1279}=(2^{50})^{25}2^{29}\equiv-2\times3^4=-162\equiv88\bmod125$$.

• If you insisted on not using $\phi$ then your answer's method is suspect: how do you know to calculate those particular powers $2^7$, $2^{49}$ and $2^{50}$ modulo 125 if you don't already know that 50 is the pertinent power? Given that factorising 125 is easy, invoking $\phi$ is surely not that hard, and it makes the method more honest. $125=5^3$ and 5 is prime, so $\phi(125)=(5-1)5^2=100$. May 20, 2020 at 12:42