Skip to content

# 抽象代数作业代写| Congruence relations. Ring Z_n

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.

4. Lemma 1

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.

5. Definition 2

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}$.

6. Example 1

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}$.

7. Example 2

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] .$$

8. Example 3

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.

9. Definition 3

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.

10. Example 4

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}$.