Quotient group

Let ${\displaystyle N}$ be a normal subgroup of a group ${\displaystyle G}$ . Define the set ${\displaystyle G\,/\,N}$ to be the set of all left cosets of ${\displaystyle N}$ in ${\displaystyle G}$ . That is, ${\displaystyle G\,/\,N=\left\{aN:a\in G\right\}}$. Since the identity element ${\displaystyle e\in N}$, ${\displaystyle a\in aN}$. Define a binary operation on the set of cosets, ${\displaystyle G\,/\,N}$, as follows. For each ${\displaystyle aN}$ and ${\displaystyle bN}$ in ${\displaystyle G\,/\,N}$, the product of ${\displaystyle aN}$ and ${\displaystyle bN}$, ${\displaystyle (aN)(bN)}$, is ${\displaystyle (ab)N}$. This works only because ${\displaystyle (ab)N}$ does not depend on the choice of the representatives, ${\displaystyle a}$ and ${\displaystyle b}$, of each left coset, ${\displaystyle aN}$ and ${\displaystyle bN}$. To prove this, suppose ${\displaystyle xN=aN}$ and ${\displaystyle yN=bN}$ for some ${\displaystyle x,y,a,b\in G}$. Then

${\textstyle (ab)N=a(bN)=a(yN)=a(Ny)=(aN)y=(xN)y=x(Ny)=x(yN)=(xy)N}$.

This depends on the fact that N is a normal subgroup. It still remains to be shown that this condition is not only sufficient but necessary to define the operation on G/N.

To show that it is necessary, consider that for a subgroup ${\displaystyle N}$ of ${\displaystyle G}$, we have been given that the operation is well defined. That is, for all ${\displaystyle xN=aN}$ and ${\displaystyle yN=bN}$, for ${\displaystyle x,y,a,b\in G,\;(ab)N=(xy)N}$.

Let ${\displaystyle n\in N}$ and ${\displaystyle g\in G}$. Since ${\displaystyle eN=nN}$, we have ${\displaystyle gN=(eg)N=(eN)(gN)=(nN)(gN)=(ng)N}$.

Now, ${\displaystyle gN=(ng)N\Leftrightarrow N=(g^{-1}ng)N\Leftrightarrow g^{-1}ng\in N,\;\forall \,n\in N}$ and ${\displaystyle g\in G}$.

Hence ${\displaystyle N}$ is a normal subgroup of ${\displaystyle G}$ .

It can also be checked that this operation on ${\displaystyle G\,/\,N}$ is always associative, ${\displaystyle G\,/\,N}$ has identity element ${\displaystyle N}$, and the inverse of element ${\displaystyle aN}$ can always be represented by ${\displaystyle a^{-1}N}$. Therefore, the set ${\displaystyle G\,/\,N}$ together with the operation defined by ${\displaystyle (aN)(bN)=(ab)N}$ forms a group, the quotient group of ${\displaystyle G}$ by ${\displaystyle N}$.

Due to the normality of ${\displaystyle N}$, the left cosets and right cosets of ${\displaystyle N}$ in ${\displaystyle G}$ are the same, and so, ${\displaystyle G\,/\,N}$ could have been defined to be the set of right cosets of ${\displaystyle N}$ in ${\displaystyle G}$ .

For example, consider the group with addition modulo 6: ${\displaystyle G=\left\{0,1,2,3,4,5\right\}}$. Consider the subgroup ${\displaystyle N=\left\{0,3\right\}}$, which is normal because ${\displaystyle G}$ is abelian. Then the set of (left) cosets is of size three:

${\displaystyle G\,/\,N=\left\{a+N:a\in G\right\}=\left\{\left\{0,3\right\},\left\{1,4\right\},\left\{2,5\right\}\right\}=\left\{0+N,1+N,2+N\right\}}$.

The binary operation defined above makes this set into a group, known as the quotient group, which in this case is isomorphic to the cyclic group of order 3.

