Monday, May 09, 2005

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 = 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

13 comments :

Susan said...

I am writing a paper on Euclid's other than his geometry contributions. From the research I have done so far I have found the following contributions:
Number theory books 7,8,9 and proportional theory book 5, Elements of Music. Do you have other examples of contributions I can research. You seem to be a vast of knowledge!

Larry Freeman said...

Hi Susan,

Here's a link that shows many of his other works:
http://en.wikipedia.org/wiki/Euclid

-Larry

Anonymous said...

I really do hate to be the devils advocate here, but your statement of the theorem indicates that EVERY integer is a product of a unique set of primes. Yet your proof only shows that numbers greater than 1 are products of a unique set of primes. How do you deal with the integer 1?

Larry Freeman said...

Great question. The proof does not relate to 1. 1 is the only positive integer that is not composed of primes.

In fact, we routinely say gcd(2,3)=1 to show that there is no common prime between two numbers.

So, to be more accurate, all integers greater than 1 are composed of a unique set of primes.

-Larry

P. B. said...

I believe you have a typo under Theorem 1: Case II: (5)(a)

It reads:
a = BC + D

and I believe it's meant to read:
a = bC + D

Not a huge deal, but it gave me a bit of a pause when I was reading over it.

I'm enjoying your Fermat Blog and look forward to perusing this one more as well.

Thanks for your efforts,
-Pat

Larry Freeman said...

Hi Pat,

Thanks very much for noticing that! :-)

I've fixed the typo.

Cheers,

-Larry

Scouse Rob said...

In Lemma 2 (5) a 'd' appears, which I think should be a 'b'.

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

Rob

Larry Freeman said...

Hi Scouse Rob,

Thanks for noticing. It's now been fixed.

-Larry

Gustolandia said...

Hi. b>0 is in need on the first proof.

Larry Freeman said...

Hi Gustolandia,

b > 0 doesn't need to be proved because c can be negative.

In that case, a - bc is still >= 0 even when b is negative.

-Larry

2j5k said...
This comment has been removed by the author.
2j5k said...
This comment has been removed by the author.
2j5k said...

Hi Mr Freeman,

Theorem 1: Division Algorithm for Integers
(4e)

But if b is negative, then a - b(c+1) = d - b is more than d, isn't it?

-----------------
(5b)

d - D should be D - d.

----------------
(5d)

Is it better to write 0 < D - d < b instead? Otherwise, D - d could be kb where k is a negative integer.

And maybe also include d < D in (5a) to make 0 < D - d in (5d) more obvious?