Skip to main content
Mathematics LibreTexts

1.4: The Integers modulo m

  1. Last updated
  2. Save as PDF
  • Page ID
    82460

    • \( \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}}\)

    Learning Objectives

    In this section, we'll seek to answer the questions:

    • What are equivalence relations?
    • What is congruence modulo \(m\text{?}\)
    • How does arithmetic in \(\mathbb{Z}_m\) compare to arithmetic in \(\mathbb{Z}\text{?}\)

    The foundation for our exploration of abstract algebra is nearly complete. We need the basics of one more "number system" in order to appreciate the abstract approach developed in subsequent chapters. To build that number system, a brief review of relations and equivalence relations is required. Recall that given sets \(S\) and \(T\text{,}\) the Cartesian product of \(S\) with \(T\text{,}\) denoted \(S\times T\) ("\(S\) cross \(T\)"), is the set of all possible ordered pairs whose first element is from \(S\) and second element is from \(T\text{.}\) Symbolically,

    \begin{equation*} S\times T = \{(s,t) : s\in S, \ t\in T \}. \end{equation*}

    Definition: Relation

    Let \(S\) be a nonempty set. A relation \(R\) on \(S\) is a subset of \(S\times S\text{.}\) If \(x,y\in S\) such that \((x,y)\in R\text{,}\) we usually write \(xRy\) and say that \(x\) and \(y\) are related under \(R\).

    The notion of a relation as presented above is extremely open-ended. Any subset of ordered pairs of \(S\times S\) describes a relation on the set \(S\text{.}\) Of course, some relations are more meaningful than others; the branch of mathematics known as order theory studies order relations (such as the familiar \(\lt\)). Our focus will be on equivalence relations, which isolate the important features of \(=\text{.}\)

    Definition: Equivalence Relation

    Let \(S\) be a nonempty set. We say a relation \(\sim\) on \(S\) is an equivalence relation if the following properties hold:

    • \(\sim\) is reflexive: if \(a\in S\text{,}\) then \(a\sim a\text{.}\)
    • \(\sim\) is symmetric: if \(a,b\in S\) with \(a\sim b\text{,}\) then \(b\sim a\text{.}\)
    • \(\sim\) is transitive: if \(a,b,c\in S\) with \(a\sim b\) and \(b\sim c\text{,}\) then \(a\sim c\text{.}\)

    Given \(x\in S\text{,}\) the set

    \begin{equation*} \overline{x} = \{y\in S: x\sim y\} \end{equation*}

    is called the equivalence class of\(x\). Any element \(z\in \overline{x}\) is called a representative of the equivalence class.

    Activity 1.4.1

    Prove that “has the same birthday as” is an equivalence relation on the set \(P\) of all people.

    Exploration 1.4.1

    What other relations can you think of? Write down one example and one non-example of an equivalence relation.

    Activity 1.4.2

    Prove that \(\le\) is not an equivalence relation on \(\mathbb{Z}\text{.}\)

    For our purposes, a particularly important equivalence relation is congruence modulo \(m\) on the set of integers.

    Definition: is Congruent to ... Modulo

    Let \(a,b\in \mathbb{Z}\) and \(m \in \mathbb{N}\text{,}\) \(m > 1\text{.}\) We say \(a\) is congruent to \(b\) modulo \(m\) if \(m\mid a-b\text{.}\) We write \(a \equiv b\mod m\text{.}\)

    Activity 1.4.3

    Justify the following congruences.

    1. \(\displaystyle 18 \equiv 6\mod 12\)
    2. \(\displaystyle 47 \equiv 8\mod 13\)
    3. \(\displaystyle 71 \equiv 1\mod 5\)
    4. \(\displaystyle 21 \equiv -1 \mod 11\)
    5. \(\displaystyle 24 \equiv 0\mod 6\)
    Theorem 1.4.1

    Given an integer \(m > 1\text{,}\) congruence modulo \(m\) is an equivalence relation on \(\mathbb{Z}\text{.}\)

    Exploration 1.4.2

    Find all of the equivalence classes of \(\mathbb{Z}_5\) and \(\mathbb{Z}_7\text{.}\)

    Theorem 1.4.2

    Let \(a,b, c,d\in \mathbb{Z}\) and \(m > 1\) such that \(a\equiv c\mod m\) and \(b\equiv d\mod m\text{.}\) Then \(a+b \equiv c + d \mod m\text{.}\)

    Theorem 1.4.3

    Let \(a,b, c,d\in \mathbb{Z}\) and \(m > 1\) such that \(a\equiv c\mod m\) and \(b\equiv d\mod m\text{.}\) Then \(ab \equiv c d\mod m\text{.}\)

    Definition: Well-Defined

    Let \(S\) be a set and \(\sim\) an equivalence relation on \(S\text{.}\) Then a statement \(P\) about the equivalence classes of \(S\) is well-defined if the representative of the equivalence class does not matter. That is, whenever \(\overline{x} = \overline{y}\text{,}\) \(P(\overline{x}) = P(\overline{y})\text{.}\)

    The previous exercises justify the following definitions.

    Definition: Modulo

    Let \(m > 1\) and \(a,b\in \mathbb{Z}_m\text{.}\) Then the following are well-defined operations on the equivalence classes:

    1. Addition modulo \(m\): \(\overline{a} + \overline{b} := \overline{a+b}\text{.}\)
    2. Multiplication modulo \(m\): \(\overline{a}\cdot \overline{b} := \overline{a\cdot b}\text{.}\)

    Most elementary propositions about \(\mathbb{Z}_m\) can be recast as statements about \(\mathbb{Z}\text{.}\) For instance, in proving Theorem 1.4.2 you likely proved that if \(m|a-c\) and \(m|b-d\) that \(m|(a+b)-(c+d)\text{.}\) However, as the statements become more complex, repeatedly reshaping statements about \(Z_m\) as statements about \(\mathbb{Z}\) becomes cumbersome and unhelpful. Instead, you are encouraged to become comfortable doing arithmetic modulo \(m\) or, put another way, arithmetic with the equivalence classes of \(\mathbb{Z}_m\) as defined in Definition: Modulo.

    Activity 1.4.4

    Without passing back to \(\mathbb{Z}\text{,}\) find the smallest nonnegative integer representative of the resulting equivalence classes.

    1. \(\overline{5}+\overline{11}\) in \(\mathbb{Z}_{9}\)
    2. \(\overline{-3}+\overline{-3}\) in \(\mathbb{Z}_{6}\)
    3. \(\overline{8}\cdot\overline{3}\) in \(\mathbb{Z}_{19}\)
    4. \(\overline{-1}\cdot(\overline{3}+\overline{8})\) in \(\mathbb{Z}_{7}\)
    5. \(\overline{3}\cdot(\overline{5}^2+\overline{3}^3)\) in \(\mathbb{Z}_{20}\)

    In the remainder of this section, we investigate fundamental properties of arithmetic in \(\mathbb{Z}_m\text{.}\)

    Investigation 1.4.1

    Let \(\overline{a},\overline{b},\overline{c}\in \mathbb{Z}_m\) with \(\overline{c}\ne\overline{0}\) and \(m > 1\text{.}\) If \(\overline{a}\cdot \overline{c} = \overline{b}\cdot \overline{c}\text{,}\) is it true that \(\overline{a} = \overline{b}\text{?}\) If so, prove it. If not, find an example of when the statement fails to hold.

    Theorem 1.4.4

    Let \(a,b,c\text{,}\) and \(m\) be integers with \(m > 1\) and \(\gcd(c,m)=1\text{.}\) Then there is some \(x\in \mathbb{Z}\) such that \(\overline{c} \overline{x} = \overline{1}\text{.}\)

    Conclude that if \(\overline{a} \cdot\overline{c} = \overline{b}\cdot\overline{c}\) in \(\mathbb{Z}_m\) that \(\overline{a} = \overline{b}\text{.}\)

    Theorem 1.4.5

    Let \(p\in \mathbb{N}\) be prime and \(\overline{a},\overline{b},\overline{c}\in \mathbb{Z}_p\) such that \(\overline{c}\ne \overline{0}\text{.}\) Then

    1. there is some \(\overline{x}\in \mathbb{Z}_p\) such that \(\overline{c}\cdot \overline{x} = \overline{1}\text{;}\) and,
    2. if \(\overline{a} \cdot\overline{c} = \overline{b}\cdot\overline{c}\text{,}\) \(\overline{a} = \overline{b}\text{.}\)

    This page titled 1.4: The Integers modulo m is shared under a CC BY-SA 4.0 license and was authored, remixed, and/or curated by Michael Janssen & Melissa Lindsey via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.