Why is the Fundamental Theorem of Arithmetic so important?

I've recently read about the Fundamental Theorem of Arithmetic and I think that I have just about understood the proof. What I found quite interesting at first was the "Fundamental" part in the name. I understand that my mathematical experience is nowhere near enough to fully appreciate this theorem, but can someone can explain to me why this theorem is so important? What would happen if this theorem wasn't actually true?

Thanks in advance!

• It serves as the basis for a lot of number theory and algebra, in some sense. – Cameron Williams Apr 30 '16 at 23:18
• Any natural number can be factorized into prime numbers, hence this theorem basically tells you that the prime numbers are the building blocks of all natural numbers. That is in itself a very nice insight. This decomposing into basic building blocks is something we like very much in mathematics. There are many generalisations, in some rings one wants to be able to decompose ideals into prime ideals (very useful in algebraic number theory). In representation theory one wants to decompose modules into indecomposable modules and so on. – Mathematician 42 Apr 30 '16 at 23:23
• Following on from @Mathematician42's answer, it tells us that the factorization into primes is unique. If nothing else, this has consequences in cryptography. I don't know much about cryptography, but I think something like the following gives a good mental image. Somebody can crack your code only by finding exactly the right numbers, no others will do. Also, your code is simplified by this fact, in a sense, since you don't need to account for multiple keys. – Will R Apr 30 '16 at 23:33
• @Superuser1189: Thank you, but I'm very sure that if you leave this question open for a bit longer, you'll get far better answers than the one I gave you. This theorem truly is fundamental. It can also be used to prove that there are infinitely many prime numbers (which is somewhat surprising, at first I thought you needed the existence of infinitely many primes to prove this theorem and not the other way round, but hey, there you go). – Mathematician 42 Apr 30 '16 at 23:34
• It's also somewhat funny that the building blocks (prime numbers here) are still not completely understood. There are so many conjectures surrounding prime numbers still open, such as the Goldbach conjecture, the twin prime conjecture and so on (which you probably believe when you try these). If I told you there were arbitrarily long arithmetic progressions in the prime numbers you probably wouldn't believe me, but Terence Tao and Ben Green showed that this is true. – Mathematician 42 Apr 30 '16 at 23:42

3 Answers

The fundamental theorem of arithmetic is important because it tells us something important and not immediately obvious about $\mathbb{Z}$ (the ring of the counting numbers together with those numbers multiplied by 0 or $-1$). Every nonzero number in $\mathbb{Z}$ can be uniquely factorized into primes without regard for order or multiplication by units.

It doesn't matter if you consider numbers like $-2$, $-3$, $-5$, $-7$, etc., to be prime or not. For example, $-2 = -1 \times 2 = 2 \times -1$, and we see that 2 is a positive prime and $-1$ is a unit, and it doesn't matter which one we present first. Accepting some negative numbers (specifically the positive primes multiplied by $-1$) as primes presents no philosophical problem to the fundamental theorem of arithmetic.

This is something that you must not take for granted when you step out to the larger world of algebraic integers. Consider for example $\mathbb{Z}[\sqrt{-5}]$, which consists of numbers of the form $a + b\sqrt{-5}$, where $a$ and $b$ are integers of the kind you're already familiar with. For now, take my word for it that $$21 = 3 \times 7 = (4 - \sqrt{-5})(4 + \sqrt{-5}) = (1 - 2\sqrt{-5})(1 + 2\sqrt{-5}).$$

Well, you can verify the equation with Wolfram Alpha, for example, put in (4 - Sqrt[-5])(4 + Sqrt[-5]). But for now you still have to take my word that the equation above does not contain any units, nor any non-obvious multiples of units.

This is the sort of thing that would happen in $\mathbb{Z}$ if the fundamental theorem of arithmetic was not actually true.

To help us make sense of integral domains like $\mathbb{Z}[\sqrt{-5}]$, we use a "norm" function that takes in a number from that domain and gives us a number in $\mathbb{Z}$. The norm function for $\mathbb{Z}[\sqrt{-5}]$ is $N(a + b\sqrt{-5}) = a^2 + 5b^2$. Thanks to the norm function, we can see that, for example, $1681 = (31 - 12\sqrt{-5})(31 + 12\sqrt{-5})$ is an incomplete factorization, because $(6 + \sqrt{-5})^2 = (31 + 12\sqrt{-5})$ (we just had to find a "smaller" number with a norm of 41).

The fact that $\mathbb{Z}$ has unique factorization (as shown by the fundamental theorem of arithmetic) allows us to prove things about numbers in other integral domains regardless of whether or not those other domains have unique factorization. And it turns out that of the infinitely many imaginary quadratic integer rings, only nine of them have unique factorization (clearly $\mathbb{Z}[\sqrt{-5}]$ is not one of them).

Let us also take a look at the frivolous theorem of arithmetic and the fundamental theorem of algebra.

