Blogs, Proofs

Fundamental Theorem of Arithmetic

Every time I read the name of that theorem, I get an idea of a grand majestic theorem that is of the utmost importance. While, it is quite the large claim, this theorem really is extremely important in a lot of what we do in when considering multiplication of natural numbers. However, the name of the theorem could be a little less majestic and a little more descriptive. Therefore, we will state the theorem.

Fundamental Theorem of Arithmetic

Every natural number other than 1 can be written uniquely (up to a reordering) as the product of prime numbers.

Therefore, what this says is just that we can factor any natural number into a product of primes, and this can be done in only one way. To show an example of this, suppose that we are given the number 212. Then we can factor 212 in the following ways,

Here we have created a factor tree.  The factors we used for each step in the two different techniques were different, however, if we look only at the terminal numbers of the tree, we have exactly the same numbers, just rearranged.  The fundamental theorem states that for any number, this will always be the case.

It is possible to give such a factorization

The first part of the theorem that we will have to show is that such a factorization is always possible.  Using the above example, we can follow the procedure of,

  1. Let n be a natural number,
  2. If n cannot be factored using numbers other than n and 1, we are done.
  3. Otherwise, write n=ab where \(2 \leq a < n\) and \(2 \leq b < n\).
  4. Repeat steps 2 and 3 for a and b until you have arrived at all terms that are prime.

The important point to see here is that in each case we will be making a tree as we did above.  Therefore, we would have to repeat steps 2 and 3 for each of the factors of the numbers, then each of the factors of these numbers and so on.  In order to show that this will indeed give us a factorization, we would then have to show that such a process much eventually stop.

To show that this process must stop, instead suppose that it didn’t.  Then we would continue on forever finding factors.  However, each factor is strictly smaller than the preceding term.  Therefore each step will subtract at least one from the previous term.  Since we started at the natural number \(n\), if we subtracted one forever, we would eventually end up with negative numbers.  However this contradicts the fact that each term in the factorization is greater than or equal to 2.

While some of the details above are a little vague, we can still see that we could find such a factorization.  In order to give a more formal proof, we would do the following

  • Note \(n=2\) is already written as the product of primes.
  • Suppose that you can factor all natural numbers \(k\) with \(2 \leq k \leq n-1\) into a product of primes.
  • Now, look at \(n\).  If \(n\) cannot be factored, it is prime so we are done.
  • If \(n\) can be factored, do so as \(n=ab\).  Note \(2 \leq a < n\) and \(2 \leq b < n\), so by the induction hypothesis \(a\) and \(b\) can be written as the product of primes.
  • If we multiply the factorization of \(a\) by the factorization of \(b\) we get a factorization of \(n\).

Here we have shown that since \(2\) can be factored, \(3\) can as well.  Since both of these can be, \(4\) can also be factored.  If we continue in this manner, we will indeed get that every natural number can be factored.  This is indeed what we would call a proof by strong induction, and the nice thing about this proof is the it is a very good example of when we would need to use strong induction.  While induction proofs are regularly shown, it is hard to come up with an example that doesn’t seem completely arbitrary that requires the assumption of more than one prior term.

Unique Factorization

We have shown that a factorization into primes of any natural number is possible, so all we have left to do is show that this factorization is unique up to a reordering.  For this part, we have to show that if \(a\) can be factored as \(a=p_{1} \cdots p_{n}=q_{1} \cdots q_{m}\), then \(p_{i}=q_{j}\) for some \(i\) and \(j\) and \(n=m\).  In order to do this, we again use induction, this time on the number of terms in the first factorization \(n\).

  • Suppose \(a=p_{1}=q_{1}q_{2}\cdots q_{m}\).  Since \(p_{1}\) is prime, we must have that \(m=1\) and \(q_{1}=p_{1}\), hence the theorem holds.
  • Now assume the theorem is true for \(n-1\) terms and prove for \(n\).
  • Let \(a=p_{1} \cdots p_{n}=q_{1} \cdots q_{m}\).
  • Note that \(p_{n}\) is prime and divides \(q_{1} \cdots q_{m}\)
  • We showed in Those are some prime irreducibles that \(p_{n}\) must therefore divide a \(q_{i}\) for some \(i\).
  • Since \(q_{i}\) is prime and \(p_{n} \neq 1\), this implies \(p_{n}=q_{i}\).
  • Now, we have that \(p_{1} \cdots p_{n-1}=q_{1} \cdots q_{i-1}q_{i+1} \cdots q_{m}\).
  • Therefore, by the induction hypothesis \(m-1=n-1\) and the terms are the same up to a reordering.
  • Hence, we will have a unique factorization of any natural number.

Conclusion

The proof we’ve used here is indeed a wonderful example of both weak and strong induction, thus making this a wonderful way to explore the idea of an induction proof with meaningful results.  This result is meaningful, because we now know that, regardless of how we are to factor a number, if we continue until we have the product of primes, we will always arrive at the same factorization.  When working with things like least common multiples and greatest common divisor, or things like combining fractions with a common divisor, this is extremely useful.  If the order we factored in mattered, then we really could get some strange results.  As in the other proofs we’ve been looking at, we again have a theorem that both gives a wonderful result and wonderful example of technique that we can use in proofs.

I hope you’re enjoying these proofs and learning something along the way.  If you are, let me know by liking the post or sharing it on Social Media.  If you have questions, or comments please let me know below.

 

 

2 thoughts on “Fundamental Theorem of Arithmetic”

We'd love to hear your thoughts!

This site uses Akismet to reduce spam. Learn how your comment data is processed.