# Prime congruence

If $p\equiv3\pmod{4}$ and $q=2p+1$ is a prime then $q|(2^p-1)$ if $2^p-1$ is composite.

Also, prove that there are infinitely many primes $p$ for which $2^p-1$ is composite.

-
please read in place of multiple, 2^p -1 is composite – mahima Naidu Sep 17 '11 at 8:32
Can you state your question in the form of a question? – Fixee Sep 18 '11 at 6:15

Unfortunately it is not known whether there are infinitely many primes $p$ such that $2^p-1$ is composite!

This is quite amazing, since primes $p$ for which $2^p-1$ is prime seem to be, in fact, very scarce. On the numerical evidence, "almost every" number of the form $2^p-1$, where $p$ is prime, is composite.

The Great Internet Mersenne Prime Search (GIMPS) has found some primes of the form $2^p-1$, but not many. Each new prime of this form is deemed newsworthy. (It is also not known whether there are infinitely many primes such that $2^p-1$ is prime, but that is much less surprising.)

It is true that if $p \equiv 3 \pmod{4}$, and $q=2p+1$ is prime, then $2^p-1$ is divisible by $q$. But it is not known whether there are infinitely many primes $p$ such that $2p+1$ is prime. This is connected to the unsolved problems of whether there are infinitely many Sophie Germain primes, or "safe" primes.

There are many other plausible conjectures, which have strong empirical and theoretical support, that imply that there are infinitely many composites of the shape $2^p-1$, where $p$ is prime. So far, none of these conjectures has been proved.

Finally, we give a proof of the divisibility result mentioned in the post.

Theorem: (a) If $p\equiv 3\pmod{4}$, and $q=2p+1$ is prime, then $q$ divides $2^p-1$. (b) If in addition $p \ne 3$, then $2^p-1$ is not prime.

Proof: (a) If $p$ is of the form $4k+3$, then $q$ is of the form $8k+7$. By a standard result, $2$ is a quadratic residue of $q$. It follows by Euler's Criterion that $2^{(q-1)/2} \equiv 1 \pmod q$. Thus $q$ is a divisor of $2^p-1$.

Another way: We do not need to use Euler's Criterion. For by Fermat's (little) Theorem, $2^{q-1}\equiv 1 \pmod{q}$. Thus $q$ divides $2^{2p}-1$, and therefore $q$ divides $(2^p-1)(2^p+1)$. We now show that $q$ cannot divide $2^p+1$.

If $q$ divides $2^p+1$, then since $2$ is a quadratic residue of $q$, it follows that $-1$ is a quadratic residue of $q$. This is impossible, since it is well-known that $-1$ is not a quadratic residue of any prime congruent to $3$ modulo $4$.

(b) We show that if $p\ne 3$, then $q$ is a proper divisor of $2^p-1$. The only way that $q$ can fail to be a proper divisor is if $q=2p+1=2^p-1$. This can only happen at $p=3$, because if $p>3$, then $2^p-1>2p+1$.

-