3.3: Modulo Arithmetic
- Page ID
- 88854
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)Terminology
All integers are said to be equivalent mod n to their remainder after dividing by n. For example \(9 \equiv 4 \pmod 5\) because \(9/5\) has remainder 4. Similarly \(13 \equiv 1 \pmod 2\) because \(13/2\) has remainder 1.
Example 3.3.1 shows a function evaluated (mod5).
| \(n\) | 0 | 1 | 2 | 3 | 4 |
| \(n^2\) | 0 | 1 | 4 | 4 | 1 |
The formal definition of modulo arithmetic requires two definitions.
\(a\) divides \(b\), written \(a|b\), if and only if there exists some \(k \in Z\) such that \(ak=b\).
aa is equivalent to \(b\) modulo \(n\), written \(a \equiv b \pmod n\), if and only if \(n|b−a\).
Note you may be familiar with the operation % in programming. That is an operation like + or ×. Here we are using a different number system like integers or reals. Avoid conflating the two. For example % has an order of operation. The question of order does not make sense with arithmetic mod \(n\) as will be demonstrated.
Practice
To address the issue of order of operation under modulo arithmetic consider the function \(f(n)=n^2+3n+5 \pmod 7\).
\begin{align*}
f(4) = & 4^2+3(4)+5 \pmod 7.\\
& \text{First we calculate each term above} \pmod 7.\\
4^2 = & 16 \equiv 2 \pmod 7.\\
3(4) = & 12 \equiv 5 \pmod 7.\\
5 = & 5 \equiv 5 \pmod 7.\\
& \text{Next we add the terms} \pmod 7.\\
2+5+5 = & 12 \equiv 5 \pmod 7.\\
& \text{Thus}\\
f(4) = & 5 \pmod 7.
\end{align*}
\begin{align*}
f(4) & = & 4^2+3(4)+5 \pmod 7\\
& = & 33 \pmod 7\\
& \equiv & 5 \pmod 7.
\end{align*}
Checkpoint \(\PageIndex{6}\)
(a) Calculate \(f(2)\) and \(f(6)\) twice; once using Example \(\PageIndex{4}\) and once using Example \(\PageIndex{5}\)
(b) Does it matter whether we mod each term or only after the last step?
Checkpoint \(\PageIndex{7}\)
Complete the table below calculating (mod7).
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| n2−3 |
Checkpoint \(\PageIndex{8}\)
Based on two numbers being equivalent modulo 5 if their remainders are the same after dividing by 5, list four (4) numbers that are equivalent to \(3 \pmod 5\).
Find all solutions to the following equation modulo 5. \(n^2-1=0 \pmod 5\).
Find all solutions to \(3n=0 \pmod 5\).
Complete the table below calculating modulo 8.
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 4n |
Checkpoint \(\PageIndex{12}\)
Find all solutions to \(4n=0 \pmod 8\).
Checkpoint \(\PageIndex{13}\)
Find all solutions to \(5n=0 \pmod 8\).
Checkpoint \(\PageIndex{14}\)
Using the graph paper in Table \(\PageIndex{15}\), graph the function \(p(n)=n^2-4n+3 \pmod 5\).
| 4 | |||||
| 3 | |||||
| 2 | |||||
| 1 | |||||
| 0 | |||||
| 0 | 1 | 2 | 3 | 4 |
Proofs
If \(a|b\) then \(−a|b\).
- Proof
-
By definition of divides a|ba|b implies there exists \(k \in Z\) such that \(ak=b\).
Consider
\begin{align*}
(-a)(-k) & = \\
ak & = b
\end{align*}Thus \(−a|b\) by definition of divides.
If \(a \equiv b \pmod n\) then \(a-n \equiv b \pmod n\).
- Proof
-
By definition of modulo equivalence \(a \equiv b \pmod n\) implies that \(n|(b−a)\). Thus, by definition of divides, there exists \(k \in Z\) such that \(nk=b−a\).
Consider
\begin{align*}
b-(a-n) & =\\
b-a+n & = nk+n\\
& = n(k+1).
\end{align*}Thus \(n|(b−(a−n))\) by definition of divides. This implies \(a-n \equiv b \pmod n\).