BIGtheme.net http://bigtheme.net/ecommerce/opencart OpenCart Templates
Friday , July 28 2017
Home / Elementary Number Theory / There are an infinite number of primes of the form 4n + 3.

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

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 q1, q2,…,qs Consider the positive integer N = 4 (q1, q2,…,qs – 1) + 3

and let N = r1r2…rt be its prime factorization. Because N is an odd integer we have rk ≠ 2 for all k, so that each rk 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 ri of the form 4n + 3. But ri cannot be found among the listing q1, q2,…,qs for this would lead to the contradiction that ri\1. The only possible conclusion is that there are infinitely many primes of the form 4n + 3. (Proved).

## Theorem: If 2p – 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,

2p – 1 = 2ab – 1

= (2a)b – 1

= xb – 1 , where x = 2a

= (x – 1) (xb –1 + xb – 2 + …+1)

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

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

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

## Application of Euclidian’s algorithm in Diophantine equation

Problem-1: Which of the following Diophantine equations cannot be solved –   a) 6x + ...