§1.3 Primes and Unique Factorization

Definition of Prime

Every nonzero integer $n$ except $\pm 1$ has at least four distinct divisors, namely 1, $-1$, $n$, and $-n$. Integers that have only these four divisors play a crucial role in number theory.

Prime: An integer $p$ is said to be prime if $p \neq 0$, $\pm 1$, and the only divisors of $p$ are $\pm 1$ and $\pm p$.

Example 1.3.1: Prime Numbers

The numbers $3, -5, 7, -11, 13,$ and $-17$ are prime, but 15 is not (because 15 has divisors other than $\pm 1$ and $\pm 15$, such as 3 and 5).

The integer 4567 is prime, but proving this fact from the definition requires a tedious check of all its possible divisors. Fortunately, there are more efficient methods for determining whether an integer is prime, one of which is discussed at the end of this section.

Infinitely Many Distinct Primes

It is not difficult to show that there are infinitely many distinct primes (Exercise 1.32). Because an integer $p$ has the same divisors as $-p$, we see that:

$$ p \text{ is prime if and only if } -p \text{ is prime.} $$

If $p$ and $q$ are both prime and $p \mid q$, then $p$ must be one of 1, $-1$, $q$, or $-q$. But since $p$ is prime, $p \neq \pm 1$. Hence:

$$ \text{if } p \text{ and } q \text{ are prime and } p \mid q, \text{ then } p = \pm q. $$

Under what conditions does a divisor of a product $bc$ necessarily divide $b$ or $c$? Theorem 1.4 gave one answer to this question. Here is another.

Theorem 1.5: Primes Dividing a Product

Let $p$ be an integer with $p \neq 0, \pm 1$. Then $p$ is prime if and only if it has the property:

$$ \text{whenever } p \mid bc, \text{ then } p \mid b \text{ or } p \mid c. $$

Proof of Theorem 1.5

Since this is an "if and only if" statement, there are two parts to the proof.

Step 1: Assume that $p$ is prime and prove that $p$ has the property stated in the theorem.

Proof of Step 1: If $p$ is prime and divides $bc$, consider the gcd of $p$ and $b$. Now, $(p, b)$ must be a positive divisor of the prime $p$. So the only possibilities are $(p, b) = 1$ and $(p, b) = \pm p$ (whichever is positive). If $(p, b) = \pm p$, then $p \mid b$. If $(p, b) = 1$, since $p \mid bc$, we must have $p \mid c$ by Theorem 1.4. In every case, therefore, $p \mid b$ or $p \mid c$. Hence, $p$ has the property stated in the theorem.

Step 2: Assume that $p$ is an integer that has the property stated in the theorem and prove that $p$ is prime.

Proof of Step 2: This proof is left to the reader (Exercise 1.14). $\blacksquare$

Corollary 1.6: Prime Divisors in Products

If $p$ is prime and $p \mid a_1a_2\cdots a_n$, then $p$ divides at least one of the $a_i$.

Proof of Corollary 1.6

Proof: If $p \mid a_1(a_2a_3 \cdots a_n)$, then $p \mid a_1$ or $p \mid (a_2a_3 \cdots a_n)$ by Theorem 1.5. If $p \mid a_1$, we are finished. If not, continue this process, using Theorem 1.5 repeatedly. After at most $n$ steps, there must be an $a_i$ that is divisible by $p$. $\blacksquare$

Prime Factorizations

Choose an integer other than 0, $\pm 1$. If you factor it "as much as possible," you will find that it is a product of one or more primes. For example:

$$ 12 = 4 \cdot 3 = 2 \cdot 2 \cdot 3, \\ 60 = 12 \cdot 5 = 2 \cdot 2 \cdot 3 \cdot 5, \\ 113 = 113 \text{ (prime)}. $$

In this context, we allow the possibility of a "product" with just one factor in case the number we begin with is actually a prime. What was done in these examples can always be done.

Theorem 1.7: Every Integer is a Product of Primes

Every integer $n$ except 0, $\pm 1$ is a product of primes.

