# Blog Archives

## Infinite number of primes :)

In today’s post , I will present a very well known proof. What makes this proof especially appealing is that it is not too complex. Even so, it is very **powerful.** This theorem was first presented in Euclid’s Elements (Book IX, Proposition 20).

Theorem: **There are an infinite number of primes.**

Proof:

(1) Assume that there is only a finite number of primes.

(2) Then, there exists a prime p_{n} that is the largest prime.

(3) Let p_{1}, p_{2}, …, p_{n} be the list of all primes that exist.

(4) Let x = p_{1}*p_{2}*…*p_{n} + 1.

(5) By the fundamental theorem of arithmetic (see Theorem 3, here), we know there is at least one prime that divides x. Let us call this prime p*.

(6) But none of the primes p_{1} … p_{n} divide x since x ≡ 1 (mod p_{i}) for any of the primes p_{1} … p_{n}

(7) Therefore, we have a contradiction. We have a prime p* that is not in the complete list of primes.

(8) So, we reject our assumption in step#1 and conclude that there are an infinite number of primes that exist.

QED

## Fundamental Theorem Of Arithmetic

Before, we can provide this theorem, we will need an initial theorem on division and one lemma which will we borrow from Euclid.

Theorem 1: Division Algorithm for Integers

This theorem shows that given any two integers, there exist a unique divisor and a unique remainder.

(1) Let S be a set such that { a – bc : c is an integer and a-bc ≥ 0}

(2) S is not empty.

Case I: b divides a

In this case, then there exists a c where a – bc = 0. Therefore, 0 is an element of this set.

Case II: b doesn’t divide a

In this case, there exists an c where a – bc has a remainder is greater than 0. This remainder is then an element of this set.

(3) Then, then there exists d such that d is the smallest element of the set. [Well Ordering Principle]

(4) We know that d is less than **b**.

(a) Assume that d is greater than or equal to b.

(b) Then d – b is greater than or equal to 0.

(c) Since

d – b = (a – bc) – b = a – bc – b = a – b(c+1)

(d) We conclude that a – b(c+1) must be an element of S.

(e) But a – b(c+1) is less than **d**

(f) Which is a contradiction since d is the smallest element from step #3.

(5) Finally, for any a,b, the lowest value d and the remainder c are unique.

(a) Assume C,D are integers that can be derived from a,b.

a = bc + d, d is greater than 0 and less than b.

a = bC + D, D is greater than 0 and less than b.

(b) So

bc + d = bC + D –> b(c – C) = d – D

(c) Which means that b divides (d – D).

(d) Since d – D is less than **b**, we know d – D = 0 and that d = D.

(e) Which gives us b(c – C) = 0 or that c – C = 0.

(f) We can therefore conclude that c = C.

QED

Lemma 2: Euclid’s Lemma

This lemma shows that given a prime that divides a product, either it divides one value or it divides the other.

(1) Let’s assume a prime p divides a product ab.

(2) Let’s assume that p does not divide a.

(3) Then gcd(p,a)=1. [See blog on Greatest Common Denominators for details]

(4) There exists s,t such that 1 = as + pt. [See blog on Greatest Common Denominators]

(5) Multiplying both sides with b gives us:

b(1) = b(as + pt) = b = abs + ptb

(6) Since p divides ab, there exists k such that ab = pk.

(7) Combining with (5), we get

b = pks + ptd = p(ks + td).

QED

We can also tag on a corollary.

Corollary 2.1: Generalized Euclid’s Lemma

The idea here is that if a prime divides a product of n elements, then it is necessarily divides at least one of those elements.

(1) Let’s assume that we have a product of n elements.

a = a_{1} * a_{2} * … * a_{n}

(2) We can take any one of these elements and get:

a = a_{1} * (a_{2} * … * a_{n})

(3)So, by Euclid’s Lemma (see Lemma 2 above), the prime either divides a_{1} or one of the rest of the elements.

(4) So, either it divides a_{1} or a_{2} etc.

(5) And we get to the last two elements, we are done by Euclid’s Lemma.

QED

Theorem 3: Fundamental Theorem of Arithmetic

This theorem proves that each integer greater than 1 is the product of a unique set of primes.

(1) Let S be a set S of {primes or products of primes > 1}.

(2) 2 is an element of S since 2 is prime.

(3) From (1), (2) there exists a value n which is 3 or greater where all values less than n and greater or equal to 2 are in S.

(4) If n is a prime, then it is a member of S.

(5) If n is not a prime, then it is also a member of S.

(a) If n is not a prime, then there exist a,b such that n=ab where **a,b** are greater than **1** and less than **n**. [Definition of a prime]

(b) But a,b must be elements of S since they are less than n. [From step #3 above]

(c) Then, n must also be a member of S since n is a product of two numbers which are either primes or products of primes.

(6) Now, all the primes that make up n are necessarily unique.

(a) Let **n = p _{1} * p_{2} * … p_{r} = q_{1} * q_{2} * … q_{s}** where p,q are all primes.

(b) Let’s start with **p _{1}**

(c) Either **p _{1}** divides

**q**or

_{1}**q**or someother value. [see Euclid’s Generalized Lemma above]

_{2}(d) Likewise, each value **p _{r}** can be matched by some value

**q**.

_{s}(e) In other words, they must necessarily be the same combination.

QED