Congruences Modulo $n$

Definition 2.1 (Group)   A group is a set $G$ equipped with a binary operation $G \times G \to G$ (denoted by multiplication below) and an identity element $1\in G$ such that:

1. For all $a,b,c\in G$ , we have $(ab)c = a(bc)$ .
2. For each $a\in G$ , we have $1a = a1 = a$ , and there exists $b\in G$ such that $ab=1$ .

Definition 2.1 (Abelian Group)   An abelian group is a group $G$ such that $ab=ba$ for every $a,b\in G$ .

Definition 2.1 (Ring)   A ring $R$ is a set equipped with binary operations $+$ and $\times$ and elements $0,1\in R$ such that $R$ is an abelian group under $+$ , and for all $a,b,c \in R$ we have

• $1a = a1 = a$
• $(ab)c = a(bc)$
• $a(b+c) = ab + ac$ .

If in addition $ab=ba$ for all $a,b\in R$ , then we call $R$ a commutative ring.

In this section we define the ring $\mathbb{Z}/n\mathbb{Z}{}$ of integers modulo $n$ , introduce the Euler $\varphi$ -function, and relate it to the multiplicative order of certain elements of $\mathbb{Z}/n\mathbb{Z}{}$ .

If $a, b\in \mathbb {Z}$ and $n\in\mathbb{N}$ , we say that $a$ is congruent to $b$ modulo $n$ if $n\mid a-b$ , and write $a\equiv b\pmod{n}$ . Let $n\mathbb{Z}=(n)$ be the ideal of $\mathbb {Z}$ generated by $n$ .

Definition 2.1 (Integers Modulo $n$ )   The ring of integers modulo $n$ is the quotient ring $\mathbb{Z}/n\mathbb{Z}{}$ of equivalence classes of integers modulo $n$ . It is equipped with its natural ring structure:

$$(a + n\mathbb{Z}) + (b + n\mathbb{Z}) = (a+b) + n\mathbb{Z}$$

$$(a + n\mathbb{Z}) \cdot (b + n\mathbb{Z}) = (a\cdot b) + n\mathbb{Z}.$$

Example 2.1   For example,

$$\mathbb{Z}/3\mathbb{Z}{} = \{ \{\ldots, -3, 0, 3, \ldots\}, \{\ldots, -2, 1, 4, \ldots\}, \{\ldots, -1, 2, 5, \ldots\}\}$$

SAGE Example 2.1   In SAGE we list the elements of $\mathbb{Z}/n\mathbb{Z}$ as follows:

sage: R = Integers(3)
sage: list(R)
[0, 1, 2]

We use the notation $\mathbb{Z}/n\mathbb{Z}{}$ because $\mathbb{Z}/n\mathbb{Z}{}$ is the quotient of the ring  $\mathbb {Z}$ by the ideal $n\mathbb{Z}$ of multiples of $n$ . Because $\mathbb{Z}/n\mathbb{Z}{}$ is the quotient of a ring by an ideal, the ring structure on  $\mathbb {Z}$ induces a ring structure on $\mathbb{Z}/n\mathbb{Z}{}$ . We often let $a$ or $a\pmod{n}$ denote the equivalence class $a+n\mathbb{Z}$ of $a$ .

Definition 2.1 (Field)   A field $K$ is a ring such that for every nonzero element $a\in K$ there is an element $b\in K$ such that $ab=1$ .

For example, if $p$ is a prime, then $\mathbb{Z}/p\mathbb{Z}{}$ is a field (see Exercise 2.12).

We call the natural reduction map $\mathbb{Z}\to \mathbb{Z}/n\mathbb{Z}{}$ , which sends $a$ to $a+n\mathbb{Z}$ , reduction modulo $n$ . We also say that $a$ is a lift of $a+n\mathbb{Z}$ . Thus, e.g., $7$ is a lift of $1$ mod $3$ , since $7+3\mathbb{Z}= 1+3\mathbb{Z}$ .

We can use that arithmetic in $\mathbb{Z}/n\mathbb{Z}{}$ is well defined is to derive tests for divisibility by $n$ (see Exercise 2.8).

Proposition 2.1   A number $n\in\mathbb{Z}$ is divisible by $3$ if and only if the sum of the digits of $n$ is divisible by $3$ .

Proof. Write

$$n=a+10b+100c+\cdots,$$

where the digits of $n$ are $a$ , $b$ , $c$ , etc. Since $10\equiv 1\pmod{3}$ ,

$$n = a + 10b + 100c+\cdots \equiv a + b + c+\cdots \pmod{3},$$

from which the proposition follows. $\qedsymbol$