# Mersenne number divisible by twin primes

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.
• 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. – topoquestion Jan 18 '16 at 12:01
• 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 – topoquestion Jan 18 '16 at 14:12