2
$\begingroup$

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

$\endgroup$
3
  • 2
    $\begingroup$ It is Mersenne. $\endgroup$
    – quid ♦
    Feb 2, 2016 at 20:09
  • $\begingroup$ "I am looking for a method..." a method for what? For finding the last 3 digits? $\endgroup$
    – Wojowu
    Feb 2, 2016 at 20:53
  • $\begingroup$ 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. $\endgroup$
    – smci
    Mar 25, 2019 at 5:04

2 Answers 2

Reset to default
0
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ Thats what the Euler Totient Function does. OP asked for a solution without that, and I don't think he meant brute-forcing $\endgroup$
    – vrugtehagel
    Feb 2, 2016 at 21:09
  • $\begingroup$ 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? $\endgroup$
    – John
    Feb 2, 2016 at 21:19
  • 1
    $\begingroup$ 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. $\endgroup$
    – vrugtehagel
    Feb 2, 2016 at 21:20
  • $\begingroup$ 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. $\endgroup$
    – John
    Feb 2, 2016 at 21:28
  • 1
    $\begingroup$ 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$. $\endgroup$
    – vrugtehagel
    Feb 2, 2016 at 21:33
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$
    – Rosie F
    May 20, 2020 at 12:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .