Fundamental Theorem of Arithmetic

Introduction to Fundamental Theorem of Arithmetic
The fundamental theorem of arithmetic is If (1) p1, p2, p3… pn and q1, q2, q3… qm are primes (both groups written in order of increasing size) and if (2) p1p2p3…pn = q1q2q3…qm, then p1 = q1, p2 = q2 … pn = qm and hence m = n. The Fundamental Theorem of Arithmetic is also called the "unique factorization theorem."  The following example is the fundamental theorem of arithmetic

Example:

3468 = 22 · 3 · 172   or   600 = 23 · 3 · 52

Fundamental Theorem of Arithmetic - Proof

It would be reasonable to prove first that p1 = q1.

Now p1 is a divisor of the product of all the ps (call it N) so it must be a divisor of the product of all the qs (which is also N).

If we knew that this forces p1 to divide at least one of the qs, we could then reason like this: Since p1 divides one of the qs, and since the qs are prime, so p1 must equal the q that it divides.

q1 is the smallest of the qs, so p1 = q1. Identical reasoning about q1 shows that q1 = p1. Thus p1 is equal to q1. So, replacing q1 with p1 in q1q2q3…qm, we get p1p2p3…pn = p1q2q3…qm.

Dividing both sides by p1 we get p2p3…pn = q2q3…qm. This new equation has one less prime on each side.

The same kind of reasoning that proved p1 = q1 also shows that p2 = q2. Step by step we peel away the primes from each side, establishing that pk = qk for all values of k.

Since every p pairs off with one q and vice versa, we see that m = n (the number of ps = the number of qs).

The problem is that we don't know that whenever a prime divides the product of several natural numbers it must divide at least one of them.

Fundamental Theorem of Arithmetic - Examples

Example 1:

216 = 2. 108= 2.2.54 = 2.2.2.27 =2.2.2.3.9 = 2.2.2.3.3.3

That is,

216 = 23. 33

Example 2:

26624 = 8.3328 = 8.8.416 = 8.8.8.52 = 8.8.8.2.26 = 8.8.8.2.2.13

That is

8.8.8.2.2.13 = 83.22.13