32 Cosets and Lagrange's Theorem

#todo/school : Try problems Section 3.2: 1, 4, 5, 8, 11, 16, 19, 22, 23 📅 2025-02-14 ✅ 2025-02-17

1

Question

Which of the following are permissible Order (Groups) for Subgroups of a Group of order 120: 1, 2, 5, 7, 9, 15, 60, 240?

Proof

Using Lagrange's Divisibility Theorem of Order of Subgroups, we must have $| H |$ divide $| G | = 120$ . Thus, any candidate must be a factor of 120. That means that the follow work/don't work as $120 = 1 \cdot 2^{3} \cdot 3 \cdot 5$ :

☐

4

Question

Show that if $| G | = p q$ for some primes $p, q$ (not necessarily distinct) then either $G$ is an Abelian Group or $Z (G) = 1$ (see Center).

Proof

Say $| G | = p q$ . If $Z (G) = 1$ then we are done so assume $Z (G) \neq 1$ . Notice that since $Z (G) \neq 1$ then $\exists z \in Z (G)$ where $z$ is not the identity. Then consider the subgroup $⟨ z ⟩$ . Notice it's not the identity so then it has some order $| ⟨ z ⟩ | = n > 1$ .

Now by Lagrange's Divisibility Theorem of Order of Subgroups, then $| ⟨ z ⟩ |$ divides $| G | = p q$ . But since these are prime factors then either $| ⟨ z ⟩ | = p$ or $| ⟨ z ⟩ | = q$ . Without loss of generality, say $| ⟨ z ⟩ | = p$ . Since this is prime, then by Prime Order Groups are Cyclic and Z_p then it is cyclic. Furthermore we know that since $| \frac{G}{Z (G)} | = \frac{| G |}{| Z (G) |} = \frac{p q}{p} = q$ is prime (for more see Index (Groups)) then it itself is cyclic, so then by 31 Quotient Groups and Homomorphisms#36 then $G$ is abelian.

☐

5

Question

Let $H \leq G$ (see Subgroup) and fix some element $g \in G$ .
a. Prove that $g H g^{- 1} \leq G$ and $| g H g^{- 1} | = | H |$ (see Order (Groups))
b. Deduce that if $n \in Z^{+}$ and $H$ is the unique subgroup of $G$ of order $n$ then $H ⊴ G$ .

Proof

a. To show $g H g^{- 1} \leq G$ , clearly it's already a subset. Let $h_{1}, h_{2} \in g H g^{- 1}$ , so then $h_{1} = g h_{1}^{'} g^{- 1}$ and $h_{2} = g h_{2}^{'} g^{- 1}$ . We want to show that $h_{1} h_{2}^{- 1} \in g H g^{- 1}$ :

\begin{aligned} h_{1} h_{2}^{- 1} \in g H g^{- 1} & ⟺ \exists h \in H (g h g^{- 1} = h_{1} h_{2}^{- 1}) \\ ⟺ g h g^{- 1} = (g h_{1}^{'} g^{- 1}) (g h_{2}^{'} g^{- 1})^{- 1} \\ ⟺ g h g^{- 1} = (g h_{1}^{'} g^{- 1}) (g h_{2}^{' - 1} g^{- 1}) \\ ⟺ g h g^{- 1} = g h_{1}^{'} h_{2}^{' - 1} g^{- 1} \\ ⟺ h = h_{1}^{'} h_{2}^{' - 1} \end{aligned}

Thus choosing $h = h_{1}^{'} h_{2}^{' - 1} \in H$ by $H \leq G$ will give us the required condition for $g H g^{- 1} \leq G$ . To get that the orders are the same, use Lagrange's Divisibility Theorem of Order of Subgroups to get that $| g H g^{- 1} | = | H |$ I claim that $φ : g H g^{- 1} \to H$ such that $g h g^{- 1} \mapsto h$ is a bijection:

Injective: Let $φ (g h_{1} g^{- 1}) = φ (g h_{2} g^{- 1})$ . Then $h_{1} = h_{2}$ by definition.
Surjective: Let $h \in H$ . Then choose $g h g^{- 1}$ as then $φ (g h g^{- 1}) = h$ .
Thus then $| g H g^{- 1} | = | H |$ .

b. Suppose $n \in Z^{+}$ where $| H | = n$ . Using (a) then $| g H g^{- 1} | = | H | = n = | G |$ for any $g \in G$ . But since $H$ is the unique subgroup and $| g H g^{- 1} | = | H |$ then $g H g^{- 1} = H$ for all $g \in G$ . This is the Equivalences for Normal Subgroups, so then $H ⊴ G$ .

☐

8

Question

Prove that if $H, K$ are finite Subgroups of $G$ whose orders are relatively prime then $H \cap K = 1$ .

Proof

Let $a \in H \cap K$ . Then by Lagrange's Divisibility Theorem of Order of Subgroups then $| ⟨ a ⟩ |$ divides $| H |$ and $| K |$ . Now, because $| H |$ and $| G |$ are relatively prime, then $| ⟨ a ⟩ | = 1$ (if it wasn't, then they both share some factor, which is composed by some prime). Thus every generator of $H \cap K$ is just the identity, so then $H \cap K = {1}$ and thus $| H \cap K | = 1$ .

