We are ready to prove the Fundamental Theorem of
Arithmetic. Recall that this
is an ancient theorem—it appeared over 2000 years ago in
Euclid's *Elements*.

Theorem 3.5.1 If $n>1$ is an integer then it can be factored as a product of primes in exactly one way. In other words, in any two factorizations of $n$ into primes, every prime $p$ occurs the same number of times in each factorization.

**Proof.**
We already have seen that $n$ can be factored in at least one
way, in theorem 2.4.4, so we
need only prove uniqueness.
The proof is by contradiction. Suppose, for instance, that $p$
occurs $i\ge 0$ times in one prime factorization of $n$, but $j>i$ times in
a different prime factorization, so
$$
p^ip_1p_2\cdots p_k = n = p^j q_1q_2\cdots q_l,
$$
where each $p_m$ and $q_m$ is a prime different from $p$.
Canceling $p^i$ gives
$$
p_1p_2\cdots p_k = p^{j-i} q_1q_2\cdots q_l.
$$
Since $(p_m,p)=1$, $[p_m]\in \U_p$, by
corollary 3.4.4, and so
$[p_1p_2\cdots p_k]\in \U_p$, by
theorem 3.4.9.
On the other hand,
$[p_1p_2\cdots p_k]=[p^{j-i}q_1q_2\cdots q_l]=[0]$,
and since $[0]\notin \U_p$ we have a
contradiction.$\qed$

Collecting like primes, this theorem says that any integer $n>1$ can be expressed uniquely in the form $$ p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k} $$ where $p_1< p_2< \cdots< p_k$ are distinct primes and the $e_i$ are positive integers. Often we wish to compare the prime factorizations of different integers. If we have two (positive) integers, say $a$ and $b$, the prime factorization of $a$ may use a different set of primes than the prime factorization of $b$; that is, some prime $p$ may occur in the prime factorization of $a$ but not $b$ (or vice versa). If we wish to use the same set of primes in both factorizations, we simply include $p^0=1$ in the prime factorization of $b$. For example, if $a$ factors as $2^2\cdot 3^5\cdot 7^3$ and $b$ factors as $3^2\cdot 5^4\cdot 11^3$, then we can write $$ \eqalign{ a & = 2^2\cdot 3^5\cdot 5^0\cdot 7^3\cdot 11^0 \cr b & = 2^0\cdot 3^2\cdot 5^4\cdot 7^0\cdot 11^3 \cr} $$ Such representations are not unique, of course, though they are unique except for the primes that appear with exponent $0$. When using an expression like $p_1^{e_1}p_2^{e_2}… p_k^{e_k}$, be sure that you make clear whether or not the $e_i$ are positive or merely non-negative; if the latter, remember not to invoke more uniqueness than is justified. Here's a simple but useful theorem that uses this approach.

Theorem 3.5.2 If $a$ and $b$ are positive integers, $\displaystyle a=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$ and $\displaystyle b=p_1^{f_1}p_2^{f_2}\cdots p_k^{f_k}$ (where the $p_i$ are distinct and the $e_i$ and $f_i$ are non-negative), then $a$ divides $b$ if and only if $e_i\le f_i$ for every $i$ from $1$ to $k$.

**Proof.**
Let
$\displaystyle
x= p_1^{t_1}p_2^{t_2}\cdots p_k^{t_k}
$,
so
$$
ax=(p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k})(p_1^{t_1}p_2^{t_2}\cdots p_k^{t_k})
=p_1^{e_1+t_1}p_2^{e_2+t_2}\cdots p_k^{e_k+t_k}.
$$
Thus, there is an $x$ such that $ax=b$ if and only if there are
non-negative integers $t_1,\ldots,t_k$ such that $e_i+t_i=f_i$ for
every $i$ from $1$ to $k$. Clearly such $t_i$ exist if and only if
$e_i\le f_i$ for every $i$ from $1$ to $k$.$\qed$

## Exercises 3.5

**Ex 3.5.1**
Let $a=3^2\cdot 5\cdot 7^3\cdot 13$
and $b=2^2\cdot 3^2\cdot 5^2\cdot 7^3\cdot 11\cdot 13^4$. Show that
$a\vert b$ by finding an $x$ such that $b=ax$.

**Ex 3.5.2**
Suppose $a=p_1^{e_1}p_1^{e_2}\cdots p_i^{e_i}$, with
$p_1< p_2< \cdots< p_i$. Describe conditions on the prime factorization
of $a$ that are equivalent to the following statements. Does it make a
difference whether the $e_i$ are allowed to be $0$?

a) $a$ is even

b) $a$ is odd

c) $a$ is a perfect square

d) $a$ is a perfect cube

e) $a$ is square-free (i.e., the only divisor of $a$ which is a perfect square is $1$)

**Ex 3.5.3**
Suppose $n>0$ and $n$ is not a perfect square. Prove that
$\sqrt{n}$ is not rational.

**Ex 3.5.4**
Prove that if $a>0$, $b>0$ and $a^2\vert b^2$,
then $a\vert b$.

**Ex 3.5.5**
If $a=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$, how many positive
divisors does $a$ have?

**Ex 3.5.6**
When does a positive integer $a$ have an odd number of
positive divisors?

**Ex 3.5.7**
Find the smallest positive integer $x$ such that $2x$ is a
perfect square and $3x$ is a perfect cube; prove that it is the smallest.

**Ex 3.5.8**

a) Show that $10\vert a^2$ implies $10\vert a$.

b) What integers $n$ have the property that for all $a$, $n\vert a^2$ implies $n\vert a$?

**Ex 3.5.9**
How many zeros are there on the end of $(1000!)$?

**Ex 3.5.10**
In the proof of the Fundamental Theorem, we made the
following statement:
"Since
$x$ is a product of primes other than $p$, $[x]\in \U_p$, by
corollary 3.4.4 and theorem
3.4.9.'' But theorem 3.4.9
concerns the product of only two elements of $\U_n$. Prove, by
induction, that $\U_n$ is closed under an arbitrary number of
multiplications.