Why is the fundamental theorem of arithmetic a theorem?

The fundamental theorem of arithmetic states that every natural number can be factorized uniquely as a product of prime numbers. The word “uniquely” here means unique up to rearranging. The theorem means that if you and I take the same number $n$ and I write $n = p_1p_2\ldots p_k$ and you write $n = q_1q_2\ldots q_l$ where each $p_i$ and $q_i$ is a prime number, then in fact $k=l$ and we wrote the same prime numbers (but maybe in a different order).

Most people happily accept this theorem as self evident and believe it without proof. Indeed some people take it to be so self evident they feel it doesn’t really deserve the name “theorem” – hence the title of this blog post. In this post I want to highlight two situations where an analogous theorem fails.

Situation One: The Even Numbers

Imagine a world where everything comes in twos. In this world nobody knows of the number one or indeed any odd number. Their counting numbers are the even numbers $\mathbb{E} = \{2,4,6,8,\ldots\}$. People in this world can add numbers and multiply numbers just like we can. They can even talk about divisibility, for example $2$ divides $8$ since $8 = 4\cdot 2$. Note that things are already getting a bit strange in this world. Since there is no number one, numbers in this world do not divide themselves.

Once people can talk about divisibility, they can talk about prime numbers. A number is prime in this world if it is not divisible by any other number. For example $2$ is prime but as we saw $8$ is not prime. Surprisingly the number $6$ is also prime in this world. This is because there are no two even numbers that multiply together to make $6$.

If a number is not prime in this world, we can reduce it to a product of primes. This is because if $n$ is not prime, then there are two number $a$ and $b$ such that $n = ab$. Since $a$ and $b$ are both smaller than $n$, we can apply the same argument and recursively write $n$ as a product of primes.

Now we can ask whether or not the fundamental theorem of arthimetic holds in this world. Namely we want to know if their is a unique way to factorize each number in this world. To get an idea we can start with some small even numbers.

• $2$ is prime.
• $4 = 2 \cdot 2$ can be factorized uniquely.
• $6$ is prime.
• $8 = 2\cdot 2 \cdot 2$ can be factorized uniquely.
• $10$ is prime.
• $12 = 2 \cdot 6$ can be factorized uniquely.
• $14$ is prime.
• $16 = 2\cdot 2 \cdot 2 \cdot 2$ can be factorized uniquely.
• $18$ is prime.
• $20 = 2 \cdot 10$ can be factorized uniquely.

Thus it seems as though there might be some hope for this theorem. It at least holds for the first handful of numbers. Unfortunately we eventually get to $36$ and we have:

$36 = 2 \cdot 18$ and $36 = 6 \cdot 6$.

Thus there are two distinct ways of writing $36$ as a product of primes in this world and thus the fundamental theorem of arithmetic does not hold.

Situtation Two: A Number Ring

While the first example is fun and interesting, it is somewhat artificial. We are unlikely to encounter a situation where we only have the even numbers. It is however common and natural for mathematicians to be lead into certain worlds called number rings. We will see one example here and see what an effect the fundamental theorem of arithmetic can have.

Consider wanting to solve the equation $x^2+19=y^3$ where $x$ and $y$ are both integers. One way to try to solve this is by rewriting the equation as $(x+\sqrt{-19})(x-\sqrt{-19}) = y^3$. With this rewriting we have left the familiar world of the whole numbers and entered the number ring $\mathbb{Z}[\sqrt{-19}]$.

In $\mathbb{Z}[\sqrt{-19}]$ all numbers have the form $a + b \sqrt{-19}$, where $a$ and $b$ are integers. Addition of two such numbers is defined like so

$(a+b\sqrt{-19}) + (c + d \sqrt{-19}) = (a+c) + (b+d)\sqrt{-19}$.

Multiplication is define by using the distributive law and the fact that $\sqrt{-19}^2 = -19$. Thus

$(a+b\sqrt{-19})(c+d\sqrt{-19}) = (ac-19bd) + (ad+bc)\sqrt{-19}$.

Since we have multiplication we can talk about when a number in $\mathbb{Z}[\sqrt{-19}]$ divides another and hence define primes in $\mathbb{Z}[\sqrt{-19}]$. One can show that if $x^2 + 19 = y^3$, then $x+\sqrt{-19}$ and $x-\sqrt{-19}$ are coprime in $\mathbb{Z}[\sqrt{-19}]$ (see the references at the end of this post).

This means that there are no primes in $\mathbb{Z}[\sqrt{-19}]$ that divides both $x+\sqrt{-19}$ and $x-\sqrt{-19}$. If we assume that the fundamental theorem of arthimetic holds in $\mathbb{Z}[\sqrt{-19}]$, then this implies that $x+\sqrt{-19}$ must itself be a cube. This is because $(x+\sqrt{-19})(x-\sqrt{-19})=y^3$ is a cube and if two coprime numbers multiply to be a cube, then both of those coprime numbers must be cubes.

Thus we can conclude that there are integers $a$ and $b$ such that $x+\sqrt{-19} = (a+b\sqrt{-19})^3$. If we expand out this cube we can conclude that

$x+\sqrt{-19} = (a^3-57ab^2)+(3a^2b-19b^3)\sqrt{-19}$.

Thus in particular we have $1=3a^2b-19b^3=(3a^2-19b^2)b$. This implies that $b = \pm 1$ and $3a^2-19b^2=\pm 1$. Hence $b^2=1$ and $3a^2-19 = \pm 1$. Now if $3a^2 -19 =-1$, then $a^2=6$ – a contradiction. Similarly if $3a^2-19=1$, then $3a^2=20$ – another contradiction. Thus we can conclude there are no integer solutions to the equation $x^2+19=y^3$!

Unfortunately however, a bit of searching reveals that $18^2+19=343=7^3$. Thus simply assuming that that the ring $\mathbb{Z}[\sqrt{-19}]$ has unique factorization led us to incorrectly conclude that an equation had no solutions. The question of unique factorization in number rings such as $\mathbb{Z}[\sqrt{-19}]$ is a subtle and important one. Some of the flawed proofs of Fermat’s Last Theorem incorrectly assume that certain number rings have unique factorization – like we did above.

References

The lecturer David Smyth showed us that the even integers do not have unique factorization during a lecture of the great course MATH2222.

The example of $\mathbb{Z}[\sqrt{-19}]$ failing to have unique factorization and the consequences of this was shown in a lecture for a course on algebraic number theory by James Borger. In this class we followed the (freely available) textbook “Number Rings” by P. Stevenhagen. Problem 1.4 on page 8 is the example I used in this post. By viewing the textbook you can see a complete solution to the problem.