Proof of Theorem 1.7

First note that if $n$ is a product of primes, say $n = p_1p_2\cdots p_k$, then $-n = (-p_1)p_2\cdots p_k$ is also a product of primes. Consequently, we need to prove the theorem only when $n > 1$. The idea of the proof can be summarized like this:

Let $S$ be the set of all integers greater than 1 that are not a product of primes. Show that $S$ is the empty set. Then, since there are no integers in $S$, it must be the case that every integer greater than 1 is a product of primes (otherwise, it would be in $S$).

Proof that $S$ is empty: The proof is by contradiction: We assume that $S$ is not empty and use that assumption to reach a contradiction. So assume that $S$ is not empty. Then $S$ contains a smallest integer $m$ by the Well-Ordering Axiom. Since $m \in S$, $m$ is not itself prime. Hence $m$ must have positive divisors other than 1 or $m$, say $m = ab$ with $1 < a < m$ and $1 < b < m$. Since both $a$ and $b$ are less than $m$ (the smallest element of $S$), neither $a$ nor $b$ is in $S$. By the definition of $S$, both $a$ and $b$ are the product of primes, say:

$$ a = p_1p_2 \cdots p_r \quad \text{and} \quad b = q_1q_2 \cdots q_s, $$

with $r \geq 1$, $s \geq 1$, and each $p_h$, $q_j$ prime. Therefore:

$$ m = ab = p_1p_2 \cdots p_r q_1q_2 \cdots q_s $$

is a product of primes, so that $m \notin S$. We have reached a contradiction: $m \in S$ and $m \notin S$. Therefore, $S$ must be empty. $\blacksquare$

Composite Numbers

An integer other than 0, $\pm 1$ that is not prime is called composite. Although a composite integer may have several different prime factorizations, such as:

$$ \begin{aligned} 45 &= 3 \cdot 3 \cdot 5, \\ 45 &= (-3) \cdot 5 \cdot (-3), \\ 45 &= 5 \cdot 3 \cdot 3, \\ 45 &= (-5) \cdot (-3) \cdot 3, \end{aligned} $$

these factorizations are essentially the same. The only differences are the order of the factors and the insertion of minus signs. You can readily convince yourself that every prime factorization of 45 has exactly three prime factors, say $q_1q_2q_3$. Furthermore, by rearranging and relabeling the $q_j$'s, you will always have $3 = \pm q_1$, $3 = \pm q_2$, and $5 = \pm q_3$. This is an example of the following theorem.

Theorem 1.8: The Fundamental Theorem of Arithmetic

Every integer $n$ except 0, $\pm 1$ is a product of primes. This prime factorization is unique in the following sense: If

$$ n = p_1p_2\cdots p_r \quad \text{and} \quad n = q_1q_2\cdots q_s $$

with each $p_i$, $q_j$ prime, then $r = s$ (that is, the number of factors is the same) and after reordering and relabeling the $q_j$'s,

$$ p_1 = \pm q_1, \quad p_2 = \pm q_2, \quad p_3 = \pm q_3, \quad \dots, \quad p_r = \pm q_r. $$

Proof of Theorem 1.8

Every integer $n$ except 0, $\pm 1$ has at least one prime factorization by Theorem 1.7. Suppose that $n$ has two prime factorizations, as listed in the statement of the theorem. Then

$$ p_1(p_2p_3 \cdots p_r) = q_1q_2q_3 \cdots q_s, $$

so that $p_1 \mid q_1q_2 \cdots q_s$. By Corollary 1.6, $p_1$ must divide one of the $q_j$. By reordering and relabeling the $q_j$'s if necessary, we may assume that $p_1 \mid q_1$. Since $p_1$ and $q_1$ are prime, we must have $p_1 = \pm q_1$. Consequently,

$$ \pm q_1p_2p_3 \cdots p_r = q_1q_2q_3 \cdots q_s. $$

Dividing both sides by $q_1$ shows that

