# Random math: 10

Source of most content: Gunhee Cho

# Inverse of Lagrage’s theroem.

$\text{Let } G = < x > \text{ with } o(x)=n < \infty. \text{ Then, } \forall d \mid n, \ \exists! H \leqslant G \text{ s.t.} d = \mid H \mid = \mid < y> \mid = o(y). \nonumber$

Here, $o(x)$ denotes the smallest natural number $n \in \mathbb{N}$ s.t. $x^n =e$. If $\nexists n$, then $o(x)=\infty$.
And $d \mid n$ denotes that $d$ is a divisior of $n$.

## Proof

To prove, we need a lemma: Let $x \in G, a \in \mathbb{Z}, o(x)=n, G=< x >,$ then $\ o(x^a) = \frac{n}{gcd(n,a)}$.
First, fix $d \mid n$.

1. (Existence) : Since $d \mid n, \ \frac{n}{d} \in \mathbb{Z} \leadsto x^{\frac{n}{d}}\in G$. Let $H := < x^{\frac{n}{d}} > \leqslant G$. Then, $\mid H \mid = \mid < x^{\frac{n}{d}} > \mid = o( x^{\frac{n}{d}}) \stackrel{Lem}{=} \frac{n}{gcd(n, n/d)}$. Therefore, there exists $H$ s.t. $\mid H\mid = d$.
2. (Uniqueness) : Let $H’ \leqslant G$ s.t. $\mid H’ \mid = d$. Then, we need to show $H’ = < x^{\frac{n}{d}} >$. By lemma, $d= \mid H’ \mid = \mid < x^m > \mid = o(x^m)=\frac{n}{gcd(n,m)}$ for some $m$, which implies $\frac{n}{d}=gcd(n,m)=ns+mt$ for some $s, t \in \mathbb{Z}$.
• $(\supseteq)$ $x^{\frac{n}{d}}=x^{ns+mt}=x^ns \cdot x^mt = (x^n)^s \cdot (x^m)^t = e \cdot (x^m)^t \in < x^m >$.
• $(\subseteq)$ $m = gcd(n,m)\cdot m’, \ m’\in\mathbb{Z} \leadsto m = \frac{n}{d}\cdot m’$. Thus, $x^m = x^{\frac{n}{d}m’}= (x^{\frac{n}{d}})^{m’} \in < x^{\frac{n}{d}} >$.
$\implies H’=< x^m > = < x^{\frac{n}{d}} > = H$.

### Proof of Lemma

• $(x^a)^{\frac{n}{gcd(n, a)}} = (x^n)^{\frac{a}{gcd(n, a)}} = e^{\frac{a}{gcd(n, a)}} = e.$
• Show that if $(x^a)^m = e$, then $\frac{a}{gcd(n, a)} \leq m$, i.e., $\frac{a}{gcd(n, a)}$ is the smallest natural number $k$ satisfying $x^k = e$.
if $(x^a)^m=e, \ am = nq+r, 0 \leq r \leq q-1 \leadsto r = am -nq$ since $x^n =e$. $x^r = x^{am-nq}=(x^a)^m (x^n)^{-q}=e$ which is a contradiction if $r \ne 0$ since $r < n$, which implies that $n \mid am$. Let $n’ = \frac{n}{gcd(n,a)}, a’ = \frac{a}{gcd(n,a)}$. From $n \mid am$, we can see that $n’ \mid a’m \leadsto n’ \mid m$ since $a’$ and $n’$ is relative prime. Therefore, $m \geq n’ = \frac{n}{gcd(n,a)}$.

$\text{For prime number } p, \text{ quotient group } \mathbb{Z}/p\mathbb{Z} \text{ has no proper subgroup except } \{e\}. \nonumber$

### Proof

Let $\mathbb{Z}/p\mathbb{Z} = < g >, o(g)=p$. If $H \leqslant \mathbb{Z}/p\mathbb{Z}$, then $H=< g^a >$ for some $a \in \mathbb{Z}.$ By lemma, $o(g^a)=\frac{p}{gcd(p,a)}=p$ or $1$. Since this implies $g^{ap}=e$ or $g^{a}=e$, this leads to $a=1$ or $a=0$. Therefore $H= \mathbb{Z}/p\mathbb{Z}$ or $H=\{ e \}$.

# Euler’s Phi function

Def. Define $\varphi: \mathbb{Z} \rightarrow \mathbb{Z} \ (n \mapsto \varphi(n)) =: \{ k\in \mathbb{Z} \mid k=0, \cdots, n-1 \text{ s.t. } gcd(n,k)=1 \}$, which is called Euler’s Phi function.

1. For prime $p$, and natural number $k \in \mathbb{N}, \varphi(p^k)=p^k-p^{k-1}$.
2. $\varphi(mn)=\varphi(m)\varphi(n)$ if $gcd(m,n)=1$.

