Say which of the following are true, or false, or neither. Explain.
\begin{align*}
\amp 8\equiv 2\pmod{3}
\amp \amp 7\equiv 2 \pmod{3}
\end{align*}
Section 1.6 Modular Arithmetic
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{.}\)
Checkpoint 1.6.1.
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\)”. We write \(n \MOD m\), pronounced “\(n\) modulo \(m\)” or simply “\(n\) mod \(m\)”, to denote this remainder.
Comment on notation: Be careful using “mod” and “MOD”. The expression \(\text{"}a\equiv b \pmod{m}\text{"}\) is a statement, that is, an assertion that is either true or false; by contrast, the expression \(\text{"}a \MOD m\text{"}\) is a number, which is neither true nor false. The expression \(\text{"}\!\!\pmod{m}\text{"}\) is an adjective that modifies the verb \(\text{"}\equiv\text{"}\) (pronounced “is equivalent to”). By contrast, the expression \(\text{"}\MOD\ m\text{"}\) is a function on the integers.
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.6.2.
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.6.1}
\end{equation}
with \(|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.6.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.6.1) becomes
\begin{equation*}
r-r' = m(k-q+q').
\end{equation*}
Because \(|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.6.3.
Is Proposition 1.6.2 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?
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.6.4.
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\)
Exercises Exercises
1.
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{.}\))
2.
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{.}\)
3.
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{.}\)
4.
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.