Consider the group of integers ${\displaystyle \mathbb {Z} }$ (under addition) and the subgroup ${\displaystyle 2\mathbb {Z} }$ consisting of all even integers. This is a normal subgroup, because ${\displaystyle \mathbb {Z} }$ is abelian. There are only two cosets: the set of even integers and the set of odd integers, and therefore the quotient group ${\displaystyle \mathbb {Z} \,/\,2\mathbb {Z} }$ is the cyclic group with two elements. This quotient group is isomorphic with the set ${\displaystyle \left\{0,1\right\}}$ with addition modulo 2; informally, it is sometimes said that ${\displaystyle \mathbb {Z} \,/\,2\mathbb {Z} }$ equals the set ${\displaystyle \left\{0,1\right\}}$ with addition modulo 2.

Example further explained...

Let ${\displaystyle \gamma (m)}$ be the remainders of ${\displaystyle m\in \mathbb {Z} }$ when dividing by ${\displaystyle 2}$. Then, ${\displaystyle \gamma (m)=0}$ when ${\displaystyle m}$ is even and ${\displaystyle \gamma (m)=1}$ when ${\displaystyle m}$ is odd.

By definition of ${\displaystyle \gamma }$, the kernel of ${\displaystyle \gamma }$, ${\displaystyle \ker(\gamma )}$ ${\displaystyle =\{m\in \mathbb {Z}$ :\gamma (m)=0\}} , is the set of all even integers.

Let ${\displaystyle H=}$ ${\displaystyle \ker(\gamma )}$. Then, ${\displaystyle H}$ is a subgroup, because the identity in ${\displaystyle \mathbb {Z} }$, which is ${\displaystyle 0}$, is in ${\displaystyle H}$, the sum of two even integers is even and hence if ${\displaystyle m}$ and ${\displaystyle n}$ are in ${\displaystyle H}$, ${\displaystyle m+n}$ is in ${\displaystyle H}$ (closure) and if ${\displaystyle m}$ is even, ${\displaystyle -m}$ is also even and so ${\displaystyle H}$ contains its inverses.

Define ${\displaystyle \mu$ :\mathbb {Z} /H\to \mathbb {Z} _{2}} as ${\displaystyle \mu (aH)=\gamma (a)}$ for ${\displaystyle a\in \mathbb {Z} }$ and ${\displaystyle \mathbb {Z} /H}$ is the quotient group of left cosets; ${\displaystyle \mathbb {Z} /H=\{H,1+H\}}$.

Note that we have defined ${\displaystyle \mu }$, ${\displaystyle \mu (aH)}$ is ${\displaystyle 1}$ if ${\displaystyle a}$ is odd and ${\displaystyle 0}$ if ${\displaystyle a}$ is even.

Thus, ${\displaystyle \mu }$ is an isomorphism from ${\displaystyle \mathbb {Z} /H}$ to ${\displaystyle \mathbb {Z} _{2}}$.

A slight generalization of the last example. Once again consider the group of integers ${\displaystyle \mathbb {Z} }$ under addition. Let n be any positive integer. We will consider the subgroup ${\displaystyle n\mathbb {Z} }$ of ${\displaystyle \mathbb {Z} }$ consisting of all multiples of ${\displaystyle n}$. Once again ${\displaystyle n\mathbb {Z} }$ is normal in ${\displaystyle \mathbb {Z} }$ because ${\displaystyle \mathbb {Z} }$ is abelian. The cosets are the collection ${\displaystyle \left\{n\mathbb {Z} ,1+n\mathbb {Z} ,\;\ldots ,(n-2)+n\mathbb {Z} ,(n-1)+n\mathbb {Z} \right\}}$. An integer ${\displaystyle k}$ belongs to the coset ${\displaystyle r+n\mathbb {Z} }$, where ${\displaystyle r}$ is the remainder when dividing ${\displaystyle k}$ by ${\displaystyle n}$. The quotient ${\displaystyle \mathbb {Z} \,/\,n\mathbb {Z} }$ can be thought of as the group of "remainders" modulo ${\displaystyle n}$. This is a cyclic group of order ${\displaystyle n}$.

The cosets of the fourth roots of unity N in the twelfth roots of unity G.

