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

发表回复

您的电子邮箱地址不会被公开。