The frivolous theorem of arithmetic tells us that almost all positive integers are very large. This is obvious, and therefore frivolous, because for any large positive integer that you can name, I can name a larger still positive integer just by adding 1, e.g., you say "googolplex", I say "googolplex plus 1".

The fundamental theorem of algebra tells us that every valid polynomial has as many roots as its degree. For example, $x^4 - 1$ is a polynomial of degree 4, and it has four roots, two of which you should be able to figure out yourself. The fundamental theorem of algebra seems like it should be obvious, yet its proof is quite lengthy and involved. But to appreciate its meaning and importance, you just need to understand imaginary and complex numbers.

• A not-frivolous theorem of arithmetic is that most positive integers are highly composite. For any k, let S(k) be the set of natural numbers with fewer than k distinct prime factors. The asymptotic density of S(k) is 0. – DanielWainfleet Aug 12 '18 at 3:34

For me, it's important because it tells you what numbers are made out of! It tells you that prime numbers are the "building blocks" of every number, and even better, this prime factorization is unique. So this tells you that a number just "is" a product of primes.

Aside from being pretty cool (I think the proof is neat and easy to understand for how important it is), think about how useful this was early on when you were trying to add together fractions; you find the least common denominator usually by using the prime factorization of the denominators. Similarly, when you want to reduce the ratio of two integers, it can be useful to divide both the numerator and denominator by the greatest common factor, which again can be found using the greatest common factor. If it weren't true you would have to find another algorithm! In other areas I know very little about, like cryptography (by the way, fun to read about when you are learning elementary number theory), the fundamental theorem of arithmetic gives you a good way to send secret messages to another person just using knowledge of one of the prime factors of a really big number. We always know this prime factorization exists, but it can be very hard to actually find it for a really big number.

As people are hinting at in the comments, this idea generalizes to other areas in abstract algebra (a part of math where you study sets of things with different levels of structure on them); it can be useful to try and find the building blocks of other sets. In fact building other (finite) fields, which are sets of numbers that are a lot like the rational and real numbers in their level of structure, relies on using building blocks of polynomials and a euclidean division similar to the one you use when you divide integers by other integers. When I started learning about that stuff, I found it really helpful to think back on how these processes worked for things I found more familiar, like integers.

I haven't gotten very far in math, but I have found that concepts like "how do we reduce this one thing that we don't know much about into just a collection of smaller things we do know something about" come up a lot across subjects. It helps to have seen them before and have a good stock of simpler examples in easier to grasp or more familiar places.

• Modern ( computer- assisted ) cryptography is based on basic Number-Theory, and almost all of basic Number-Theory is based on the F.T.A. Modern encryption methods began (independently, about the same time) by the American NSA and the British MI-5 or MI-6. – DanielWainfleet Aug 12 '18 at 3:13

I decided to compare this theorem to another favorite theorem of mine, Fermat's little theorem (which some people just call "Fermat's theorem).

On ProofWiki, I went to the pages for both theorems and clicked "what links here": https://proofwiki.org/wiki/Special:WhatLinksHere/Fundamental_Theorem_of_Arithmetic , https://proofwiki.org/wiki/Special:WhatLinksHere/Fermat%27s_Little_Theorem

As you can see, the fundamental theorem of arithmetic is invoked for the following results:

• Positive Integer Greater than 1 has Prime Divisor
• Integers form Unique Factorization Domain
• Cartesian Product of Countable Sets is Countable
• Power of Prime Divides
• Set of Divisors of Integer
• Tau Function from Prime Decomposition
• Ostrowski's Theorem
• Sum of Reciprocals of Primes is Divergent
• Zero and One are the only Consecutive Perfect Squares
• Product Form of Sum on Completely Multiplicative Function
• Solution of Linear Diophantine Equation
• Number of Primes is Infinite (this can be proven without the fundamental theorem of arithmetic, so it's okay if you choose to cross it off the list)
• Dirichlet L-Function from Trivial Character
• Finite Multiplicative Subgroup of Field is Cyclic
• Sum Over Divisors of von Mangoldt is Logarithm
• Power of Elements is Subgroup
• Power of Sum Mod Prime
• Set of Finite Subsets of Countable Set is Countable
• Cyclicity Condition for Units of Ring of Integers Modulo m
• Irrationality of Logarithm
• Integer to Rational Power is Irrational iff not Integer or Reciprocal

Compare Fermat's little theorem:

• Floor Defines Equivalence
• Index of Subgroup of Subgroup
• Ring of Integers Modulo Prime is Field
• Wilson's Theorem
• Lucas-Lehmer Test
• Integer as Sum of Two Squares
• Factors of Mersenne Numbers
• Values of Legendre Symbol
• P-adic Norm not Complete on Rational Numbers
• Euler's Criterion
• Finite Cyclic Group has Euler Phi Generators

I have chosen to ignore lemmas, corollaries, definitions, biographies, and of course pages that are very specific to ProofWiki, like the Help:Page Editing page.

My conclusion is, that by this measure, Fermat's little theorem is important in the sense that other theorems depend on it, but not as important as the fundamental theorem of arithmetic.