# Looking to Acquire Intution Regarding the Fundamental Theorem of Arithmetic

I'm sorry ahead if time if this is overly trivial for this site.

Currently in school, much of what I enjoy is number theory - based. Currently, I lean pretty heavily on the FTA for a good deal of my understanding and proofs. That being said, recently I've realized my intuition behind the FTA is somewhat lacking. I can prove the theorem many ways, but still have trouble "seeing" or "visualizing" the uniqueness of the FTA. This is largely because I use the FTA to understand the ideas behind the proofs used in the uniqueness part of the proof of the FTA itself. Ie, I have a bad case of circular reasoning. For example, a typical way to show uniqueness is based on the fact that if $p$ is prime, $p \mid ab \implies p \mid a$ or $p \mid b$, but I use the FTA to understand this idea.

What I'm looking for, is some intuition behind the uniqueness of the FTA so that I may be able to understand it at a very intuitive level. I'm just appealing to the wiser, who may understand this through and through and may be able to offer some valuable insight on how they view the idea.

Thank you in advance for all that took the time to read this and/or offer insight

-typed using ipad, sorry for typos

• What do you mean by "the uniqueness of the FTA"? – Pedro Tamaroff Mar 6 '13 at 1:34
• Sorry, I should have been more clear in typing. By this I mean the uniqueness of the prime factorization of a natural number(up to ordering) – gone Mar 6 '13 at 1:38
• What is your question? Are you using the fundamental theorem of arithmetic to prove the statement $p \mid ab \implies p \mid a$ or $p \mid b$? Are you combining the statement $p \mid ab \implies p \mid a$ or $p \mid b$ which you already know how to prove with the fundamental theorem of arithmetic to derive the fundamental theorem of arithmetic? – Timothy Jul 18 at 20:53

There are many properties that are equivalent to uniqueness of factorization in $\,\Bbb Z.\:$ Below is a sample off the top of my head (by no means complete). Each provides a slightly different perspective on why uniqueness holds - perspectives that becomes clearer when one sees how these equivalent properties bifurcate in more general integral domains. Below we use the notation $\rm\:(a,b)=1\:$ to mean that $\rm\:a,b\:$ are coprime, i.e. $\rm\:c\mid a,b\:\Rightarrow\:c\mid 1.$

$\rm(1)\ \ \ gcd(a,b)\:$ exists for all $\rm\:a,b\ne 0\ \$ [GCD domain]

