Divisibility and Primes

Section 1.5 Divisibility and Primes

The set

\begin{equation*} \Z=\{ \ldots,-3,-2,-1,0,1,2,3,\ldots \} \end{equation*}

of all the whole numbers is called the integers. We say that an integer \(a\) divides an integer \(b\text{,}\) written \(a|b\) , if \(b=ak\) for some integer \(k\text{.}\) If \(a|b\text{,}\) we say that \(b\) is divisible by \(a\text{,}\) and we say \(a\) is a divisor of \(b\text{.}\) We write \(a\nmid b\) to indicate that \(a\) does not divide \(b\text{.}\) An integer \(p>1\) whose only positive divisors are \(1\) and \(p\) is called prime.

Checkpoint 1.5.1.

Say which of the following are true, or false, or neither. Explain.

\begin{align*} 6|3 \amp \amp 3|6 \amp \amp 6/3 \end{align*}

Here are two important facts about divisibility and primes.

Theorem 1.5.2. The Division Algorithm.

Let \(m\) be a positive integer. For every integer \(n\) there are unique integers \(q,r\) that satisfy

\begin{align*} n=mq + r, \amp \amp 0\leq r\lt m. \end{align*}

The number \(q\) is called the quotient and the number \(r\) is called the remainder for dividing \(n\) by \(m\).

Theorem 1.5.3. The Fundamental Theorem of Arithmetic.

Every integer \(n\gt 1\) can be written as a product of primes. Further, this prime factorization is unique. That means that if

\begin{equation*} n=p_1p_2\cdots p_k=q_1q_2\cdots q_\ell \end{equation*}

for primes \(p_i,q_j\text{,}\) then \(k=\ell\) and there is a rearrangement of the subscripts for which \(p_i=q_i\) for \(1\leq i\leq k\text{.}\)

Here is a useful corollary that relates divisibility to the Division Algorithm.

Corollary 1.5.4.

Let \(m\) be a positive integer, let \(n\) be any integer, and let \(n=qm+r\text{,}\) where \(q,r\) are integers, with \(r\) in the range \(0\leq r\lt m\text{,}\) as guaranteed by the Division Algorithm. Then we have \(m|n\) if and only if \(r=0\text{.}\)

Proof.

Suppose \(r=0\text{.}\) Then \(n=mq+r\) reduces to \(n=mq\text{,}\) so \(m|n\text{.}\) Conversely, suppose that \(m|n\text{.}\) Then we have \(n=mk\) for some integer \(k\text{.}\) The Division algorithm says that \(n=mq+r\) is the only possible way to write \(n\) as a multiple of \(m\) with a remainder in the range \(0\leq r\lt m\text{.}\) Therefore we conclude that \(q=k\) and \(r=0\text{.}\)

Remark on the statement and proof of Corollary 1.5.4. The phrase "if and only if" means that the following two statements hold.

If \(r=0\text{,}\) then \(m|n\text{.}\)
If \(m|n\text{,}\) then \(r=0\text{.}\)

It often works well to construct a proof for an "if and only if" statement in two parts, one part for each of the two "if-then" statements. Statement 1 is called the "if" part of the "if and only if" statement, and statement 2 is called the "only if" part of the "if and only if" statement.

Checkpoint 1.5.5.

Prove the following statement: An integer \(n\) is divisible by 6 if and only if \(n\) can be written as a product \(n=ab\) of integers \(a,b\) such that \(a\) is divisible by 2 and \(b\) is divisible by 3. Write a proof in two parts. For part 1, suppose that \(a\) is divisible by 2 and \(b\) is divisible by 3, and then show that \(n=ab\) is divisible by \(6\text{.}\) For part 2, suppose that \(n\) is divisible by 6, and then show that there exist integers \(a,b\) so that \(n=ab\text{,}\) and that \(a\) is divisible by 2 and \(b\) is divisible by 3.

Here is a fact that demonstrates the power of the Division Algorithm and the Fundamental Theorem of Arithmetic.

Proposition 1.5.6.

There are infinitely many prime numbers.

Proof.

