**Lemma: The product of two or more integers of the form 4n + 1 is of the same form.**

**Proof**: It is sufficient to consider the product of just two integers. Let us take k = 4n + 1 and k′ = 4m + 1. Multiplying these together, we obtain

kk′ = (4n + 1) (4m + 1) = 16 nm + 4n + 4m + 1 = 4(4 nm + n + m) + 1

let, 4 nm + n + m = n

So, kk′ = 4n + 1

*Which is of the desired form.*

### Theorem: There are an infinite number of primes of the form 4n + 3.

**Proof**: In anticipation of contradiction, let us assume that there exist only finitely many primes of the form 4n + 3; call them q_{1}, q_{2},…,q_{s} Consider the positive integer N = 4 (q_{1}, q_{2},…,q_{s} – 1) + 3

and let N = r_{1}r_{2}…r_{t} be its prime factorization. Because N is an odd integer we have r_{k} ≠ 2 for all k, so that each r_{k} is either of the form 4n + 1 or 4n + 3. By the lemma, the product of any number of primes of the form 4n + 1is again an integer of this type. For N to take the form 4n + 3, as it clear does, N must contain at least one prime factor r_{i} of the form 4n + 3. But r_{i} cannot be found among the listing q_{1}, q_{2},…,q_{s} for this would lead to the contradiction that r_{i}\1. The only possible conclusion is that there are infinitely many primes of the form 4n + 3. (Proved).

## Theorem: If 2^{p} – 1 is a prime, then p itself is a prime.

**Proof**: We prove the theorem by contradiction. Suppose that p is not a prime. Then p is composite and say p = ab,

2^{p} – 1 = 2^{ab} – 1

= (2^{a})^{b} – 1

= x^{b} – 1 , where x = 2^{a}

= (x – 1) (x^{b –1} + x^{b – 2} + …+1)

= (2^{a} – 1) {(2^{a})^{b – 1} + (2^{a})^{b – 2} +…+ 1}

This shows that 2^{p} – 1 is divisible by 2^{a} – 1 , where 1 < 2^{a} – 1 < 2^{p} – 1 .

*This contradicts the fact that 2 ^{p} – 1 is a prime. Hence p must be prime. (Proved)*