1. Congruence relations and $\mathbb{Z}_{n}$.
Throughout this section let us fix a positive integer $n \in \mathbb{Z}$ (to get reasonable examples further on it is natural to assume also that $n>1)$.
2. Definition 1: Congruence relation modulo $n$
Given fixed nonzero $n$, let us introduce an equivalence relation on $\mathbb{Z}$ as follows:
$$
a \sim b \Longleftrightarrow n \mid(a-b),
$$
i.e., $a$ is equivalent to $b$ if and only if their difference if divisible by $n .$ In this case we will write
$$
a \equiv b \quad \bmod n
$$
‘ $a$ is equivalent to $b$ modulo $n$ ‘.
Problem 1: Verify that this is an equivalence relation.
The equivalence class modulo this equivalence relation is called a congruence class. Clearly numbers $a$ and $b$ are in the same congruence class if and only if $a$ and $b$ have the same remainder under division by $b$, so that the set of equivalence classes is
$$
(\mathbb{Z} / \sim)={[0],[1], \ldots,[n-1]}
$$
where
$$
[a]={a+n k \mid k \in \mathbb{Z}}=a+n \mathbb{Z} .
$$
We will use a special notation for the set of equivalence classes $\mathbb{Z} / \sim$ and denote it
$$
\mathbb{Z}_{n}:={[0],[1], \ldots,[n-1]}
$$
to keep track of our choice of $n$. Another commonly used notation is $\mathbb{Z} / n \mathbb{Z}$.
3. Arithmetics in $\mathbb{Z}_{n}$
So far $\mathbb{Z}{n}$ is only a set consisting of $n$ elements. Our next goal is to introduce addition and multiplication operations on $\mathbb{Z}{n} .$ To this end we will need a simple lemma.
If $a \equiv a^{\prime} \bmod n$ and $b \equiv b^{\prime} \bmod n$, then
$$
\begin{gathered}
(a+b) \equiv\left(a^{\prime}+b^{\prime}\right) \quad \bmod n \
a b \equiv a^{\prime} b^{\prime} \quad \bmod n
\end{gathered}
$$
Proof. We will prove the claim about multiplication. The claim about addition is proved similarly (and is a good exercise).
From the assumptions of the lemma, of know that
$$
a^{\prime}=a+k n \quad b^{\prime}=b+\ln
$$
for some $k, l \in \mathbb{Z}$. Therefore the difference
$$
a^{\prime} b^{\prime}-a b=(a+k n)(b+\ln )-a b=k n b+\ln a+k \ln ^{2}=n(a b+l a+k \ln )
$$
is clearly divisible by $n$, so that $a^{\prime} b^{\prime} \equiv a b \bmod n$. This lemma allows us introduce addition and multiplication on $\mathbb{Z}_{n}$ as follows.
Given two congruence classes $[a]$ and $[b]$ in $\mathbb{Z}_{n}$ we choose representatives $a \in[a]$ and $b \in[b]$ and introduce an operation $\oplus$
$$
$$
and an operation $\odot$
$$
[a] \odot[b]:=[a b]
$$
The above lemma ensures that this definition is correct, i.e., if we had chosen different representatives $a^{\prime} \in[a]$ and $b^{\prime} \in[b]$, we would get the same congruence classes as the results of $\oplus$ and $\odot$ operations. Operations $\oplus$ and $\odot$ satisfy all the axioms $\mathrm{G} 1, \mathrm{G} 2, \mathrm{G} 3, \mathrm{GC}, \mathrm{R} 1, \mathrm{R} 2, \mathrm{R} 3$, i.e.:
G1 $\oplus$ is associative
$\mathrm{G} 2 \oplus$ has neutral element $[0]$
G3 $[a]$ has additive inverse $[-a]$
$\mathrm{GC} \oplus$ is commutative
R1 $\odot$ is associative
$R 2 \odot$ is distributive with respect to $\oplus$
R3 $\odot$ has neutral element $[1]$
which means that the pair $\left(\mathbb{Z}{n}, \oplus\right)$ is a commutative group and the triple $\left(Z{n}, \oplus, \odot\right)$ is a ring.
For this lecture we will keep notations $[a]$ to denote an element of $\mathbb{Z}{n}$ and write $\oplus$ and $\odot$ for addition and multiplication to underline that these are new elements and new operations. However, from the next lecture on, we will write just $a,+$, and simply add ( $\bmod n$ ), if we are considering those in $\mathbb{Z}{n}$.
In $\mathbb{Z}_{5}$ we have
$$
[1] \oplus[4]=[0]
$$
and
$$
\text { [4] } \odot[4]=[1]
$$
Problem 2: Find all elements in $\mathbb{Z}_{16}$ such that $[a] \odot[a]=[1] .$
Multiplication in $\mathbb{Z}_{n}$ has several new features, which are not present in $\mathbb{Z}$.
In $\mathbb{Z}_{7}$ we have $[3] \odot[5]=[1] .$ For this reason, $[5]$ plays the same role as the number $1 / 3$ in $\mathbb{Q}$, i.e., it is multiplicative inverse for 3 .
For instance, if we want to solve equation
$$
[3] \odot y=[5]
$$
in $\mathbb{Z}_{7}$, we can multiply both sides with [5] (which will have the same effect as division by [3]), and get
$$
[5] \odot[3] \odot y=[5] \odot[5]
$$
Using the fact that $[5] \odot[3]=[1]$ and $[5] \odot[5]=[25]=[4]$ in $\mathbb{Z}_{7}$ we conclude
$$
y=[4] .
$$
In $\mathbb{Z}_{6}$ the product of two nonzero elements might be zero:
$$
[2] \odot[3]=[6]=[0] \quad \text { in } \mathbb{Z}_{6} .
$$
The above example motivates us to introduce the following notion.
Congruence class $[a]$ in $\mathbb{Z}_{n}$ is called a unit (or multiplicatively invertible), if there exists a congruence class $[b]$ such that
$$
[a] \odot[b]=[1]
$$
Problem 3: Prove that multiplicative inverse, if exists, unique.
In $\mathbb{Z}_{6}$ congruence classes $[1],[5]$ are invertible
$$
[1] \odot[1]=[1], \quad[5] \odot[5]=[1]
$$
while the remaining classes are not invertible (why?).
NB 1: Caution! In general in $\mathbb{Z}{n}$ one can not cancel nonzero factors from both sides of an identity, for example in $\mathbb{Z}{6}$
$$
[2] \odot[3]=[0]=[2] \odot[0]
$$
while
$$
[3] \neq[0] \text {. }
$$
In the next lecture we will give necessary and sufficient condition under which we can cancel factor $[a]$ in $\mathbb{Z}_{n}$.