Skip to main content

Rings with Inquiry: An inquiry-oriented introduction to ring theory.

Michael Janssen, Melissa Lindsey

Section 1.4 The Integers modulo \(m\)

Guiding Questions.

In this section, we’ll seek to answer the questions:
  • What are equivalence relations?
  • What is congruence modulo \(m\text{?}\)
  • How does arithmetic in \(\Z_m\) compare to arithmetic in \(\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 = \setof{(s,t)}{s\in S, \ t\in T}. \end{equation*}

Definition 1.4.1.

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
 1 
en.wikipedia.org/wiki/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 1.4.2.

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} = \setof{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.2.

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

Activity 1.4.3.

Prove that \(\le\) is not an equivalence relation on \(\Z\text{.}\)
For our purposes, a particularly important equivalence relation is congruence modulo \(m\) on the set of integers.

Definition 1.4.3.

Let \(a,b\in \Z\) and \(m \in \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.4.

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\)
The set of equivalence classes of \(\Z\) under the equivalence relation congruence modulo \(m\) is called the integers modulo \(m\), and is denoted \(\Z_m\) (pronounced "Z mod m").

Exploration 1.4.5.

List the elements of \(\Z_5\) and \(\Z_7\text{.}\)

Definition 1.4.7.

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

Let \(m > 1\) and \(\overline{a},\overline{b}\in \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 \(\Z_m\) can be recast as statements about \(\Z\text{.}\) For instance, in proving Theorem 1.4.5 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 \(\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 \(\Z_m\) as defined in Definition 1.4.8.

Activity 1.4.6.

Without passing back to \(\Z\text{,}\) find the smallest nonnegative integer representative of the resulting equivalence classes.
  1. \(\overline{5}+\overline{11}\) in \(\Z_{9}\)
  2. \(\overline{-3}+\overline{-3}\) in \(\Z_{6}\)
  3. \(\overline{8}\cdot\overline{3}\) in \(\Z_{19}\)
  4. \(\overline{-1}\cdot(\overline{3}+\overline{8})\) in \(\Z_{7}\)
  5. \(\overline{3}\cdot(\overline{5}^2+\overline{3}^3)\) in \(\Z_{20}\)
In the remainder of this section, we investigate fundamental properties of arithmetic in \(\Z_m\text{.}\)

Investigation 1.4.7.

Let \(\overline{a},\overline{b},\overline{c}\in \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.
PrevTopNext