Skip to main content

Discrete Mathematical Structures

Dan Yasaki, Sebastian Pauli

Subsection 5.1.2 Modular arithmetic

Definition 5.1.2.1.

Let \(a\text{,}\) \(b\text{,}\) and \(m\) be integers, with \(m \gt 0\text{.}\) We say \(a\) is congruent to \(b\) modulo \(m\text{,}\) denoted \(a \equiv b \pmod m\) when \(m \mid (a - b)\text{.}\)
🔗
🔗

Remark 5.1.2.2.

This notion is different (but related) to the mod representing the remainder from the division algorithm. For example, if \(a = b\bmod m\text{,}\) then \(a\) is an integer with \(0\leq a \lt m\text{.}\) In particular, \(b \bmod m\) is an integer. On the other hand, \(a \equiv b \pmod m\) asserts a relationship between \(a\) and \(b\text{.}\) We never write \(b \pmod m\) by itself.
🔗
🔗

Proof.

It is enough to prove \(1 \implies 2\text{,}\) \(2 \implies 3\text{,}\) and \(3 \implies 1\text{.}\)
\(1 \implies 2\)
🔗
Suppose \(a \equiv b \pmod m\text{.}\) Then \(m \mid (a - b)\text{.}\) Then there exists an integer \(k\) such that \(a - b = mk\text{.}\) Solving for \(a\text{,}\) we have \(a = b + km\) as desired.
🔗
\(2 \implies 3\)
🔗
Suppose there exists \(k \in \ZZ\) such that \(a = b + km\text{.}\) Using the Division algorithm, we write \(a = qm + r\) and \(b = q'm + r'\text{,}\) for some integers \(q, q', r, r'\) with \(0\leq r, r' \lt m\text{.}\) We want to show that \(r = r'\text{.}\) We compute
\begin{equation*} a = b + km = (q'm + r') + km = (q' + k)m + r'. \end{equation*}
By the uniqueness of the integers in the Division algorithm, we must have \(q' + k = q\) and \(r' = r\text{.}\)
🔗
\(3 \implies 1\)
🔗
Suppose \(a \bmod m = b \bmod m\text{.}\) Let \(r = a \bmod m = b \bmod m\text{.}\) Then by the Division algorithm, there exist integers \(q\) and \(q'\) such that \(a = qm + r\) and \(b = q'm + r\text{.}\) We compute
\begin{equation*} a - b = (qm + r) - (q'm + r) = m(q - q'). \end{equation*}
Since \(q\) and \(q'\) are integers, we have \(m \mid (a - b)\text{.}\) Thus \(a \equiv b \pmod m\text{.}\)
🔗
🔗
🔗

Definition 5.1.2.4.

The set of integers that are congruent to \(a\) modulo \(m\) is called the congruence class of \(a\) modulo \(m\text{,}\) and is denoted \([a]_m\text{.}\) In particular,
\begin{equation*} [a]_m = \set{a + mk \mid k \in \ZZ}. \end{equation*}
The integer \(a\) is called a representative of the congruence class \([a]_m\text{.}\)
🔗
🔗

Remark 5.1.2.5.

Let \(m\in\NN\) and \(a\in\ZZ\text{.}\) By Theorem 5.1.2.3 we have
\begin{equation*} [a]_m= \set{a + mk \given k \in \ZZ}=\set{b\given b\in\ZZ \land b\equiv a \pmod m}= \set{b\given b\in\ZZ\land b\bmod m = a\bmod m}. \end{equation*}
It follows directly that if \(c\in[a]_m\) then \([c]_m=[a]_m\)
🔗
🔗

Example 5.1.2.6. Congruence classes modulo \(7\).

The congruence class of \(3\) modulo \(7\) is
\begin{equation*} [3] = \set{3 + 7k \mid k \in \ZZ} = \set{\dots, -11, -4, 3, 10, 17, \dots} \end{equation*}
This is equal to the congruence class of \(10\) since
\begin{equation*} [10] = \set{10 + 7k \mid k \in \ZZ} = \set{\dots, -11, -4, 3, 10, 17, \dots} \end{equation*}
In fact, the congruence class of \(3\) is equal to the congruence class of any integer that is congruent to \(3\) modulo \(7\text{,}\)
\begin{equation*} \dots = [-4] = [3] = [10] = [17] = \cdots. \end{equation*}
🔗
🔗

Example 5.1.2.7. Congruence classes modulo \(5\).

There are five congruence classes modulo \(5\text{,}\) namely
\begin{align*} [0]_5 \amp = \set{0 + 5k \mid k \in \ZZ} = \set{\dots, -10, -5, 0, 5, 10, \dots} \\ [1]_5 \amp = \set{1 + 5k \mid k \in \ZZ} = \set{\dots, -9, -4, 1, 6, 11, \dots} \\ [2]_5 \amp = \set{2 + 5k \mid k \in \ZZ} = \set{\dots, -8, -3, 2, 7, 12, \dots} \\ [3]_5 \amp = \set{3 + 5k \mid k \in \ZZ} = \set{\dots, -7, -2, 3, 8, 13, \dots} \\ [4]_5 \amp = \set{4 + 5k \mid k \in \ZZ} = \set{\dots, -6, -1, 4, 9, 14, \dots}. \end{align*}
and we have
\begin{equation*} [0]_5\cup [1]_5 \cup [2]_5 \cup [3]_5\cup [4]_5=\ZZ. \end{equation*}
🔗
🔗
The following result says that we can define arithmetic on congruence classes.
🔗

Proof.

  1. Suppose \(a \equiv \ahat \pmod m\) and \(b \equiv \bhat \pmod m\text{.}\) Then there exist integers \(k\) and \(\ell\) such that \(a = \ahat + k m\) and \(b = \bhat + \ell m\text{.}\) We compute
    \begin{equation*} a + b = (\ahat + k m) + (\bhat + \ell m) = (\ahat + \bhat) + m(k + \ell). \end{equation*}
    Since \(k\) and \(\ell\) are integers, \(k + \ell\) is an integer. Thus \(a + b \equiv \ahat + \bhat \pmod m\) by Theorem 5.1.2.3.
    🔗
    🔗
  2. Similarly, we compute
    \begin{equation*} ab = (\ahat + k m)(\bhat + \ell m) = (\ahat \bhat) + m(k\bhat + \ell \ahat + k \ell m). \end{equation*}
    Since \(\ahat\text{,}\) \(\bhat\text{,}\) \(k\text{,}\) \(m\text{,}\) and \(\ell\) are integers, \((k\bhat + \ell \ahat + k \ell m)\) is an integer. Thus \(a b \equiv \ahat \bhat \pmod m\) by Theorem 5.1.2.3.
    🔗
    🔗
🔗
🔗
The result says that we can take any element in the congruence class of \(a\) and add it to any element in the congruence class of \(b\text{,}\) and we will get an element of the congruence class of \(a + b\text{,}\) and the analogous result for multiplication. The division algorithm ensures that each congruence class modulo \(m\) will contain a unique representative \(0\leq a \lt m\text{,}\) so we can transfer the arithmetic on congruence classes to an arithmetic on congruence class representatives.
🔗

Example 5.1.2.9. Arithmetic modulo \(10\).

Suppose \(a \equiv 5 \pmod{10}\) and \(b \equiv 2 \pmod{10}\text{.}\) Then
\begin{equation*} a^2 - b \equiv 5^2 - 2 \equiv 23 \equiv 3 \pmod{10}. \end{equation*}
🔗
🔗

Definition 5.1.2.10.

Let \(m\) be a positive integer. The integers mod \(m\), denoted \(\ZZ_m\text{,}\) as a set is
\begin{equation*} \ZZ_m = \set{0, 1, \dots, m - 1}. \end{equation*}
We endow this set with arithmetic, called modular arithmetic For \(a\) and \(b\) in \(\ZZ_m\text{,}\) we define the sum and product by
\begin{equation*} a \oplus_m b = (a + b) \bmod m \quad \text{and} \quad a \otimes_m b = (ab) \bmod m. \end{equation*}
🔗
🔗

Example 5.1.2.11. Addition and multiplication table modulo \(6\).

We compute the addition and multiplication table for \(\ZZ_6\text{.}\)
\begin{equation*} \begin{array}{|c||c|c|c|c|c|c|c|} \hline \oplus_6 \amp 0 \amp 1 \amp 2 \amp 3 \amp 4 \amp 5\\ \hline \hline 0 \amp 0 \amp 1 \amp 2 \amp 3 \amp 4 \amp 5\\ \hline 1 \amp 1 \amp 2 \amp 3 \amp 4 \amp 5 \amp 0\\ \hline 2 \amp 2 \amp 3 \amp 4 \amp 5 \amp 0 \amp 1\\ \hline 3 \amp 3 \amp 4 \amp 5 \amp 0 \amp 1 \amp 2\\ \hline 4 \amp 4 \amp 5 \amp 0 \amp 1 \amp 2 \amp 3\\ \hline 5 \amp 5 \amp 0 \amp 1 \amp 2 \amp 3 \amp 4\\ \hline \end{array} \quad \begin{array}{|c||c|c|c|c|c|c|c|} \hline \otimes_6 \amp 0 \amp 1 \amp 2 \amp 3 \amp 4 \amp 5\\ \hline \hline 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0\\ \hline 1 \amp 0 \amp 1 \amp 2 \amp 3 \amp 4 \amp 5\\ \hline 2 \amp 0 \amp 2 \amp 4 \amp 0 \amp 2 \amp 4\\ \hline 3 \amp 0 \amp 3 \amp 0 \amp 3 \amp 0 \amp 3\\ \hline 4 \amp 0 \amp 4 \amp 2 \amp 0 \amp 4 \amp 2\\ \hline 5 \amp 0 \amp 5 \amp 4 \amp 3 \amp 2 \amp 1\\ \hline \end{array} \end{equation*}
🔗
🔗
🔗
PrevTopNext