The twelfth roots of unity, which are points on the complex unit circle, form a multiplicative abelian group ${\displaystyle G}$, shown on the picture on the right as colored balls with the number at each point giving its complex argument. Consider its subgroup ${\displaystyle N}$ made of the fourth roots of unity, shown as red balls. This normal subgroup splits the group into three cosets, shown in red, green and blue. One can check that the cosets form a group of three elements (the product of a red element with a blue element is blue, the inverse of a blue element is green, etc.). Thus, the quotient group ${\displaystyle G\,/\,N}$ is the group of three colors, which turns out to be the cyclic group with three elements.

Consider the group of real numbers ${\displaystyle \mathbb {R} }$ under addition, and the subgroup ${\displaystyle \mathbb {Z} }$ of integers. Each coset of ${\displaystyle \mathbb {Z} }$ in ${\displaystyle \mathbb {R} }$ is a set of the form ${\displaystyle a+\mathbb {Z} }$, where ${\displaystyle a}$ is a real number. Since ${\displaystyle a_{1}+\mathbb {Z} }$ and ${\displaystyle a_{2}+\mathbb {Z} }$ are identical sets when the non-integer parts of ${\displaystyle a_{1}}$ and ${\displaystyle a_{2}}$ are equal, one may impose the restriction ${\displaystyle 0\leq a<1}$ without change of meaning. Adding such cosets is done by adding the corresponding real numbers, and subtracting 1 if the result is greater than or equal to 1. The quotient group ${\displaystyle \mathbb {R} \,/\,\mathbb {Z} }$ is isomorphic to the circle group, the group of complex numbers of absolute value 1 under multiplication, or correspondingly, the group of rotations in 2D about the origin, that is, the special orthogonal group ${\displaystyle {\mbox{SO}}(2)}$. An isomorphism is given by ${\displaystyle f(a+\mathbb {Z} )=\exp(2\pi ia)}$ (see Euler's identity).

If ${\displaystyle G}$ is the group of invertible ${\displaystyle 3\times 3}$ real matrices, and ${\displaystyle N}$ is the subgroup of ${\displaystyle 3\times 3}$ real matrices with determinant 1, then ${\displaystyle N}$ is normal in ${\displaystyle G}$ (since it is the kernel of the determinant homomorphism). The cosets of ${\displaystyle N}$ are the sets of matrices with a given determinant, and hence ${\displaystyle G\,/\,N}$ is isomorphic to the multiplicative group of non-zero real numbers. The group ${\displaystyle N}$ is known as the special linear group ${\displaystyle {\mbox{SL}}(3)}$.

Consider the abelian group ${\displaystyle \mathbb {Z} _{4}=\mathbb {Z} \,/\,4\mathbb {Z} }$ (that is, the set ${\displaystyle \left\{0,1,2,3\right\}}$ with addition modulo 4), and its subgroup ${\displaystyle \left\{0,2\right\}}$. The quotient group ${\displaystyle \mathbb {Z} _{4}\,/\,\left\{0,2\right\}}$ is ${\displaystyle \left\{\left\{0,2\right\},\left\{1,3\right\}\right\}}$. This is a group with identity element ${\displaystyle \left\{0,2\right\}}$, and group operations such as ${\displaystyle \left\{0,2\right\}+\left\{1,3\right\}=\left\{1,3\right\}}$. Both the subgroup ${\displaystyle \left\{0,2\right\}}$ and the quotient group ${\displaystyle \left\{\left\{0,2\right\},\left\{1,3\right\}\right\}}$ are isomorphic with ${\displaystyle \mathbb {Z} _{2}}$.

Consider the multiplicative group ${\displaystyle G=(\mathbb {Z} _{n^{2}})^{\times }}$. The set ${\displaystyle N}$ of ${\displaystyle n}$th residues is a multiplicative subgroup isomorphic to ${\displaystyle (\mathbb {Z} _{n})^{\times }}$. Then ${\displaystyle N}$ is normal in ${\displaystyle G}$ and the factor group ${\displaystyle G\,/\,N}$ has the cosets ${\displaystyle N,(1+n)N,(1+n)2N,\;\ldots ,(1+n)n-1N}$. The Paillier cryptosystem is based on the conjecture that it is difficult to determine the coset of a random element of ${\displaystyle G}$ without knowing the factorization of ${\displaystyle n}$.