$$ p_2(p_3p_4 \cdots p_r) = q_2q_3 \cdots q_s, $$

so that $p_2 \mid q_2q_3 \cdots q_s$. By Corollary 1.6, $p_2$ must divide one of the $q_j$; as before, we may assume $p_2 \mid q_2$. Hence, $p_2 = \pm q_2$ and

$$ \pm q_2p_3p_4 \cdots p_r = q_2q_3q_4 \cdots q_s. $$

Dividing both sides by $q_2$ shows that

$$ p_3(\pm p_4 \cdots p_r) = q_3q_4 \cdots q_s. $$

We continue in this manner, repeatedly using Corollary 1.6 and eliminating one prime on each side at every step. If $r = s$, then this process leads to the desired conclusion: $p_1 = \pm q_1$, $p_2 = \pm q_2$, $\dots$, $p_r = \pm q_r$. So to complete the proof of the theorem, we must show that $r = s$.

Proof that $r = s$

The proof that $r = s$ is a proof by contradiction: We assume that $r \neq s$ (which means that $r > s$ or that $r < s$), and show that this assumption leads to a contradiction.

First, suppose that $r > s$. Then after $s$ steps of the preceding process, all the $q_j$'s will have been eliminated and the equation will read

$$ \pm p_{s+1}p_{s+2} \cdots p_r = 1. $$

This equation says (among other things) that $p_r \mid 1$. Since the only divisors of 1 are $\pm 1$, we have $p_r = \pm 1$. However, since $p_r$ is prime, we know that $p_r \neq \pm 1$ by the definition of "prime." We have reached a contradiction ($p_r = \pm 1$ and $p_r \neq \pm 1$). So $r > s$ cannot occur. A similar argument shows that the assumption $r < s$ also leads to a contradiction and, hence, cannot occur. Therefore, $r=s$ is the only possibility, and the theorem is proved. $\blacksquare$

Corollary 1.9: Unique Factorization

Every integer $n > 1$ can be written in one and only one way in the form

$$ n = p_1p_2p_3 \cdots p_r, $$

where the $p_i$ are positive primes such that $p_1 \leq p_2 \leq p_3 \leq \dots \leq p_r$.

Proof: Exercise 1.3.12. $\blacksquare$

Primality Testing

In theory, it is easy to determine if a positive integer $n$ is prime. Just divide $n$ by every integer between 1 and $n$ to see if $n$ has a factor other than 1 or $n$. Actually, you need only check prime divisors because any factor of $n$ (except 1) is divisible by at least one prime. The following primality test greatly reduces the number of divisions that are necessary.

Theorem 1.10: Primality Test

Let $n > 1$. If $n$ has no positive prime factor less than or equal to $\sqrt{n}$, then $n$ is prime.

Before proving this theorem, it may be helpful to see how it is used.

Example 1.3.2: Primality of 137

To prove that 137 is prime, the theorem says that we must verify that 137 has no positive prime factors less than or equal to $\sqrt{137} \approx 11.7$; that is, we need only show that 2, 3, 5, 7, and 11 are not factors of 137. You can easily verify that none of them divide 137. Hence, 137 is prime by Theorem 1.10.

Proof of Theorem 1.10

The proof is by contradiction. Suppose that $n$ is not prime. Then $n$ has at least two positive prime factors, say $p_1$ and $p_2$, so that $n = p_1p_2k$ for some positive integer $k$. By hypothesis, $n$ has no positive prime divisors less than or equal to $\sqrt{n}$. Hence, $p_1 > \sqrt{n}$ and $p_2 > \sqrt{n}$. Therefore,

$$ n = p_1p_2k \geq p_1p_2 > \sqrt{n}\sqrt{n} = n, $$

which says that $n > n$, a contradiction. Since the assumption that $n$ is not prime has led to a contradiction, we conclude that $n$ is prime. $\blacksquare$

Theorem 1.10 is useful when working by hand with relatively small numbers. Testing very large integers for primality, however, requires a computer and techniques that are beyond the scope of this lesson.