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.