let p and q be prime numbers with p=3 mod 4 and q=2p + 1. Prove that 2^p -1 is a Mersenne prime if and only if p=3.

Printable View

- Nov 9th 2008, 09:22 AMmndi1105law of quadratic residue
let p and q be prime numbers with p=3 mod 4 and q=2p + 1. Prove that 2^p -1 is a Mersenne prime if and only if p=3.

- Nov 9th 2008, 09:53 AMThePerfectHacker
Since $\displaystyle p=4k+3$ it means $\displaystyle q=2(4k+3)+1 = 8k+7$ thus $\displaystyle q\equiv 7(\bmod 8)$. Therefore, $\displaystyle 2$ is a quadradic residue modulo $\displaystyle q$. Thus, there is a solution to $\displaystyle x^2 \equiv 2(\bmod q)$. Therefore, $\displaystyle 2^p = 2^{(q-1)/2} \equiv \left( x^2 \right)^{(q-1)/2} \equiv x^{q-1} \equiv 1(\bmod q)$. Therefore, we see that $\displaystyle q$ divides $\displaystyle 2^p - 1$. However, $\displaystyle 2^p-1$ can still be prime if $\displaystyle 2^p - 1 = q$. However, if $\displaystyle p>3$ then $\displaystyle 2^p - 1 > 2p+1 = q$ which would mean that $\displaystyle 2^p-1$ is not prime. The only way, therefore, for it to be prime is when $\displaystyle p=3$.