law of quadratic residue

**mndi1105** · November 9th 2008, 09:22 AM

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.

**ThePerfectHacker** · November 9th 2008, 09:53 AM

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

Thread: law of quadratic residue

LinkBack

Thread Tools

Display

law of quadratic residue

Similar Math Help Forum Discussions

When is 2 a quadratic residue?

Quadratic residue mod 2^r

Quadratic residue -5

Quadratic Residue

quadratic non residue

Search Tags