3.3: Modulo Arithmetic

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

Example \(\PageIndex{1}\): Function mod 5.

\(n\)	0	1	2	3	4
\(n^2\)	0	1	4	4	1

The formal definition of modulo arithmetic requires two definitions.

Definition \(\PageIndex{2}\): Divides.

\(a\) divides \(b\), written \(a|b\), if and only if there exists some \(k \in Z\) such that \(ak=b\).

Definition: Modulo.

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

Example \(\PageIndex{4}\): Calculate function modulo n, each step.

\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*}

Example \(\PageIndex{5}\): Calculate function modulo n, last step.

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

Checkpoint \(\PageIndex{9}\)

Find all solutions to the following equation modulo 5. \(n^2-1=0 \pmod 5\).

Checkpoint \(\PageIndex{10}\)

Find all solutions to \(3n=0 \pmod 5\).

Checkpoint \(\PageIndex{11}\)

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

Table \(\PageIndex{15}\) Graph Paper for function mod 5

4
3
2
1
0
	0	1	2	3	4

Proofs

Theorem \(\PageIndex{16}\)

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.

Lemma \(\PageIndex{17}\)

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