Skip to main content

Section 3.1 The Integers mod \(n\)

The integers mod \(n\) have become indispensable in the theory and applications of algebra. In mathematics they are used in cryptography, coding theory, and the detection of errors in identification codes.
We have already seen in Example 1.30 that two integers \(a\) and \(b\) are equivalent mod \(n\) if \(n\) divides \(a - b\text{.}\) The integers mod \(n\) also partition \({\mathbb Z}\) into \(n\) different equivalence classes; we will denote the set of these equivalence classes by \({\mathbb Z}_n\text{.}\) Consider the integers modulo 12 and the corresponding partition of the integers:
\begin{align*} {[0]} & = \{ \ldots, -12, 0, 12, 24, \ldots \},\\ {[1]} & = \{ \ldots, -11, 1, 13, 25, \ldots \},\\ & \vdots\\ {[11]} & = \{ \ldots, -1, 11, 23, 35, \ldots \}. \end{align*}
When no confusion can arise, we will use \(0, 1, \ldots, 11\) to indicate the equivalence classes \({[0]}, {[1]}, \ldots, {[11]}\) respectively. We can do arithmetic on \({\mathbb Z}_n\text{.}\) For two integers \(a\) and \(b\text{,}\) define addition modulo \(n\) to be \((a + b) \pmod{n}\text{;}\) that is, the remainder when \(a + b\) is divided by \(n\text{.}\) Similarly, multiplication modulo \(n\) is defined as \((a b) \pmod{ n}\text{,}\) the remainder when \(a b\) is divided by \(n\text{.}\)

Example 3.1.

The following examples illustrate integer arithmetic modulo \(n\text{:}\)
\begin{align*} 7 + 4 & \equiv 1 \pmod{ 5} & 7 \cdot 3 & \equiv 1 \pmod{ 5}\\ 3 + 5 & \equiv 0 \pmod{ 8} & 3 \cdot 5 & \equiv 7 \pmod{ 8}\\ 3 + 4 & \equiv 7 \pmod{ 12} & 3 \cdot 4 & \equiv 0 \pmod{ 12}\text{.} \end{align*}
In particular, notice that it is possible that the product of two nonzero numbers modulo \(n\) can be equivalent to \(0 \) modulo \(n\text{.}\)

Example 3.2.

Most, but not all, of the usual laws of arithmetic hold for addition and multiplication in \({\mathbb Z}_n\text{.}\) For instance, it is not necessarily true that there is a multiplicative inverse. Consider the multiplication table for \({\mathbb Z}_8\) in Table 3.3. Notice that 2, 4, and 6 do not have multiplicative inverses; that is, for \(n = 2\text{,}\) 4, or 6, there is no integer \(k\) such that \(k n \equiv 1 \pmod{ 8}\text{.}\)
Table 3.3. Multiplication table for \({\mathbb Z_8}\)
\(\cdot\) 0 1 2 3 4 5 6 7
0 0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6 7
2 0 2 4 6 0 2 4 6
3 0 3 6 1 4 7 2 5
4 0 4 0 4 0 4 0 4
5 0 5 2 7 4 1 6 3
6 0 6 4 2 0 6 4 2
7 0 7 6 5 4 3 2 1

Proof.
We will prove (1) and (6) and leave the remaining properties to be proven in the exercises.
(1) Addition and multiplication are commutative modulo \(n\) since the remainder of \(a + b\) divided by \(n\) is the same as the remainder of \(b + a\) divided by \(n\text{.}\)
(6) Suppose that \(\gcd(a, n) = 1\text{.}\) Then there exist integers \(r\) and \(s\) such that \(ar + ns = 1\text{.}\) Since \(ns = 1 - ar\text{,}\) it must be the case that \(ar \equiv 1 \pmod{n}\text{.}\) Letting \(b\) be the equivalence class of \(r\text{,}\) \(a b \equiv 1\pmod{n}\text{.}\)
Conversely, suppose that there exists an integer \(b\) such that \(ab \equiv 1 \pmod{ n}\text{.}\) Then \(n\) divides \(ab -1\text{,}\) so there is an integer \(k\) such that \(ab - nk = 1\text{.}\) Let \(d = \gcd(a,n)\text{.}\) Since \(d\) divides \(ab - nk\text{,}\) \(d\) must also divide 1; hence, \(d = 1\text{.}\)
Because modular arithmetic follows the usual rules of addition and multiplication, we can work with them as we would in high-school algebra, as the following example shows.

Example 3.5.