We wish to show that there are infinitely many primes. Suppose, on the contrary, that there exist only finitely many primes, say \(p_1,p_2,\ldots,p_r\text{.}\) Let \(s=p_1p_2\cdots p_r+1\text{.}\) Using the division algorithm to divide \(s\) by \(p_1\text{,}\) we have \(s= p_1q+r\) with \(q=p_2p_3\cdots p_r\) and \(r=1\text{.}\) By Corollary 1.5.4, the fact that \(r=1\) means that \(p_1\) does not divide \(s\text{,}\) so \(p_1\) cannot appear in the prime factorization of \(s\text{.}\) A similar argument shows that none of the \(p_j\)’s can appear in the prime factorization of \(s\text{.}\) This contradicts the Fundamental Theorem of Arithmetic, that says \(s\) can be expressed as a product of primes. We conclude that there are infinitely many primes.

Remark on the proof of Proposition 1.5.6. The proof uses a logic structure called proof by contradiction. To show that a claim is true ("there are infinitely many primes"), a proof by contradiction begins by supposing that the opposite of the claim is true ("suppose there are only finitely many primes"). Next, we show that there is an impossible consequence ("the Fundamental Theorem of Arithmetic is false"). We conclude that the opposite claim ("there are only finitely many primes") must be false, so the original claim ("there are infinitely many primes") is true.

Checkpoint 1.5.7.

In the proof of Proposition 1.5.6, a number \(s\) is constructed by multiplying together a collection of prime numbers and then adding 1. Then we conclude that \(s\) is not divisible by any of the primes in the original collection. Must it be the case that \(s\) itself must be prime, but just not equal to any of the primes in the original collection? Does it always turn out that the product of a collection of primes, plus 1, is a prime number? If not, give an example of a collection of prime numbers that, when multiplied together and increased by 1, is not prime.

Exercises Exercises

1.

An integer is called even if it is divisible by \(2\text{,}\) and otherwise it is called odd. Use the Division Algorithm to show that an integer \(n\) is odd if and only if \(n=2k+1\) for some integer \(k\text{.}\) Then use this fact to show that the product of two odd integers must be odd.

2.

Let \(p\) be prime and suppose that \(p|(ab)\) for some integers \(a,b\text{.}\) Show that it must be the case that \(p|a\) or \(p|b\) (or both).

3. Consolidating prime factors.

Here is another version of Theorem 1.5.3 (the FTA).

The Fundamental Theorem of Arithmetic, version 2 (FTAv2). Every integer \(n\gt 1\) can be written in the form
\begin{equation} n=p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}\tag{1.5.1} \end{equation}
where \(p_1,p_2,\ldots,p_r\) are primes with \(p_1\lt p_2\lt \cdots \lt p_r\text{,}\) and the numbers \(e_1,e_2,\ldots,e_r\) and the number \(r\) are positive integers. Further, this expression is unique in the sense that if \(n=q_1^{f_1}q_2^{f_2}\cdots q_s^{f_s}\) for some increasing sequence of primes \(q_1,q_2,\ldots,q_s\) and positive integers \(f_1,f_2,\ldots,f_s\text{,}\) then \(s=r\text{,}\) \(q_i=p_i\) for all \(i\text{,}\) and \(f_i=e_i\) for all \(i\text{.}\)

Consider the products
\begin{equation*} 108 = p_1p_2p_3p_4p_5 = q_1q_2q_3q_4q_5 \end{equation*}
where \(p_1=p_3=2\text{,}\) \(p_2=p_4=p_5=3\text{,}\) \(q_1=q_3=q_5=3\text{,}\) and \(q_2=q_4=2\text{.}\) Does the fact that \(p_1\neq q_1\) violate the FTA? Write the factorization for 108 given by the FTAv2. Find the values of \(r\text{,}\) \(p_1,p_2,\ldots,p_r\text{,}\) and \(e_1,e_2,\ldots,e_r\text{.}\)
Why do the FTA and the FTAv2 assume that \(n\gt 1\text{?}\) What happens if \(n=1\text{?}\) What happens if we change the definition of prime numbers to allow 1 to be a prime number?
Suppose that an integer \(a\gt 1\) has prime factorization \(a=p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}\) as given FTAv2, and suppose a positive integer \(m\) divides \(a\text{.}\) What can be said about the FTAv2 prime factorization of \(m\text{?}\)

Prev Top Next