MTH 461 University of Miami Consequences of Lagrange Theorem Questions

MTH 461: Survey of Modern Algebra, Spring 2021Homework 4
Homework 4
1. List the left and right cosets of the subgroups in the following list.
(a) The subgroup x5y, generated by 5 pmod 20q, inside pZ5 , `q.
(b) The subgroup 4Z “ t4k ∶ k P Zu inside the group pZ, `q.
(c) The subgroup A3 inside the symmetric group S3 .
(d) The subgroup H “ te, p12qp34q, p13qp24q, p14qp23qu in the group A4 .
(e) The subgroup H “ te, p123q, p132qu in the group A4 .
For which of these examples does it happen that every right coset is a left coset, and
every left coset is a right coset?
2. Let G be a group and H Ă G a subgroup with index 2, i.e. rG ∶ Hs “ 2. Show that
aH “ Ha for all a P G.
3. Recall that GL2 pRq is the group of real 2 ˆ 2 matrices with non-zero determinant, and
SL2 pRq is the subgroup of those matrices with determinant 1. Describe the right cosets
of SL2 pRq in GL2 pRq, and find the index of this subgroup.
4. Use Euler’s Theorem or Fermat’s Little Theorem to help compute the following.
(a) 726 pmod 15q
(b) The last digit of 97123 (Hint: pass to integers mod 10)
(c) 1583 pmod 41q
5. Suppose G is a finite group, and a P G. Suppose n is an integer greater than 1 that
divides the order of G. Show that an cannot generate G, i.e. xan y ‰ G.
6. Let G be a finite group of order pq where p and q are distinct primes. Show that
if a, b P G are non-identity elements of different orders, then the only subgroup in G
containing a and b is the whole group G.
1
MTH 461: Survey of Modern Algebra, Spring 2021
Lecture 7
Lecture 7: Symmetric groups
In this lecture we continue our study of the symmetric groups Sn introduced last lecture,
and we then introduce the notion of even and odd permutations.
§ The order of the group Sn is given by |Sn| “ n!.
This is a basic counting exercise. Each permutation σ is a way of rearranging the elements
t1, . . . , nu. There are n possibilities for σp1q P t1, . . . , nu. Once the value of σp1q is fixed,
there are n ´ 1 possibilities left for σp2q, since it can be anything except for σp1q. Continuing
in this fashion, we see that the number of possibilities for the permutation σ P Sn is equal
to npn ´ 1qpn ´ 2q⋯2 ¨ 1 “ n!.
For example, we have seen that |S1 | “ 1 “ 1!, |S2 | “ 2 “ 2! and |S3 | “ 6 “ 3!. Recall that S3
is essentially the symmetries of an equilateral triangle, and there are 6 such symmetries.
A cycle is a permutation σ P Sn such that there exists an i P t1, . . . , nu with the property
that for each j P t1, . . . , nu either σpjq “ j or j “ σ k piq for some k P Z. In other words, every
element of t1, . . . , nu is either fixed by σ or can be obtained from i by successively applying
σ. Our notation for such a cycle, which we introduced last lecture, is as follows:
pi σpiq σ 2 piq ⋯ σ l´1 piqq
Here l is the smallest positive integer such that σ l piq “ i.
§ Every σ P Sn can be written as a product of disjoint cycles.
Two cycles are disjoint if they share no common elements in their cycle notations. For
example, p13q and p246q are disjoint cycles, while p12q and p254q are not. To prove the
statement, define a relation on the set t1, . . . , nu as follows: i „ j if and only if σ k piq “ j for
some k P Z. You can check that this defines an equivalence relation, and hence partitions
the set t1, . . . , nu, and each equivalence class forms a cycle with respect to σ.
2
4
5
1
6
3
The content of the above is that any permutation σ P Sn partitions the set t1, 2, . . . , nu into
subsets each of which σ permutes in a cyclic fashion. For example, σ “ p245qp16q P S6 is
depicted above. Note that σ fixes “3” and this does not appear in cycle notation.
§ Disjoint cycles in Sn commute.
The length of a cycle is the number of elements appearing in it: p146q is a cycle of length 3,
and p4263q is length 4. A transposition is a cycle of length 2, such as p12q.
1
MTH 461: Survey of Modern Algebra, Spring 2021
Lecture 7
§ For n ě 2, every σ P Sn is a product of transpositions.
We first note that an arbitrary cycle pa1 a2 ⋯ak q can be written
pa1 a2 ⋯ak´1 ak q “ pa3 a2 qpa4 a3 q⋯pak ak´1 qpa1 ak q
For example, p245q “ p45qp24q. The general case follows from the case of cycles, because any
σ P Sn is a product of cycles.
The way in which a cycle is written as a product of transpositions is not unique. As an
example, we have p12qp13q “ p132q “ p23qp12q in the group S3 . In fact, another formula for
writing an arbitrary cycle as a product of transpositions is as follows:
pa1 a2 ⋯ak´1 ak q “ pa1 ak qpa1 ak´1 q⋯pa1 a3 qpa1 a2 q
Even and odd permutations
Let f “ f px1 , . . . , xn q be a polynomial in n variables. Given a permutation σ P Sn define a
new polynomial σpf q to be f pxσp1q , . . . , xσpnq q. Define the special polynomial
ź
∆n “
pxi ´ xj q
1ďiăjďn
to be the product ofl all factors pxi ´ xj q where i, j range over elements of t1, . . . , nu with
i ă j. Then we may apply any permutation σ to this to obtain a new polynomial σp∆n q. It
turns out that this new polynomial is always either ∆n or ´∆n . This lets us divide permutations into two types, as follows:
§ If σp∆nq “ ∆n is called even.
If σp∆n q “ ´∆n then σ is called odd .
For example, consider σ “ p12q P S3 . Note ∆3 “ px1 ´ x2 qpx1 ´ x3 qpx2 ´ x3 q. Then
σp∆3 q “ pxσp1q ´ xσp2q qpxσp1q ´ xσp3q qpxσp2q ´ xσp3q q
“ px2 ´ x1 qpx1 ´ x3 qpx2 ´ x3 q
“ ´px1 ´ x2 qpx2 ´ x3 qpx1 ´ x3 q
“ ´∆3
Thus σ “ p12q is odd. In the next lecture we will show that the even permutations form a
subgroup of Sn called the alternating group An .
2
MTH 461: Survey of Modern Algebra, Spring 2021
Lecture 8
Alternating groups
In this lecture we continue studying even and odd permutations. We introduce and study the
alternating groups An which consist of even permutations. We then consider the rotational
symmetries of the tetrahedron, which are closely related the group A4 .
Recall that a permutation
σ P Sn is even if σp∆n q “ ∆n and odd if σp∆n q “ ´∆n . Here ∆n
ś
is the polynomial 1ďiăjďn pxi ´ xj q introduced last lecture. Define
An “ tσ P Sn ∶ σ is evenu Ă Sn
§ The subset An Ă Sn is a subgroup, called the nth alternating group.
To prove this we first record a useful relation. Given any permutations σ, σ 1 P Sn we have
pσσ 1 qp∆n q “ σpσ 1 p∆n qq
This just follows by writing out what each side means explicitly:
ź
ź
pσσ 1 qp∆n q “
pxpσσ1 qpiq ´ xpσσ1 qpjq q “
pxσpσ1 piqq ´ xσpσ1 pjqq q
1ďiăjďn
1ďiăjďn
˜
“σ
¸
ź
pxσ1 piq ´ xσ1 pjq q
“ σpσ 1 p∆n qq
1ďiăjďn
Similarly, σp´∆n q “ ´σp∆n q. Now suppose σp∆n q “ p´1qk ∆n and σ 1 p∆n q “ p´1ql ∆n . Then
pσσ 1 qp∆n q “ σpσ 1 p∆n qq “ σpp´1ql ∆n q
“ p´1ql σp∆n q “ p´1ql p´1qk ∆n
“ p´1ql`k ∆n
From this computation we see the same rules as for adding even and odd integers:
σ
σ1
even
even
even
odd
even
odd
even
odd
odd
odd
odd
odd
σσ 1
In particular, if σ, σ 1 P An (σ, σ 1 are both even) then σσ 1 P An (σσ 1 is even). Also the identity
is even, so it is in An . Further, if σ P An (σ is even), then since σσ ´1 “ e P An (σσ ´1 is even)
we must have σ ´1 P An (σ ´1 is even). Thus An is a subgroup of Sn .
An alternative characterization of the parity of a permutation is as follows:
1
MTH 461: Survey of Modern Algebra, Spring 2021
§ If σ “ τ1⋯τk
Lecture 8
where τi are transpositions, then σ is odd if and only if k is odd.
To prove this we first show that every transposition is odd. First consider the transposition
σ “ p12q P Sn . There are four kinds of factors in ∆n :
px1 ´ x2 q,
px1 ´ xj q pj ą 2q,
px2 ´ xj q pj ą 2q,
pxi ´ xj q pj ą i ą 2q
Now σ “ p12q only swaps 1 and 2. So it sends the first type of factor to its negative
px2 ´ x1 q “ ´px2 ´ x1 q. It interchanges the second and third types (preserving signs), and
fixes all factors of the fourth type. Taking the product we conclude σp∆n q “ ´∆n , where
the sign comes from the effect of σ “ p12q on the factor px1 ´ x2 q. Next, we use:
§
Let σ “ pa1 a2 ⋯ ak q P Sn be a cycle and τ P Sn any other permutation. Then
τ στ ´1 “ pτ pa1 q τ pa2 q ⋯ τ pak qq
A special case is when σ “ pi jq a transposition different from p12q with j ą i. Setting
τ “ pi 1qpj 2q we get τ ´1 στ “ p12q. If i “ 1, interpret pi 1q as e.
Now let σ be any transposition and choose τ as above such that τ στ ´1 “ p12q. Then
σ “ τ ´1 p12qτ . Let τ p∆n q “ p´1qk ∆n . Note also τ ´1 p∆n q “ p´1qk ∆n . We then compute
σp∆n q “ pτ ´1 p12qτ qp∆n q
“ τ ´1 pp12qpτ p∆n qqq
“ τ ´1 pp12qp´1qk ∆n qq
“ p´1qk τ ´1 pp12qp∆n qq
“ p´1qk τ ´1 p´∆n q
“ p´1qk`1 τ ´1 p∆n q
“ p´1q2k`1 ∆n “ ´∆n
This completes our claim that every transposition is odd. Then to prove the claim about
σ “ τ1 ⋯τk for a product of transpositions, we use the rules of the table we determined above.
Let us look at some examples. As S1 “ teu we of course have A1 “ teu. Next, S2 “ te, p12qu,
and p12q is odd, so in fact A2 “ teu as well. The 3rd symmetric group is
S3 “ te, p12q, p23q, p31q, p123q, p132qu
The three transpositions p12q, p23q, p31q are odd, so they are not in A3 . On the other hand
p123q “ p13qp12q and p132q “ p12qp13q, so these are even. Thus
A3 “ te, p123q, p132qu
Note that p123q2 “ p132q and p123q3 “ e, so A3 is a cyclic (hence abelian) group of order 3.
This is in contrast to S3 . However:
§ The alternating group An is non-abelian if and only if n ě 4.
2
MTH 461: Survey of Modern Algebra, Spring 2021
Lecture 8
Symmetries of the tetrahedron
The first non-abelian alternating group, A4 , is closely related to the rotational symmetries
of the tetrahedron in 3-dimensional space.
A tetrahedron is a solid in 3-dimensional Euclidean space which has 4 vertices and 4 sides,
each an equilateral triangle. On the next page we list the symmetries of the tetrahedron.
There are 2 types of non-identity symmetries. The first type pR1˘1 , R2˘1 , R3˘1 , R4˘1 q fixes a
vertex and rotates the tetrahedron around an axis passing through the fixed vertex by 120˝
in one of two directions. The second kind of symmetry pA, B, Cq is a 180˝ rotation through
an axis which passes through the centers of two opposite edges.
If we label the vertices of the tetrahedron by t1, 2, 3, 4u we can associate a permutation to
each symmetry. Magically, the subgroup of S4 corresponding to the symmetries of the tetrahedron is A4 ! Below we include the Cayley table.
e
R1
R1´1
R2
R2´1
R3
R3´1
R4
R4´1
A
B
C
e
e
R1
R1´1
R2
R2´1
R3
R3´1
R4
R4´1
A
B
C
R1
R1
R1´1
e
A
R4
B
R2
C
R3
R3´1
R4´1
R2´1
R1´1
R1´1
e
R1
R3´1
C
R4´1
A
R2´1
B
R2
R3
R4
R2
R2
C
R4´1
R2´1
e
R1
B
R3´1
A
R1´1
R4
R3
R2´1
R2´1
R3
A
e
R2
C
R4
B
R1´1
R4´1
R3´1
R1
R3
R3
A
R2´1
R4´1
B
R3´1
e
R1
C
R4
R1´1
R2
R3´1
R3´1
R4
B
C
R1´1
e
R3
A
R2
R1
R2´1
R4´1
R4
R4
B
R3´1
R1
A
R2´1
C
R4´1
e
R3
R2
R1´1
R4´1
R4´1
R2
C
B
R3
A
R1´1
e
R4
R2´1
R1
R3´1
A
A
R2´1
R3
R4
R1
R1´1
R4´1
R2
R3´1
e
C
B
B
B
R3´1
R4
R3
R4´1
R2
R1
R1´1
R2´1
C
e
A
C
C
R4´1
R2
R1´1
R3´1
R4
R2´1
R3
R1
B
A
e
3
MTH 461: Survey of Modern Algebra, Spring 2021
Lecture 9
Cosets and Lagrange’s Theorem
In this lecture we introduce the notion of a coset and prove the famous result of Lagrange
regarding the divisibility of the order of a group by the orders of its subgroups.
Fix a group G and a subgroup H Ă G. Define a relation „ on the set G such that for a, b P G:
a„b
ðñ
ab´1 P H
Keep in mind that „ depends on H. We show that this is an equivalence relation.
1. (Reflexivity) a „ a because aa´1 “ e and the identity is in any subgroup.
2. (Symmetry) a „ b implies ab´1 P H. Since H is a subgroup, the inverse of this element
is also in H: we have pab´1 q´1 “ ba´1 P H. Thus b „ a.
3. (Transitivity) a „ b and b „ c imply ab´1 P H and bc´1 P H. Since H is a subgroup, it
is closed under the group operation. Thus pab´1 qpbc´1 q “ ac´1 P H, and a „ c.
We have seen this construction before in a special case. Let G “ pZ, `q and for a fixed
positive integer n take the subgroup H “ nZ “ tnk ∶ k P Zu Ă Z. Then a „ b if and only if
“ab´1 ” “ a ´ b P nZ, i.e. a ” b pmod nq. This motivates the following general notation:
a„b
§ For a P G, let Ha “ tha ∶ h P Hu.
ðñ
a ” b pmod Hq
Then Ha is called a right coset of H in G.
The right cosets of H in G are the equivalence classes of the above relation:
Ha “ tb P G ∶ a ” b pmod Hqu
To see this, consider some b P Ha. Then b “ ha where h P H. From this we then find
ab´1 “ aphaq´1 “ aa´1 h´1 “ eh´1 “ h´1 P H and so a ” b pmod Hq. Thus Ha is a subset of
the equivalence class of a. Conversely consider any b P G such that a ” b pmod Hq. Then
ab´1 P H, so ab´1 “ h for some h P H, and so b “ h´1 a P Ha.
§ There is a 1-1 correspondence between any two right cosets of H
in G.
Let Ha be a right coset. It suffices to show that Ha is in 1-1 correspondence with H itself.
For this, we note that each h P H determines the element ha P Ha, and every element in Ha
is of this form. Thus the only thing to check is that if ha “ h1 a then h “ h1 , and this just
follows from multiplying by a´1 on the right.
We define the index of a subgroup H in G, written rG ∶ Hs, as follows:
rG ∶ Hs “ #tdistinct right cosets of H in Gu
Of course it is possible that rG ∶ Hs is infinite.
1
MTH 461: Survey of Modern Algebra, Spring 2021
Lecture 9
§ (Lagrange’s Theorem) If G is a finite group, and H
is a subgroup of G, then
rG ∶ Hs “ |G|{|H|
In particular, if G is finite, the order of any subgroup H divides the order of the group G.
The proof follows from our discussion above: the right cosets in G are equivalence classes,
and partition the set G into rG ∶ Hs distinct subsets, each of which has size |H|. From this
it follows that |G| “ rG ∶ Hs ¨ |H|.
Let’s see all of this in action. Take the symmetric group S3 of orer 6:
S3 “ te, p12q, p23q, p31q, p123q, p132qu
Let H be the order 2 cyclic subgroup te, p12qu. Then the right cosets are
He “ te, p12qu,
Hp23q “ tp23q, p123qu,
Hp31q “ tp31q, p132qu
Any other right coset is one of the above 3: we have Hp12q “ He “ H, Hp123q “ Hp23q and
Hp132q “ Hp31q. The number of distinct right cosets is rS3 ∶ Hs “ 3. We directly observe
Lagrange’s Theorem: 6{2 “ |S3 |{|H| “ rS3 ∶ Hs “ 3.
For another example, consider the symmetric group S4 . This has order |S4 | “ 4! “ 24. We
saw last lecture that the alternating group A4 Ă S4 has order 12. Thus
rS4 ∶ A4 s “ |S4 |{|A4 | “ 24{12 “ 2
In particular, there are exactly two right cosets: A4 “ A4 e and A4 σ where σ is any odd
permutation, say, a transposition.
For the general symmetric group Sn , and the subgroup An Ă Sn , there are only two right
cosets. To see this, we note that a ” b pmod An q if and only if ab´1 is even. Thus the two
equivalence classes, i.e. right cosets, are the sets of even and odd permutations. We conclude
|An | “ |Sn |{rSn ∶ An s “ n!{2.
Thus the alternating group An has order n!{2.
2
MTH 461: Survey of Modern Algebra, Spring 2021
Lecture 10
Consequences of Lagrange’s Theorem
Last lecture we discussed Lagrange’s Theorem: for any finite group G, and subgroup H Ă G,
we have rG ∶ Hs “ |G|{|H|. Recall here that rG ∶ Hs is the number of right cosets of H in G.
The most useful consequence of this theorem is the following:
§ If G is a finite group, and H
is a subgroup of G, then |H| divides |G|.
This of course greatly constrains the possibilities for which subsets of G can be subgroups.
A particular case is the following. Let a P G and consider the cyclic subgroup xay Ă G
generated by a. Recall that ordpaq is equal to the size of this subgroup. We obtain:
§ If G is a finite group and a P G then ordpaq divides |G|.
For example, S3 can only have elements of orders t1, 2, 3, 6u, and 6 does not occur because S3
is not cyclic. In fact, we know all of this from direct computation. But now we understand
more about why the orders of elements are constrained to these numbers.
§ If G is a finite group and a P G then a|G| “ e.
Indeed, writing |G| “ ordpaq ¨ n, we have a|G| “ aordpaq¨n “ paordpaq qn “ en “ e, as claimed.
Next, we apply this last result to the group pZˆ
n , ˆq where n is a positive integer. Define
φpnq “ |Zˆ
n | “ #tk P Z ∶ 1 ď k ď n, gcdpk, nq “ 1u
The function φpnq is called Euler’s φ-function, and sometimes Euler’s totient function. For
ˆ
example, Zˆ
7 “ t1, 2, 3, 4, 5, 6u so φp7q “ 6, while Z10 “ t1, 3, 7, 9u and so φp10q “ 4. Below
we show a graph of Euler’s φ-function.
80
60
40
20
20
40
60
80
100
Euler’s φ-function
1
MTH 461: Survey of Modern Algebra, Spring 2021
Lecture 10
§ (Euler’s Theorem) For any integer k relatively prime to n, we have
k φpnq ” 1 pmod nq
This result follows from the previous one: just view k pmod nq as an element of Zˆ
n , and
note that the order of the group is by definition φpnq!
For example, let n “ 30. We list the integers from 1 to 30 which are relatively prime to 30:
Zˆ
30 “ t1, 7, 11, 13, 17, 19, 23, 29u
Thus φp30q “ |Zˆ
30 | “ 8. Furthermore, Euler’s Theorem tells us that for any one of the above
8 integers k (and their congruence classes mod 30) we have k 8 ” 1 pmod 30q.
A special case of Euler’s Theorem is when n is a prime number p. For in this case we have
Zˆ
p “ t1, 2, ⋯, p ´ 1u
so in particular φppq “ p ´ 1. Therefore we obtain:
§ (Fermat’s Little Theorem) For a prime p and integer k relatively prime to p:
k p´1 ” 1 pmod pq
The conclusion of this result is often written as k p ” k pmod pq.
For example, 97 is a prime number. Let’s compute 599 pmod 97q. Fermat’s Little Theorem
tells us that 596 ” 1 pmod 97q. Using this we compute:
599 ” 596`3 ” 596 53 ” 1 ¨ 53 ” 125 ” 28 pmod 97q
Without the help of Fermat’s Little Theorem, this would have taken much longer!
Another important consequence of Lagrange’s Theorem is the following.
§ Suppose G is a finite group of prime order.
Then G is cyclic.
Let H Ă G be a subgroup of G. Then Lagrange’s Theorem tells us that |H| divides |G|.
Since |G| is prime, |H| must be 1 or |G|. In the first case, we must have H “ teu, and in
the latter case, H “ G. In particular, G has no non-trivial proper subgroups. Let a P G be
a non-identity element. Then xay is a non-trivial subgroup and thus must be all of G. In
particular, G “ xay and so G is cyclic and generated by a.
We make two important remarks about Lagrange’s Theorem. First, we could have used
the notion of a left coset instead of a right coset: these are subsets aH “ tah ∶ h P Hu.
Lagrange’s Theorem holds for left cosets, by the same arguments. A consequence is that the
number of left cosets is equal to rG ∶ Hs, the number of right cosets.
2
MTH 461: Survey of Modern Algebra, Spring 2021
Lecture 10
Second, the converse to Lagrange’s Theorem is false: if a positive integer d divides |G|, then
it is not necessarily true that there is a subgroup of order d within G. The first instance of
this phenomenon is the following:
§ In the alternating group A4 of order 12, there is no subgroup of order 6.
Let us prove this. First we write out the 12 elements of A4 :
A4 “ te, p123q, p132q, p124q, p142q, p134q, p143q, p234q, p243q, p12qp34q, p13qp24q, p14qp23qu
Note we have 8 cycles of length 3, which have order 3, and 3 elements which are pairs of
disjoint transpositions, each of order 2. Now suppose there is a subgroup H Ă A4 of order
6. Let σ P A4 be a cycle of length 3. Consider the right cosets
H,
Hσ,
Hσ 2
Lagrange’s Theorem tells us that rA4 ∶ Hs “ |A4 |{|H| “ 12{6 “ 2, so there are exactly 2 right
cosets. So two of the cosets above must be equal. If H “ Hσ, then σ P H, and similarly if
H “ Hσ 2 then σ 2 P H. But since σ 2 “ σ ´1 and H is a subgroup, we must have σ P H. The
other possibility is that Hσ “ Hσ 2 . Multiplying on the right by σ gives Hσ 2 “ H, and again
we conclude σ P H. In conclusion, every length 3 cycle in A4 must be in H. But there are
8 such cycles. Thus 6 “ |H| ě 8, which is a contradiction. Thus A4 cannot have a subgroup
of order 6, as we claimed.
3