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.


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).


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.


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.



About shivang1729

I am a young student who loves math . I like number theory and inequalities part the most , and preparing for Math Olympiads :)

Posted on Tuesday,February 14, 2012, in Fundamental Theorem Of Arthimetic and tagged , , , , , . Bookmark the permalink. 3 Comments.

  1. Reblogged this on Fundamental maths Concepts and commented:


  2. WOW just whaat I wass searching for. Came here by searching ffor bed
    linens etc

  1. Pingback: Infinite number of primes :) « Fundamental maths Concepts

Comments / doubts/answers here:

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: