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:

**(3)So, by Euclid's Lemma (see Lemma 2 above), the prime either divides a**

a = a

a = a

_{1}* (a_{2}* ... * a_{n})_{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**where p,q are all primes.

_{1}* p_{2}* ... p_{r}= q_{1}* q_{2}* ... q_{s}(b) Let's start with

**p**

_{1}(c) Either

**p**divides

_{1}**q**or

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

_{2}(d) Likewise, each value

**p**can be matched by some value

_{r}**q**.

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

QED

## 13 comments :

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!

Hi Susan,

Here's a link that shows many of his other works:

http://en.wikipedia.org/wiki/Euclid

-Larry

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?

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

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

Hi Pat,

Thanks very much for noticing that! :-)

I've fixed the typo.

Cheers,

-Larry

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

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

Rob

Hi Scouse Rob,

Thanks for noticing. It's now been fixed.

-Larry

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

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

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?

Post a Comment