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₁ * a₂ * ... * a_n

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

a = a₁ * (a₂ * ... * a_n)

(3)So, by Euclid's Lemma (see Lemma 2 above), the prime either divides a₁ or one of the rest of the elements.

(4) So, either it divides a₁ or a₂ 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₁ * p₂ * ... p_r = q₁ * q₂ * ... q_s where p,q are all primes.

(b) Let's start with p₁

(c) Either p₁ divides q₁ or q₂ or someother value. [see Euclid's Generalized Lemma above]

(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