I am trying to determine the smallest odd n > 1 where the Mersenne number $2^n - 1$ is divisible by twin primes p and q with $p<q$.

If n were even, by inspection, $M_4$ is divisible by 3 and 5 but the odd case is harder.

I know that p being the first twin prime implies $p \equiv_6 -1$

The textbook hints that 2 is a quadratic residue modulo p and modulo q but I don't see how this follows. I know this is the case only if p and q are congruent to +-1 modulo 8 or alternatively if $2^{p-1\over{2}}$ is congruent to 1 modulo p. I can't get there.

Can anyone give me a hint in this direction.



It is known that for any natural number $n$ and for any prime $p$, $ord_p(n)$ divides $p-1$, as seen here.

Using this, it is safe to say $ord_p(2)|p-1$ and $ord_q(2)|q-1$.

In your problem, for such odd $n$ to exist, $lcm(ord_p(2),ord_q(2))$ must divide $n$. This implies that $lcm(ord_p(2),ord_q(2))$ must be odd, or that both $ord_p(2)$ and $ord_q(2)$ are odd.

I suggest you continue from here.

  • $\begingroup$ The lcm stuff seems extraneous. $2^n \equiv_n 1$ implies $ord_p 2 | n$ implies $ord_p 2$ is odd since an even number cannot divide an odd integer. I think this will be helpful. I'll continue in this direction. Thank you. $\endgroup$ – topoquestion Jan 18 '16 at 12:01
  • $\begingroup$ ok, this also produces the other result. Since $ord_p 2$ is odd, $ord_p 2 | p-1$ implies $ord_p 2 | 2( p-1\2 )$ implies $ord_p 2 | (p-1)\2 $ implies $2^(p-1/2) \equiv_p 1$ so that 2 is a quadratic residue by Euler's Criterion $\endgroup$ – topoquestion Jan 18 '16 at 14:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.