☐

11

Question

Let $H \leq K \leq G$ . Prove that $| G : H | = | G : K | \cdot | K : H |$ (see Index (Groups)).

Proof

Notice using Lagrange's Divisibility Theorem of Order of Subgroups that $| H |$ divides $| K |$ divides $| G |$ where:

| K | = (# cosets of H in K) | H | = | K : H | | H |

similarly:

| G | = | G : K | | K | = | G : K | | K : H | | H |

Thus since $| G : H | = \frac{| G |}{| H |}$ then:

\Rightarrow | G : H | = \frac{| G |}{| H |} = \frac{| G : K | | K : H | | H |}{| H |} = | G : K | | K : H |

as desired.

☐

16

Question

Use Lagrange's Divisibility Theorem of Order of Subgroups in the multiplicative group ${(\frac{Z}{p Z})}^{\times}$ to prove Fermat's Little Theorem: if $p$ is a prime then $a^{p} \equiv a mod p$ for all $a \in Z$ .

Proof

Let $p$ be a prime and $a \in Z$ . Because Prime Order Groups are Cyclic and Z_p then our multiplicative group is a Cyclic Group and of order $p - 1$ .

Now if $a | p$ then notice that $a^{p}$ is still a multiple of $p$ (inductively) so then it is equivalent to $0 mod p$ , just as described in the theorem.

If instead $a ∤ p$ then $a mod p$ is equivalent to some $a^{'} \in {(\frac{Z}{p Z})}^{\times}$ . Since it is cyclic, then $a^{'} \neq 0$ is a valid generator!. Thus it must be order $p - 1$ , suggesting that $a^{' p - 1} = 1$ . Multiplying both sides by $a^{'}$ gives that $a^{' p} \equiv a^{'} mod p$ . But since $a mod p \equiv a^{'} mod p$ then:

a^{p} \equiv a^{' p} \equiv a^{'} mod p \equiv a mod p

as desired.

☐

19

Question

Prove that if $N$ is a Normal Subgroup of the finite group $G$ and $gcd (| N |, | G : N |) = 1$ (see Index (Groups)) then $N$ is the unique subgroup of $G$ of order $| N |$ .

Proof

Suppose $N ⊴ G$ with $G$ being finite. Suppose also $gcd (| N |, | G : N |) = 1$ so they are coprime. That means that $| N |$ and $\frac{| G |}{| N |}$ are coprime.

We just want to show that any other subgroup $N^{'} \leq G$ where $| N^{'} | = | N |$ then $N^{'} = N$ .

Notice then that $N^{'} N$ is a subgroup as $N$ is normal. But then:

| N^{'} N | = \frac{| N^{'} | | N |}{| N^{'} \cap N |} = \frac{| N |^{2}}{| N^{'} \cap N |}

Let $k = \frac{| N |}{| N^{'} \cap N |}$ . Then $| N^{'} N | = | N | k$ . Then:

| G : N^{'} N | = \frac{| N^{'} N |}{| G |} = \frac{| N |^{2}}{| G | | N^{'} \cap N |} = \frac{| N |}{| G |} k = | G : N | k

But look! That will contradict our $gcd$ requirements as:

gcd (| N |, | G : N |) = 1 \neq k = gcd (| N^{'} N |, | G : N^{'} N |)

Thus then $k = 1$ per our requirement, but then that means that $| N | = | N^{'} \cap N | = | N^{'} | = | N^{'} N |$ but that can only happen if $N$ and $N^{'}$ are the same.

☐

22

Question

Use Lagrange's Divisibility Theorem of Order of Subgroups in the multiplicative group ${(\frac{Z}{n Z})}^{\times}$ to prove Euler's Theorem: $a^{φ (n)} \equiv 1 mod n$ for every $a \in Z$ that's relatively prime to $n$ , where $φ$ denotes the Euler-Totient Function.

Proof

Let $a \in Z$ be relatively prime to $n$ . Consider the subgroup generated by $a$ , namely $⟨ a ⟩$ . Then since $⟨ a ⟩ \leq G$ (here use $G = (\frac{Z}{n Z})^{\times}$ for simplicity) then by Lagrange's Divisibility Theorem of Order of Subgroups then $| ⟨ a ⟩ | = | a | = | G | \cdot | G : ⟨ a ⟩ |$ .

But here the order of $G$ is actually $φ (n)$ , the Euler Totient function, since for any prime $p < n$ then $p$ is an element of $G$ , while any composite number $q$ is made up of multiplicative elements of the primes and thus can be ignored as a unique element. Hence, $φ (n) = | G |$ .

Thus notice:

| a | = φ (n) \cdot | G : ⟨ a ⟩ |

But since $a$ is relatively prime to $n$ , then it must be a Cyclic Group and thus generate all of $G$ . Thus $| a | = φ (n)$ . Thus:

\Rightarrow 1 = | G : ⟨ a ⟩ |

Thus then $\frac{G}{⟨ a ⟩} = {1}$ . That suggests that $| G |$ is a multiple of $| a |$ , implying that:

a^{| G |} = 1 \Rightarrow a^{φ (n)} = 1 \equiv 1 mod n

☐

23

Question

Determine the last two digits of $3^{3^{100}}$ using the previous question.

Proof

First let's determine $a^{100} mod 100$ . This is done using the previous exercise:

a^{φ (100)} \equiv 1 mod 100

for any $a \in Z$ relatively prime to 100. Actually using the Euler-Totient Function though:

a^{φ (100)} = a^{40} \equiv 1 mod 100

For any $gcd (a, 100) = 1$ , implying that the exponent can be reduced mod 40.

Trying to find $3^{100} mod 40$ , we can do the theorem again using $a = 3$ since it is coprime to 40. Notice that:

3^{φ (40)} \equiv 1 mod 40

But what is $φ (40)$ ? Why it's just 16 (we can look this up, or count the primes ourselves, but $φ$ is also a Homomorphism (or Group Morphism) as the proof indicates). Thus:

3^{16} \equiv 1 mod 40

Thus:

3^{100} \equiv 3^{6 \cdot 16 + 4} \equiv (1 mod 40)^{6} \cdot 3^{4} \equiv 3^{4} \equiv 81 \equiv 1 mod 40

Thus then:

3^{3^{100}} \equiv 3^{1} \equiv 3 mod 100

Thus the last two digits are $03$ .