BIGtheme.net http://bigtheme.net/ecommerce/opencart OpenCart Templates
Saturday , July 22 2017
Home / Elementary Number Theory / Theorem of Euclid’s on prime number on prime number

# Theorem of Euclid’s on prime number on prime number

### Theorem of Euclid’s on prime number : There are an infinite number of primes.

Proof: Euclid’s proof is by contradiction let p1 = 2, p2 = 3, p3 = 5, p4 = 7, … be the primes in according order and suppose that there is a least prime called pn. Now consider the positive integer P = p1 p2p3…pn + 1.

Since P 1, we conclude that P is a divisible by some prime p. But p1 p2p3…pn are the only prime numbers, so that p must be equal to one of p1 p2p3…pn combining the relation, p\p1 p2p3…pn with p\ P, we arrive p \ P – p1 p2p3…pn or, equivalently, p\1. The only positive of the integer 1 is 1 itself, and because p > 1, a contradiction arises. Thus, no finite list of primes is complete, whence the number of primes is infinite. (Proved)

Problem: The only prime of the form n3 – 1 is 7.

Proof: Given that, n3 – 1= n3 – 13 = (n – 1) (n2 + n + 1)

We know if n is an integer, n – 1 is an integer and n2 + n + 1 is also an integer.

Thus (n – 1) (n2 + n + 1) = ab for integers and a/b.

If ab is prime, either a or b must be 1(or else we would have more than one factors).

Thus either n -1 = 1 or (n2 + n + 1) = 1. If the first is true then n = 2

∴ n3 – 1 = 7

If the 2nd is true then n = 0 and n = – 1. So, we test for n = 0, n = – 1, and n = 2.

When n = 0, then n3 – 1 = – 1 is not prime.

When n = – 1 then n3 – 1 = (– 1)3 – 1 = – 1 – 1 = – 2, is not prime.

When n = 2 then n3 – 1 = 8 – 1 = 7.

∴ The only prime of the form n3 – 1 is 7. (Proved).

### Theorem: If pn is the nth prime number, then pn ≤ 22^n-1

Proof: Let us proceed by induction on n, the asserted inequality being clearly true when n = 1. As the hypothesis of the induction, we assume that n > 1 and that the result holds for all integers up to n. Then

pn +1 ≤ p1p2…pn + 1

≤ 2.22…(22^(n-1))+1 = 21 + 2 + 2^2+…+2^(n-1)+1

Recalling the identity 1 + 2 + 2 2 + …+ 2n-1 = 2n – 1 , we obtain

pn +1 ≤ 22^n -1+1

However, 1 ≤ 22^n-1 for all n, whence

Pn+1 ≤ 22^n-1+22^n-1 = 2.22^n-1 = 22^n.

Hence, Completing the induction step and the argument. (Proved)

## Application of Euclidian’s algorithm in Diophantine equation

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