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.

Question

Need help with this promblem for number theory

Answer 1

First of all, a well known theorem:

If p is a prime, and x² ≡ y² mod p, then either x ≡ y mod p or x ≡ -y mod p.

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

x² ≡ y² mod p

x² - y² ≡ 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) = -(¹/_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.