## Algebra - Group Theory

### 2. Modulo system

• Definition 2.1: Consider the set of integers, $\mathbb{Z}$. We divide $\mathbb{Z}$ into $n$ classes $(n \in \mathbb{Z}^+)$ and this system is called modulo system.

• Definition 2.2: Let $a,b \in \mathbb{Z}$ and Let $n$ be fixed ($n \in \mathbb{Z}^+$). Then we define $a\oplus_n b=r$ where $0 \leq r <n$ called addition modulo n.

• Definition 2.3: Let $a,b \in \mathbb{Z}$ and Let $n$ be fixed ($n \in \mathbb{Z}^+$). Then we define $a\otimes_n b=r$ where $0 \leq r <n$ called multiplication modulo n.

• Definition 2.4: Let $n>0$ be fixed be fixed integer. Let $a$ and $b$ be two integers, then we define $a\equiv b($mod$n)$(read as $a$ is congruent to $b$ modulo $n$) if and only if $n|(a-b)$.

• Let $A$ be a set and $a,b,c \in A$. Relation $R$ defined on $A$ is said to be equivalence relation if the following holds.
(1.) Reflexive: $aRa$ $\forall$ $a \in A$
(2.) Symmetric: $aRb \Rightarrow bRa$ $\forall$ $a,b \in A$
(3.) Transitive: $aRb$ and $bRc$ $\Rightarrow$ $aRc$ $\forall$ $a,b \in A$

• Theorem 2.1: The set $\{0,1,2,3,......,(n-1)\}$ is an abelian group under addition modulo $n$.
Proof: Let $\mathbb{Z}_n=$ $\{0,1,2,3,......,(n-1)\}$. Let $a,b,c \in \mathbb{Z}_n$.
(1.) Closure law: Let $a,b \in \mathbb{Z}_n$ then by the definition of addition modulo $n$, we have $a\oplus_n b=r$ where $0\leq r <n$. Clearly $r \in \mathbb{Z}_n$ and so $a \oplus_n b \in \mathbb{Z}_n$.
(2.) Associative law: Since the associative law holds in $\mathbb{Z}$, it will hold in $\mathbb{Z}_n$. Hence $a\oplus_n (b \oplus_n c)=(a \oplus_n b)\oplus_n c$.
(3.) Existence of identity: $\exists$ $0 \in \mathbb{Z}_n$ such that $a\oplus_n 0=0\oplus_n a=a$ $\forall$ $a \in \mathbb{Z}_n$.
(4.) Existence of inverse: For each $a \in \mathbb{Z}_n$ $\exists$ $n-a \in \mathbb{Z}_n$ such that $a\oplus_n (n-a)=(n-a) \oplus_n a=0$.
(5.) Commutative law: Since the commutative law holds in $\mathbb{Z}$, it will hold in $\mathbb{Z}_n$. Hence $a\oplus_n b=b\oplus_n a$.
$\therefore$ $(\mathbb{Z}_n,\oplus_n)$ is an finite abelian group of order $n$. $\blacksquare$

• Theorem 2.2: The set $\{1,2,3,.....,(p-1)\}$ where $p$ is prime is an abelian group under multiplication modulo $p$.
Proof: Let $\mathbb{Z}_p=$ $\{1,2,3,......,(p-1)\}$. Let $a,b,c \in \mathbb{Z}_p$.
(1.) Closure law: Let $a,b \in \mathbb{Z}_p$ then by the definition of multiplication modulo $n$, we have $a\otimes_p b =r$ where $0\leq r<p$. Clearly $r \in \mathbb{Z}_p$ and so $a\otimes_p b \in \mathbb{Z}_p$.
(2.) Associative law: Since the associative law holds in $\mathbb{Z}$, it will hold in $\mathbb{Z}_p$. Hence $a\otimes_p (b \otimes_p c)=(a \otimes_p b)\otimes_p c$.
(3.) Existence of identity: $\exists$ $1 \in \mathbb{Z}_p$ such that $a\otimes_p 1=1\otimes_p a=a$ $\forall$ $a \in \mathbb{Z}_p$.
(4.) Existence of inverse: Let $a \in \mathbb{Z}_p$ then $a^{-1} \in \mathbb{Z}_p$ is the inverse of $a$ if $a\otimes_p a^{-1}=a^{-1}\otimes_p a=1$.
$a\otimes_p a^{-1}=1$ if $aa^{-1}\equiv 1$mod$(p)$. Since $p$ is prime, $aa^{-1}\equiv 1$mod$(p)$ has unique solution. So for each $a \in \mathbb{Z}_p$ $\exists$ unique $a^{-1} \in \mathbb{Z}_p$ such that $aa^{-1}\equiv 1$mod$(p)$ $\Rightarrow$ $a\otimes_p a^{-1}=1$
(5.) Commutative law: Since the commutative law holds in $\mathbb{Z}$, it will hold in $\mathbb{Z}_p$. Hence $a\otimes_p b=b\otimes_p a$.
$\therefore$ $(\mathbb{Z}_p,\otimes_p)$ is an finite abelian group of order $(p-1)$. $\blacksquare$

• Theorem 2.3: The relation congruence modulo $n$ is an equivalence relation on $\mathbb{Z}$.
Proof:
(1.) Reflexive: Since, $n|0 \Rightarrow n|a-a \Rightarrow$ $a\equiv a($mod$n)$.
(2.) Symmetric: Let $a\equiv b($mod$n)$ then $n|a-b \Rightarrow n|-(a-b) \Rightarrow n|b-a$ and so $b\equiv a($mod$n)$.
(3.) Transitive: Let $a\equiv b($mod$n)$ and $b\equiv c($mod$n)$. Since $a\equiv b($mod$n)$ $\Rightarrow n|a-b$ and $b\equiv c($mod$n)$ $\Rightarrow n|b-c$. Now $n|a-b$ and $n|b-c$ $\Rightarrow n|a-b+b-c \Rightarrow n|a-c$ and so $a\equiv c($mod$n)$. $\blacksquare$