Baby Steps for Adults Around the Fundamental Theorem of Arithmetic

What School Did Not Teach About Natural Numbers

Introduction

This blog post revolves around an epiphany I should have had when I was closer to nine years old than to fifty-nine years old. It may be that the circumstances are unique to myself, and that everybody else on the planet just thinks Iʼm stupid, but despite studying applied maths at undergraduate level I was never taught any of this. The idea hit me laying in bed one night, and I looked it up subsequently and read up on introductory number theory (reference at the end).

Everything in this post goes over the set of natural numbers, \(N = \{1,2,3,\ldots\},\) together with the the standard addition and multiplication operations.

The Epiphany

I remember at school being told to stare at \(3/6\) and conclude somehow that it is equivalent to \(1/2,\) or stare at \(6\) and \(12\) and conclude that the greatest common divisor (GCD; also known as the greatest common factor), is \(6.\) This is great as an exercise of the memory of multiplication tables, and for separating out the promising kids from the rest. But we were never told the underlying reasoning behind any of this, nor indeed how to solve harder problems like \(18/24.\)

The truth is that numbers are like molecules: they are built up of unique combinations of indivisible parts. We can think of a number like \(6\) and immediately see that this can be factored as \(2 \times 3,\) whereas we can think as long as we like about the number \(7\) and know that we will never find factors of it: it is an indivisible, or prime, number.

Now take the numbers \(18\) and \(24\) as examples of prime factorization. $$18 = 2 \times 9 = 2 \times 3 \times 3 ,$$ and $$24 = 2 \times 12 = 2 \times 2 \times 6 = 2 \times 2 \times 2 \times 3 .$$

And so we can compute $$\begin{align} \frac{18}{24} &= \frac {2 \times 3 \times 3} {2 \times 2 \times 2 \times 3} \\ &= \frac {\cancel{2} \times \cancel{3} \times 3} {\cancel{2} \times 2 \times 2 \times \cancel{3}} \\ &= \frac {3} {2 \times 2} \\ &= \frac {3} {4} .\end{align} $$

Why did they never tell us that at school? Or did I miss a day, or was I ill that day? If Iʼd known this my future life would have been somewhat easier.

And then we see, writing \((a,b)\) to denote the GCD (greatest common divisor) of \(a\) and \(b,\) $$\begin{align}(18,24) &= (2 \times 3 \times 3, 2 \times 2 \times 2 \times 3) \\ &= (\underline{2} \times \underline{3} \times 3, \underline{2} \times 2 \times 2 \times \underline{3}) \\ &= 2 \times 3 = 6 ;\end{align}$$ wherein we keep only the common prime factors, instead of discarding them and keeping the others.

And then returning to the fraction simplification problem we observe $$ \frac{18}{24} = \frac{3 \times 6}{4 \times 6} = \frac{3 \times \cancel{6}}{4 \times \cancel{6}} = \frac{3}{4}$$ as before. Everything makes sense now!

We then notice that \(6\) is not only the GCD of \(18\) and \(24,\) but is also the difference. This is not entirely a coincidence. Consider two numbers \(a\) and \(b,\) with \(a>b\) without loss of generality, and suppose they have the GCD \(c\) so that \(a=ca'\) and \(b =cb'.\) Then $$a-b = ca'-cb'=c(a'-b')$$ and we see immediately that the difference of two numbers is always some positive integer multiple of their GCD, which will always be less than or equal to the difference.

So we see that the GCD can never be more than the difference, though may be less. And then we get to thinking that if the difference between two numbers is \(1,\) there can be no common divisor!

Wait, let us say that again, another way. Consecutive numbers cannot have any prime factors in common. What? That canʼt be right, can it? Observe the table at right, and see that it is true for the first \(23\) numbers at least! I never knew that!

Corollary: there are an infinite number of prime numbers.

To see this, suppose there are \(n\) primes, \(p_1, \ldots, p_n.\) Now form the number $$p_1 p_2 \ldots p_n + 1 ;$$ by the statement above, this number cannot be a product of any of the \(n\) primes, therefore it is either a new prime, or has factors outside the set \(\{p_i\}.\) Either way, this is a contradiction to there being only \(n\) primes. However big \(n\) is, we can always find at least one more prime using this method. There must, therefore, be an infinity of them.

Now, before we leave, we must kick an elephant out of the room. We started this all off by saying numbers are like molecules each made with a unique collection of indivisible parts. But is this true? It is clear that we can always find a prime factorization just by taking a number and dividing it down until we can go no further. But is the factorization unique? If we perform the divisions in a different order, might we end up with a different factorization? The answer is in fact no, for suppose a number \(a\) has two different prime decompositions, $$\begin{aligned} a &= p_1 p_2 \ldots p_n \\ &= q_1 q_2 \ldots q_m\end{aligned}$$ Now arrange the primes so that equal ones are at the start of each list, $$\begin{aligned} a &= p_{1'} \, p_{2'} \ldots p_{n'} \, p_{1''} \, p_{2''} \ldots p_{n''} \\ &= q_{1'} \, q_{2'} \ldots q_{m'} \, q_{1''} \, q_{2''} \ldots q_{m''}\end{aligned}$$ where each \(p_{i'} = q_{i'}\) and every \(p_{i''}\) is different to every \(q_{j''}.\) Then the number $$\begin{aligned} a' = \frac{a}{p_{1'} \, p_{2'} \ldots } &= p_{1''} \, p_{2''} \ldots p_{n''} \\ &= q_{1''} \, q_{2''} \ldots q_{m''}\end{aligned} .$$ But this is ridiculous, as the top line says that \(a'\) definitely is divisible by \(p_{1''},\) while the bottom line says \(a'\) is definitely not divisible by \(p_{1''}\) since this does not appear amongst the list of primes \(q_{i''}\) (and cannot be a factor of any of them as they are all indivisible). So we have a contradiction and this proves that the prime decomposition of a number must be unique. This is the Fundamental Theorem of Arithmetic.

Reference

The classic university-level introductory textbook is Tom M. Apostol, Introduction to Analytic Number Theory, 1976. The substance of this blog post is contained within Chapter 1 (out of 14; they get quite advanced) of that book, the bulk of which pertains to the Prime Number Theorem, which has never actually been solved.