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*}
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.
Here are two important facts about divisibility and primes.
Theorem 1.3.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.3.3. The Fundamental Theorem of Arithmetic.
Every positive integer \(n\) 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.3.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.3.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.3.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.3.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.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.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.3.7.
In the proof of Proposition 1.3.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.
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\) as follows.
\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.8.
For each of the three items below, find examples of integers \(m\gt
1\text{,}\) \(a,b\in \Z_m\) for which the conditions hold.
- \(a+_m b = 0\) and \(a\neq 0\) and \(b\neq 0\)
- \(a \cdot_m b = 0\) and \(a\neq 0\) and \(b\neq 0\)
- \(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{.}\)
Proposition 1.3.9.
Let \(m>1\) be a positive integer, and let \(a,b\) be integers. Then \(a\equiv b \pmod{m}\) if and only if \(a\MOD m = b \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.
Checkpoint 1.3.10.
Is Proposition 1.3.9 true for the case \(m=1\text{?}\) If yes, does the given proof work? If the proposition is true for \(m=1\) and the proof does not work, write a proof that does work. If the proposition is false, give an example of two integers \(a,b\) such that exactly one of the two statements
\begin{gather*}
\text{"}a\equiv b \pmod{1}\text{"}\\
\text{"}a \MOD 1 = b \MOD 1\text{"}
\end{gather*}
is true. If the proposition is true and the given proof works, why don’t we include the case \(m=1\) in the statement of the proposition?
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.
- Show that \(a\equiv a \pmod{m}\) for every integer \(a\text{.}\) (This is called the reflexive property of equivalence modulo \(m\text{.}\))
- 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{.}\))
- 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
- \(a_1+a_2\equiv b_1+b_2 \pmod{m}\text{,}\) and
- \(a_1a_2\equiv b_1b_2 \pmod{m}\text{.}\)
4.
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{.}\)
5.
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 this text to conclude that \(\mu_a\) is onto. Finally, explain how this solves the problem by guaranteeing the existence of the \(x\) that you need.
