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 = a1 * a2 * ... * an
(2) We can take any one of these elements and get:
a = a1 * (a2 * ... * an)
(3)So, by Euclid's Lemma (see Lemma 2 above), the prime either divides a1 or one of the rest of the elements.
(4) So, either it divides a1 or a2 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 = p1 * p2 * ... pr = q1 * q2 * ... qs where p,q are all primes.
(b) Let's start with p1
(c) Either p1 divides q1 or q2 or someother value. [see Euclid's Generalized Lemma above]
(d) Likewise, each value pr can be matched by some value qs.
(e) In other words, they must necessarily be the same combination.
QED