Suppose we want to find all integers \(x\) such that
\begin{equation*} 3x \equiv 2 + 5x \pmod{7}\text{.} \end{equation*}
What would we do with the linear equation \(3x=2+5x\text{?}\) We would try to get to a solution for \(x\) by using various rules from algebra. The principle is that if we start with a valid equation and do the same operation on both sides, then we still have a valid equation. We will go through the steps slowly and be completely explicit about how we are using the properties of modular arithmetic.
\begin{align*} 3x + 2x &\equiv (2 + 5x) + 2x \pmod 7 \quad &&\mbox{add $2x$ to both sides}\\ 3x + 2x &\equiv 2 + (5x + 2x) \pmod 7 \quad &&\mbox{associativity of addition}\\ (3+2)x &\equiv 2 + (5+2)x \pmod 7 \quad &&\mbox{distributive property}\\ 5x &\equiv 2 + 0x \pmod 7 \quad &&\mbox{by evaluation}\\ 5x &\equiv 2 + 0 \pmod 7 \quad &&\mbox{$0$ times anything is $0$}\\ 5x &\equiv 2 \pmod 7 \quad &&\mbox{additive identity}\\ 3(5x) & \equiv 3 \cdot 2 \pmod 7 \quad &&\mbox{multiply by 3 on both sides}\\ (3 \cdot 5)x &\equiv 3 \cdot 2 \pmod 7 \quad &&\mbox{associativity of multiplication}\\ 1 x &\equiv 6 \pmod 7 \quad &&\mbox{by evaluation}\\ x &\equiv 6 \pmod 7 \quad &&\mbox{multiplicative identity} \end{align*}
Therefore, if \(x\) is a solution to the original equation, then \(x \equiv 6 \pmod 7\text{.}\) The converse is also true. If we substitute \(x=6\) into both sides of the original equation we see that it is a solution:
\begin{align*} 3 \cdot 6 \amp\equiv 18 \equiv 4 \pmod{7} \amp 2 + 5 \cdot 6 = 32 \amp\equiv 4 \pmod{7}\text{.} \end{align*}
Therefore, the set of solutions to the original equation are the integers which are congruent to 6 modulo 7.
Our simplifications referenced properties 2–4 of Proposition 3.4. In addition, we implicitly used properties 5 and 6 in choosing to add \(5x\) (the additive inverse of \(2x\)) and to multiply by \(3\) (the multiplicative inverse of \(5\)).
From now on, we will not do algebra in modular arithmetic in such painstaking detail as in Example 3.5. We will solve modular equations like we would any other equations. The main difference to remember is that modular division works very from division of real numbers. Instead of dividing by \(a\text{,}\) you should remember that you’re really multiplying by the equivalence class \(b\) such that \(ab \equiv 1 \pmod n\text{.}\)

Example 3.6.

Find all integers \(x\) such that
\begin{equation*} 3x + 4 \equiv x + 2 \pmod{6}\text{.} \end{equation*}
We subtract \(x+4\) on both sides and cancel to get
\begin{equation*} 2x \equiv 4 \pmod{6}\text{.} \end{equation*}
You might be tempted to divide by \(2\) to conclude that \(x \equiv 2 \pmod{6}\text{.}\) However, the greatest common divisor of \(2\) and \(6\) is \(2\text{,}\) and so \(2\) does not have a multiplicative inverse modulo \(6\text{.}\) By checking all equivalence classes modulo \(6\text{,}\) we can see that there are in fact two solutions, \(x \equiv 2 \pmod{6}\) or \(x \equiv 5 \pmod{6}\text{:}\)
\begin{gather*} 2 \cdot 0 \equiv 0 \pmod{6}\\ 2 \cdot 1 \equiv 2 \pmod{6}\\ 2 \cdot 2 \equiv 4 \pmod{6}\\ 2 \cdot 3 \equiv 0 \pmod{6}\\ 2 \cdot 4 \equiv 2 \pmod{6}\\ 2 \cdot 5 \equiv 4 \pmod{6} \end{gather*}
As an example of the power of modular arithmetic, we have the following theorem, due to Pierre de Fermat.

Proof.
By the division algorithm, \(a\) is congruent modulo \(p\) to an integer \(r\) in the range \(0 \leq r \lt p-1\text{.}\) Because \(a \equiv r \pmod p\) and \(a^p \equiv r^p \pmod p\text{,}\) we need to prove \(r \equiv r^p \pmod p\text{.}\)
Since \(r\) is non-negative, we can prove the statment by induction. If \(r = 0\text{,}\) then \(r^p = 0^p = 0 = r\text{.}\) Now suppose that the statement is true for some non-negative integer \(r\) and we want to prove it for \(r+1\text{.}\) By the binomial formula,
\begin{equation*} (r+1)^p = \sum_{i=0}^p \binom{p}{i} r^i, \quad\mbox{where}\quad \binom{p}{i} = \frac{p!}{i!(p-i)!}\text{.} \end{equation*}
The numerator \(p!\) is clearly divisible by \(p\text{.}\) When \(1 \leq i \leq p-1\text{,}\) then the denominator \(i!(p-i)!\) is a product of integers less than \(p\) and so not a multiple of \(p\) by the contrapositive of Euclid’s Lemma. Also by Euclid’s Lemma, the fraction \(p!/(i!(p-i)!)\) is therefore divisible by \(p\) for \(1 \leq i \leq p-1\text{.}\) Thus, in the summation above, all the terms are divisible by \(p\) except for \(i = 0\) and \(i = p\text{,}\) and so,
\begin{align*} (r+1)^p = \sum_{i=0}^p \binom{p}{i} r^i \amp\equiv r^0 + r^p \pmod p\\ \amp= 1 + r^p\\ \amp\equiv r + 1 \pmod p \end{align*}
by the induction hypothesis. Therefore, we’ve shown that \(r^p \equiv r \pmod p\) for all \(r \geq 0\) and thus \(a^p \equiv a \pmod p\) for all integers \(a\text{.}\)

Proof.
By Fermat’s little theorem, \(a^p \equiv a \pmod p\text{.}\) Since \(p\) does not divide \(a\) and \(p\) is prime, the greatest common divisor of \(p\) and \(a\) is \(1\text{.}\) By Proposition 3.4(6), there exists an integer \(b\) such that \(ab \equiv 1 \pmod p\) which we can use to cancel one factor of \(a\text{.}\) In other words,
\begin{align*} a^p \amp\equiv a \pmod p\\ a^pb \amp\equiv ab \pmod p\\ a^{p-1}ab \amp\equiv ab \pmod p\\ a^{p-1}\cdot 1 \amp\equiv 1 \pmod p\\ a^{p-1} \amp\equiv 1 \pmod p \end{align*}
which finishes the proof of the corollary.
PrevTopNext