# Intuition on 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

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