$\rm(2)\ \ \ a\mid BC\:\Rightarrow a=bc,\ b\mid B,\ c\mid C\ \ \,$ [Schreier refinement, Euler's four number theorem]

$\rm(3)\ \ \ a\,\Bbb Z + b\, \Bbb Z\, =\, c\,\Bbb Z,\:$ for some $\rm\,c\quad\$ [Bezout domain]

$\rm(4)\ \ \ (a,b)=1,\ a\mid bc\:\Rightarrow\: a\mid c\qquad\ \$ [Euclid's Lemma]

$\rm(5)\ \ \ (a,b)=1,\ \dfrac{a}{b} = \dfrac{c}{d}\:\Rightarrow\: b\mid d\quad\ \$ [Unique Fractionization]

$\rm(6)\ \ \ (a,b)=1,\ a,b\mid c\:\Rightarrow\: ab\mid c$

$\rm(7)\ \ \ (a,b)=1\:\Rightarrow\: a\,\Bbb Z\cap b\,\Bbb Z\, =\, ab\,\Bbb Z$

$\rm(8)\ \ \ gcd(a,b)\ \ exists\:\Rightarrow\: lcm(a,b)\ \ exists$

$\rm(9)\ \ \ (a,b)=1=(a,c)\:\Rightarrow\: (a,bc)= 1$

$\rm(10)\$ atoms $\rm\, p\,$ are prime: $\rm\ p\mid ab\:\Rightarrow\: p\mid a\ \ or\ \ p\mid b$

Which of these properties sheds the most intuitive light on why uniqueness of factorization entails? If I had to choose one, I would choose $(2),$ Schreier refinement. If you extend this by induction it implies that any two factorizations of an integer have a common refinement. For example if we have two factorizations $\rm\: a_1 a_2 = n = b_1 b_2 b_3\:$ then Schreier refinement implies that we can build the following refinement matrix, where the column labels are the product of the elements in the column, and the row labels are the products of the elements in the row

$$\begin{array}{c|ccc} &\rm b_1 &\rm b_2 &\rm b_3 \\ \hline \rm a_1 &\rm c_{1 1} &\rm c_{1 2} &\rm c_{1 3}\\ \rm a_2 &\rm c_{2 1} &\rm c_{2 2} &\rm c_{2 3}\\ \end{array}$$

This implies the following common refinement of the two factorizations

$$\rm a_1 a_2 = (c_{1 1} c_{1 2} c_{1 3}) (c_{2 1} c_{2 2} c_{2 3}) = (c_{1 1} c_{2 1}) (c_{1 2} c_{2 2}) (c_{1 3} c_{2 3}) = b_1 b_2 b_3.$$

This immediately yields the uniqueness of factorizations into primes (atoms). It also works more generally for factorizations into coprime elements, and for factorizations of certain types of algebraic structures (abelian groups, etc).

• wonderful answer, as usual! – Tyler Mar 6 '13 at 2:43
• Dear Math Gems, Is there a typo in (2) (more precisely, should $A$ and $a$ be the same)? Regards, – Matt E Mar 6 '13 at 2:48
• @Zachary I don't recall any textbooks that use $(2)$. You might have luck searching on the German name Vierzahlensatz. Nonunits $\rm\,A\,$ satisfying $(2)$ are called primal. One easily checks that atoms are primal $\Leftrightarrow$ prime. Products of primes are also primal. So "primal" may be viewed as a generalization of the notion "prime" $(10)$ from atoms to composites. – Math Gems Mar 6 '13 at 3:36
• Googling Schreier refinement turned up a gnarly statement from group theory. It looked like you might maybe make this theorem a statement about refinements of subgroups of $\mathbb Z$, but maybe you mean Schreier domain? – Thomas Andrews Mar 6 '13 at 14:28
• (I also didn't find any google result for "Euler's four number theorem.") – Thomas Andrews Mar 6 '13 at 15:52

Believe it or not, the fundamental theorem is mostly a result of the following result:

If $a,b$ are a pair of relatively prime integers, then $ax+by=1$ has for some integers, $x,y$.

In turn, this follows because the integers are something called a "principal ideal domain."

An "ideal" can be defined for a general ring, but in the case of the integers, we can define an ideal as a non-empty subset of $I\subseteq \mathbb Z$ which is closed under addition and taking additive inverses. In other words, it is a subgroup of $(\mathbb Z,+)$.

Now, we can, in general, take the set of multiples of some $d$, written $d\mathbb Z$. These are ideals, called the principal ideals.

The fact that these are the only ideals is why the previous theorem is true, because $a\mathbb Z + b\mathbb Z$ can be shown to be an ideal, so it must be principal, that is, $a\mathbb Z + b\mathbb Z=d\mathbb Z$ for some $d$. Since $a,b$ are both in the left side, $d|a$ and $d|b$. But $a,b$ have no common factors other than $\pm 1$, so $d=\pm 1$.

The fact that $\mathbb Z$ is a principal ideal domain is due to the existence of a division algorithm in $\mathbb Z$.

So, division algorithm implies principal ideal domain implies $ax+by=1$ solution implies unique factorization.

This chain of reason works in other places, such as the ring of polynomials over a field or $\mathbb Z[i]$ (the Gaussian integers.)

In other cases, division algorithm does not apply, but the ring is still a principal ideal domain.

In yet others, we don't even have a PID, but we still have unique factorization, such as the ring of polynomials with integer coefficients.

Arnold Ross professed the "fundamental theorem" should really be:

If $a|bc$ and $a,b$ are relative prime, then $a|c$

This is a direct corollary of the $ax+by=1$ theorem, and it is the heart of the "standard" fundamental theorem.

There are domains that are not unique factorization domains. For example, the set $\mathbb Z[\sqrt{-5}]=\{a+b\sqrt{-5}:a,b\in\mathbb Z\}$ is a domain in which unique factorization fails.

• Thank you for your response. I'm currently pondering much of it – gone Mar 6 '13 at 1:53

Any two integers have a greatest common divisor (gcd); $\gcd(a,b)$ can be written in the form $a x + b y$ where $x$ and $y$ are integers (by the Euclidean algorithm). This idea is behind a lot of elementary number theory.

Suppose $p$ divides $ab$ (so $ab = r p$ for some integer $r$), but $p$ does not divide $a$. Then $\gcd(a,p) = 1$ so $1 = x p + y a$ for some integers $x$ and $y$. Multiplying by $b$, $b = x b p + y a b = x b p + y r p = (xb + y r) p$, so $p$ divides $b$.

• Yes I've seen this before, but for some reason have generally attempted other ways of understanding. Is this how you perceive the theorem? – gone Mar 6 '13 at 1:55

Let $$\Bbb N = \{1,2,3.\dots\}$$.

In $$(\Bbb N, +)$$ the number $$1$$ is 'that indivisible object from which all can be uniquely derived'.

Indivisible: It is impossible to write $$1 = m + n$$.
Moreover, every other number $$a \ne 1$$ has such a decomposition.

One and Only One Derivation: Every number $$a$$ has one and only representation

$$\tag 1 a = \sum_{j=1}^{a}\, 1$$

The concept of multiplication as repeated addition is a powerful (it distributes over addition) and compact notation,

$$\tag 2 a \times b = \sum_{j=1}^{a}\, 1 \times \sum_{j=1}^{b}\, 1 = \sum_{j=1}^{a \times b}\, 1 = \big[\sum_{j=1}^{a}\, 1 \big ] \times b = a \times \big[\sum_{j=1}^{b}\, 1 \big] = \sum_{j=1}^{a}\, b = \sum_{j=1}^{b}\, a$$

While examining the properties of this incredible invention, you'll discover the definition of prime numbers and regard them as 'indivisible' objects in $$(\Bbb N^{\ge 2},\times)$$; you'll see how every number greater than $$1$$ can be represented as a product of primes (existence - check).

Definition: A number greater than $$1$$ is said to be a prime number if it is not in the range of the multiplication operator, $$(m,n) \mapsto m \times n$$, when it is restricted to $$\Bbb N^{\gt 1} \times \Bbb N^{\gt 1}$$.

It is now intuitively obvious that since the multiplicative notation is at its core a convolution directed at $$1$$ that distributes over addition, that the existence AND uniqueness of theorem $$\text{(1)}$$ must 'carry over' to a theorem in $$(\Bbb N^{\ge 2},\times)$$.

• I don't think it's clear at all that uniqueness must carry over - why should it? – Noah Schweber Jul 21 at 18:40
• @NoahSchweber Intuition is of course subjective with plenty of legroom (hanging rope?) So once you have existence, surely uniqueness must follow: $1$ generates numbers under addition so those indivisible primes, a packing of $1$'s for multiplication, must be the real (representation) deal. I was going to elaborate and discuss why all the residue morphisms $\pi_p: \Bbb N \to \frac{\Bbb N}{(p \, \Bbb N)}$ when applied to a fixed number $n$ 'build' a representation of $n$ via localization, but left that alone (but it has intuitive merit). – CopyPasteIt Jul 21 at 19:37

One can gain a better understanding of the importance of the FTA, and in particular the importance of the uniqueness in the factorization into primes, by studying examples of number systems where the FTA is not satisfied. By looking at such examples more closely, one can gain a better intuition of how some essential properties of the integers imply the FTA, and how small tweaks can make FTA fall apart.

For example, take our number system to be $$\mathbb{E} = 2\mathbb{N} = \{2,4,6,8,\ldots\}$$, the even positive numbers. Then:

• if $$p,q,r$$ are primes in $$\mathbb{N}$$, we have that $$4pqr = 2p \cdot 2qr = 2q \cdot 2pr = 2r \cdot 2pq$$ are three distinct factorizations of $$n=4pqr$$ in $$\mathbb{E}$$, and

• the number $$2pq$$ is a divisor of $$4pq =2pq \cdot 2$$ in $$\mathbb{E}$$, but we also have $$4pq =2p \cdot 2q$$ and $$2pq$$ does not divide $$2p$$ nor $$2q$$.

The point of this example is to understand the difference between the concepts of prime and irreducible, so as an exercise: determine all the primes in $$\mathbb{E}$$, and also all its irreducibles, and then show that $$\mathbb{E}$$ does not satisfy the FTA.