NB1; $\varphi(n)$ implies the number of generators of $\mathbb{Z}/n\mathbb{Z}$. This is because for $G = < g >, o(g)=n$, $o(g^k)=\frac{n}{gcd(n,k)}=n$ if $gcd(n,k)=1$, i.e., $< g^k > = < g >$.
NB2; $\forall k \in \mathbb{N}, \ \varphi(k)=\varphi(p_1^{m_1} p_2^{m_2}\cdots p_r^{m_r})$ by prime decomposition. This is equivalent to (by (2)) $\varphi(p_1^{m_1})\cdots \varphi(p_r^{m_r})$ $\stackrel{(1)}{=} (p_1^{m_1}-p_1^{m_1 -1})\cdots (p_r^{m_r}-p_r^{m_r-1})=p^{m_1}_1 \cdots p^{m_r}_r \Pi^r _{i=1}(1-\frac{1}{p_i})=k\Pi^r _{i=1}(1-\frac{1}{p_i})$.

# Coset

Def. Given $H \leqslant G, G/H := \{ gH \mid g\in G\}$ is called set of coset, where $gH$ is a coset.

Give a relation $\sim_R$ by $g \sim_R g’ := g’g^{-1} \in H$. $[ g ] = \{g’\in G \mid g \sim_R g’ \} = \{g’ \in G \mid g’g^{-1} \in H \}$. By defining $g’g^{-1}=h \in H \leadsto \{g’\in G \mid g’g^{-1}=h \in H \} = \{hg \mid h \in H \} := Hg$.

We call $Hg$ right coset and $gH$ left coset.

e.g.) $\{ e\} \leqslant G, G/\{e\}= \{g\{e\} \mid g \in G \}=\{ \{g\} \mid g \in G \} \cong \{g \mid g \in G\}=G \leadsto$ $G/\{e\}$ is isomorphic to $G$ $(G/\{e\} \triangleq G$).

## Proposition

$\text{Let, } H \leqslant G, \ g_1, g_2 \in G. \text{ Then, } g_1H=g_2H \Leftrightarrow g_1^{-1}g_2 \in H \Leftrightarrow g_2^{-1}g_1 \in H. \nonumber$

### Proof

1. $(\Rightarrow)$ Let $g_1H=g_2H$. Then, $g_1 e \in g_2 H \leadsto g_1 \in g_2 H \leadsto g_1 = g_2h$ for some $h\in H \leadsto g_2^{-1}g_1=h\in H$.
2. $(\Leftarrow)$ Let $g_1^{-1}g_2 \in H$. Then, $g_1^{-1}g_2 = h’ \in H$ for some $h’ \leadsto g_2 = g_1 h’\leadsto g_2H:= \{ g_2h \mid h \in H\}$$= \{ g_1 h’ h \mid h \in H\}=\{g_1h \mid h \in H\}= g_1H$. (note that $h$ and $h’$ are arbitrary)

$\text{Let, } H \leqslant G, \ g_1, g_2 \in G. \text{ Then, } \forall g \in G, \mid gH \mid = \mid H \mid. \nonumber$

### Proof

Define $f:gH \rightarrow H \ (gh \mapsto h)$. Then, it is enough to show that $f$ is bijective.

1. (injective) If $f(gh_1) = f(gh_2)$, then $h_1 = h_2 \leadsto gh_1=gh_2$.
2. (surjective) For any $h_0 \in H, \ f(gh_0)=h_0$.

# Lagrage’s theroem

$\text{Let } G \text{ be a finite group}, H \leqslant G. \text{ Then, } \mid H \mid \mid \mid G \mid, \text{ i.e., } \mid G \mid \text{ divides } \mid H \mid. \nonumber$

### Proof

Let $G= \sqcup_{g\in G} gH = g_1 H \sqcup \cdots \sqcup g_r H$. Then, $\mid G \mid= \sum_{k=1}^r \mid g_k H \mid = \sum_{k=1}^r \mid H \mid = r \mid H \mid,$ i.e., $\mid G \mid= r \mid H \mid$. Thus, $\mid H \mid \mid \mid G \mid$. Note that I used $\sqcup$ as discrete union.

$\text{If } G \text{ is a group with } \mid G \mid = p, \text{ where } p \text{ is a prime number, then } G \text{ is cyclic}. \nonumber$

### Proof

Take $g \in G \setminus \{e\} \leadsto < g > \leqslant G. \stackrel{Lagrange}{\implies} \mid < g > \mid \mid \mid G \mid$ since $\mid G \mid =p$ and $\mid < g > \mid \geq 2 \leadsto$ $\mid < g > \mid = \mid G \mid \leadsto < g > = G.$