Congruent Classes

Def Congruent Modulo We say that two integers $a$ and $b$ are congruent modulo $n$ if they give the same residue upon devision by $n$. All the following are equivalent:

$$a\equiv b(\mathrm{mod}n)⟺a-b\in n\mathbb{Z}$$

Prop Congruent modulo is an equivalence relation.

Def Congruent Class The congruent class of an integer $a$ modulo an integer $n>1$ is the set of all integers such that $x\equiv a\mathrm{mod}n$: $[a]=\{x\in \mathbb{Z}\mid x\equiv a\mathrm{mod}n\}$Prop Congruent class is an equivalence class.

Def $({\mathbb{Z}}_n,+)$ Define the group of $n$-congruent class with $[a]+[b]:=[a+b]$:

$${\mathbb{Z}}_n:=\{[0],[1],\cdot \cdot \cdot ,[n-1]\}=\{a+n\mathbb{Z}\mid a\in \mathbb{Z}\}$$

Prop ${\mathbb{Z}}_n$ is a cyclic group.

Def $({\mathbb{Z}}_n^{\times },\cdot )$ Let $n\in \mathbb{N}$. Define with $[a]\cdot [b]:=[a\cdot b]$

$${\mathbb{Z}}_n^{\times }:=\{[k]\mid (k,n)=1\}\subset {\mathbb{Z}}_n$$

Prop ${\mathbb{Z}}_n^{\times }$ is a group. Proof For all $[a],[b],[c]\in {\mathbb{Z}}_n^{\times }$, we have

$$([a][b])[c]=[abc]=[a][bc]=[a]([b][c])$$

And exists $[1]$ as an identity as $[a][1]=[a]$. Since there exist integers $x,y\in \mathbb{Z}$ such that $ax+yn=1$ which by taking residue modulo gives $[a][x]=[x][a]=[1]$ e.g. ${\mathbb{Z}}_8^{\times }=\{[1],[3],[5],[7]\}\cong K_4$

Prop ${\mathbb{Z}}_n^{\times }\cong \mathrm{Aut}({\mathbb{Z}}_n)$

Def Multiplicative Order Let $a$ be an integer number coprime to a prime number $p$. The multiplicative order of $a$ modulo $p$ or $[a]$ is the least positive integer $d$ such that $a^d\equiv 1\mathrm{mod}p$. The multiplicative order is equivalent to the order of $[a]$ in group ${\mathbb{Z}}_p^{\times }$.

Def Euler $\phi$-Function Let $n\in \mathbb{N}$. Euler $\phi$ function is defined to be:

$$\phi (n)=|\{1\le k\le n\mid (n,k)=1\}|=|Z_n^{\times }|$$