Skip to main content

Section 1.3 Divisibility and Modular Arithmetic

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{.}\) Given a positive integer \(m\text{,}\) we say integers \(a,b\) are equivalent modulo \(m\), written \(a\equiv b \pmod{m}\) , if \(m|(a-b)\text{.}\) An integer \(p>1\) whose only positive divisors are \(1\) and \(p\) is called prime.

Checkpoint 1.3.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 \\ \amp 8\equiv 2\pmod{3} \amp \amp 7\equiv 2 \pmod{3} \end{align*}
Here are two important facts about divisibility and primes.
Here is a useful corollary that relates divisibility to the Division Algorithm.

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.3.4. The phrase "if and only if" means that the following two statements hold.
  1. If \(r=0\text{,}\) then \(m|n\text{.}\)
  2. If \(m|n\text{,}\) then \(r=0\text{.}\)
It is often a good idea 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.
Here is a fact that demonstrates the power of the Division Algorithm and the Fundamental Theorem of Arithmetic.

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.3.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.3.5. 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.
We write \(\Z_m\) to denote the set
\begin{equation*} \Z_m = \{0,1,\ldots,m-1\} \end{equation*}
of possible remainders obtained when dividing by a positive integer by \(m\text{.}\) The function \(\Z \to \Z_m\) that sends an input \(n\) to its remainder when dividing by \(m\) is called "reducing mod \(m\)". Sometimes we write \(n \MOD m\), pronounced "\(n\) modulo \(m\)" or simply "\(n\) mod \(m\)", to denote this remainder.
We define operations \(a+_m b\) and \(a\cdot_m b\) for elements \(a,b\) in \(\Z_m\) by
\begin{align*} a+_m b \amp = (a+b)\MOD m\\ a\cdot_m b \amp = (ab)\MOD m \end{align*}
The operations \(+_m\text{,}\) \(\cdot_m\) are called addition modulo \(m\) and multiplication modulo \(m\), respectively. The set \(\Z_m\) is sometimes called the "\(m\)-hour clock" and the operations \(+_m,\cdot_m\) are called "clock arithmetic" or "arithmetic modulo \(m\)".

Checkpoint 1.3.6.

Find examples of integers \(m\gt 1\text{,}\) \(a,b\in \Z_m\) such that
  1. \(\displaystyle a+_m b = 0\)
  2. \(a \cdot_m b = 0\) and \(a\neq 0\) and \(b\neq 0\)
  3. \(a \cdot_m b =1\) and \(a\neq 1\) and \(b\neq 1\)
Here is a useful fact that connects equivalence modulo an integer \(m\) with the operation that send an integer \(n\) to \(n \MOD m\text{.}\)

Proof.

Use the division algorithm to write
\begin{align*} a \amp = qm + r\\ b \amp = q'm + r' \end{align*}
for some integers \(q,q'\) and \(r,r'\) in the range \(0\leq r,r'\lt m\text{,}\) so we have
\begin{equation} a-b = (q-q')m + (r-r')\tag{1.3.1} \end{equation}
with \(r-r'\) in the range \(-(m-1)\leq r-r'\leq m-1\text{.}\) To establish the "if" part of the statement in the Proposition, suppose that \(a \MOD m = b\MOD m\text{.}\) This means that \(r=r'\text{,}\) so (1.3.1) becomes \(a-b=(q - q')m\text{.}\) Thus we have \(m|(a-b)\text{,}\) so we conclude that \(a\equiv b \pmod{m}\text{.}\) To establish the "only if" part of the statement in the Proposition, suppose that \(a\equiv b \pmod{m}\text{,}\) so we have that \(a-b\) is a multiple of \(m\text{,}\) say \(a-b=km\text{.}\) Then (1.3.1) becomes
\begin{equation*} r-r' = m(k-q+q'). \end{equation*}
Because \(-(m-1)\leq r-r'\leq m-1\text{,}\) we conclude that \(k-q+q'\) must be zero. Thus we have \(r=r'\text{,}\) which means that \(a \MOD m = b\MOD m\text{.}\) This completes the proof.

Exercises Exercises

1.

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).

2.

Let \(m\) be a positive integer.
  1. Show that \(a\equiv a \pmod{m}\) for every integer \(a\text{.}\) (This is called the reflexive property of equivalence modulo \(m\text{.}\))
  2. Show that if \(a\equiv b \pmod{m}\) then \(b\equiv a \pmod{m}\text{.}\) (This is called the symmetric property of equivalence modulo \(m\text{.}\))
  3. Show that if \(a\equiv b \pmod{m}\) and \(b\equiv c \pmod{m}\text{,}\) then \(a\equiv c \pmod{m}\text{.}\) (This is called the transitive property of equivalence modulo \(m\text{.}\))

3.

Let \(m\) be a positive integer. Show that if \(a_1\equiv b_1 \pmod{m}\) and \(a_2\equiv b_2 \pmod{m}\text{,}\) then
  1. \(a_1+a_2\equiv b_1+b_2 \pmod{m}\text{,}\) and
  2. \(a_1a_2\equiv b_1b_2 \pmod{m}\text{.}\)

4. The distributive law for modular arithmetic.

Prove the following property of modular arithmetic, called the distributive law. For any positive integer \(m\text{,}\) we have
\begin{equation} a\cdot_m (b+_m c) = (a\cdot_m b) +_m (a\cdot_m c)\tag{1.3.2} \end{equation}
for all \(a,b,c\) in \(\Z_m\text{.}\)
Hint.
By the ordinary distributive law for integers, we have
\begin{equation*} a(b+c)=ab+ac. \end{equation*}
It follows that
\begin{equation*} a(b+c)\equiv ab+ac \pmod{m} \end{equation*}
Now use Exercise 1.3.3 to show that
\begin{equation*} a(b+c) \equiv a\cdot_m (b+_m c) \pmod{m}. \end{equation*}
and
\begin{equation*} ab+ac \equiv [(a\cdot_m b) +_m (a\cdot_m c)] \pmod{m}. \end{equation*}

5.

Suppose that \(m\) is not prime. Show that there exist nonzero elements \(a,b\) in \(\Z_m\) for which there exists no \(x\) in \(\Z_m\) such that \(ax\equiv b \pmod{m}\text{.}\)

6.

Let \(m\) be a prime. Let \(a\) be a nonzero element of \(\Z_m\) and let \(b\) be any element of \(\Z_m\text{.}\) Show that there exists some \(x\) in \(\Z_m\) such that \(ax\equiv b \pmod{m}\text{.}\) Hint: consider the function \(\mu_a\colon \Z_m \to \Z_m\) given by \(n\to an \MOD m\text{.}\) Notice that \(ax\equiv b \pmod{m}\) is the same thing as \(\mu_a(x)=b\) (say why!). Show that \(\mu_a\) is one-to-one, then cite an appropriate result from these Notes to conclude that \(\mu_a\) is onto. Finally, explain how this solves the problem by guaranteeing the existence of the \(x\) that you need.