Briana H.

asked • 12/07/12# Let p > 3 be a prime, and suppose that p = 3 (mod 4). If q = 2p+1 is also prime show that (2^p) -1 is never prime.

Need help with this promblem for number theory

## 1 Expert Answer

Roman C. answered • 12/08/12

Masters of Education Graduate with Mathematics Expertise

First of all, a well known theorem:

If p is a prime, and x^{2 }≡ y^{2} mod p, then either x ≡ y mod p or x ≡ -y mod p.

This can be seen as follows using Euclid's Lemma:

x^{2} ≡ y^{2} mod p

x^{2} - y^{2} ≡ 0 mod p

(x-y)(x+y) ≡ 0 mod p

x-y ≡ 0 mod p or x+y ≡ 0 mod p

x ≡ y mod p or x ≡ -y mod p

Now we can calculate as follows given 2p+1 is also prime.

2^{2p} ≡ 1 mod (2p+1)

2^{p }≡ 1 mod (2p+1) or -1 mod (2p+1)

Assume that 2^{p} ≡ -1 mod (2p+1). Then

2^{p-1} ≡ p mod (2p+1).

Because p-1 is even, this says that p is a quadratic residue modulo 2p+1.

Note that there is no good way to type in legendre symbol But I will write (^{a}/_{p}).

By quadratic reciprocity theorem, (^{p}/_{2p+1})(^{2p+1}/_{p}) = (-1)^{(}^{2p+1-1)(p-1)/4} = (-1)^{p(p-1)/2}

which is -1 when p ≡ 3 mod 4 which is the case in this problem.

Thus (^{p}/_{2p+1}) = -(^{2p+1}/_{p}) = -(^{1}/_{p}) = -1.

So p is a quadratic nonresidue mod (2p+1) which means that 2^{p }≠ -1 mod (2p+1).

The only conclusion is that 2^{p} ≡ 1 mod (2p+1). Thus (2p+1) | (2^{p}-1). Since for p>3, 2p+1 < 2^{p}-1, we get that 2^{p}-1 is composite.

## Still looking for help? Get the right answer, fast.

Get a free answer to a quick problem.

Most questions answered within 4 hours.

#### OR

Choose an expert and meet online. No packages or subscriptions, pay only for the time you need.

Roman C.

I will try to figure this out for you. But my analysis of small cases suggests that p doesn't need to be prime.

As long as p = 3 mod 4 and q=2p+1 is prime, q will be a factor of 2

^{p}-1. Proving this would prove the conjecture because 2p+1 < 2^{p}-1 when p>3.12/07/12