law of quadratic residue

Printable View

• November 9th 2008, 09:22 AM
mndi1105
law 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.
• November 9th 2008, 09:53 AM
ThePerfectHacker
Quote:

Originally Posted by mndi1105
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.

Since $p=4k+3$ it means $q=2(4k+3)+1 = 8k+7$ thus $q\equiv 7(\bmod 8)$. Therefore, $2$ is a quadradic residue modulo $q$. Thus, there is a solution to $x^2 \equiv 2(\bmod q)$. Therefore, $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 $q$ divides $2^p - 1$. However, $2^p-1$ can still be prime if $2^p - 1 = q$. However, if $p>3$ then $2^p - 1 > 2p+1 = q$ which would mean that $2^p-1$ is not prime. The only way, therefore, for it to be prime is when $p=3$.