MTH 461 University of Miami Survey of Modern Algebra Exercises

Just 6 short questions, and the questions are on the file ‘461’. I also uploaded the lectures for those questions. The time limit is due by this week Friday 11pm.

MTH 461: Survey of Modern Algebra, Spring 2021
Homework 2
Homework 2
1. For each equation in Zn find all solutions for x P Zn .
(a) 3x ” 10 pmod 16q
(b) 7x ” 9 pmod 18q
(c) 4x ” 5 pmod 12q
(d) 2x ” 6 pmod 12q
2. Find the orders of the following elements.
(a) 9 pmod 51q in the group pZ51 , `q
(b) 3 pmod 16q in the group pZˆ
16 , ˆq
?
(c) 7 in the group pR, `q
?
(d) 7 in the group pRˆ , ˆq
3. Find the orders of the following elements in the general linear group GL2 pRq.
ˆ
˙
ˆ
˙
ˆ
˙
2 0
0 ´1
1 1
A“
,
B“
,
C“
0 3
1 1
0 1
4. Let G be a group and a P G any element.
(a) Show that if ak “ e then ordpaq divides k.
(Hint: Write k “ ordpaqq ` r where 0 ď r ă ordpaq is the remainder.)
(b) Suppose G is abelian, and b P G. Write m “ ordpaq, n “ ordpbq. Show that
ordpabq divides the least common multiple of m, n.
(c) Consider the group G “ te, r, b, g, o, yu from Lecture 1. Compute the orders of
each element in G. Show part (b) is not true for non-abelian groups, in general.
5. Prove or disprove the following statements.
(a) pQˆ , ˆq is a cyclic group.
(b) pZˆ
4 , ˆq is a cyclic group.
(c) If a group has no proper non-trivial subgroups then it is cyclic.
(Proper: not the whole group; non-trivial: not the trivial subgroup teu.)
6. For any abelian group, show that the subset of elements of finite order is a subgroup.
1
MTH 461: Survey of Modern Algebra, Spring 2021
Lecture 3
Lecture 3: Integers modulo n
In this lecture we discuss some of the most important examples of groups: ones which
come from taking certain equivalence classes of integers. To begin, we recall the notion of
equivalence relations. Let S be a set, and R Ă S ˆ S a subset. Write a „ b if and only if
pa, bq P R. Then R is an equivalence relation on the set S if the following hold:
1. (Reflexivity) a „ a for all a P S.
2. (Symmetry) a „ b implies b „ a.
3. (Transitivity) a „ b and b „ c implies a „ c.
Given an equivalence relation on S as above, we write ras “ tb P S ∶ b „ au for the equivalence
class of a, which is a subset of S.
A partition of a set S is a collection of non-empty subsets tSi uiPI of S such that the union
of all Si over i P I is equal to S, and the subsets are pairwise disjoint: Si X Sj “ H if i ‰ j.
For example, for a set with 5 elements represented by dots, here are depicted a few different
partitions of S, where the subsets are encoded by colors:
Equivalence relations on sets and partitions of sets are essentially the same thing. Given an
equivalence relation on S, the equivalence classes form a partition of S. Conversely, if we
have a partition tSi uiPI of S, then the relation a „ b if and only if “a and b belong to some
common subset Si ” defines an equivalence relation on S.
The group Zn
Fix a positive integer n. Define a relation on Z as follows: a „ b if and only if a ´ b “ nk for
some k P Z. We check that this is an equivalence relation:
1. (Reflexivity) a „ a because a ´ a “ n0.
2. (Symmetry) a „ b implies a ´ b “ nk. Then b ´ a “ np´kq, implying b „ a.
3. (Transitivity) a „ b and b „ c implies a ´ b “ nk and b ´ c “ nl. Consequently we have
a ´ c “ pa ´ bq ` pb ´ cq “ nk ` nl “ npk ` lq. This implies a „ c.
This equivalence relation partitions the set Z into n equivalence classes.
Zn “ tequivalence classes of the relation „ u “ tr0s, r1s, . . . , rn ´ 1su
1
MTH 461: Survey of Modern Algebra, Spring 2021
Lecture 3
For example, if n “ 3, then Z3 consists of the equivalence classes r0s, r1s, r2s where
r0s “ t0 ` 3k ∶ k P Zu
r1s “ t1 ` 3k ∶ k P Zu
r2s “ t2 ` 3k ∶ k P Zu
and these partition the integers into 3 subsets. More generally, r0s, r1s, . . . , rn ´ 1s are the
equivalence classes of this relation. The set Zn is called the integers modulo n or the integers
mod n. Another notation for a „ b is: a ” b pmod nq. In summary we have:
ras “ rbs
ðñ
a ´ b “ nk for some k P Z
ðñ
a ” b pmod nq
Next, we define a binary operation “`” on the set Zn as follows:
ras ` rbs “ ra ` bs
We first check this is well-defined. That is, suppose ra1 s “ ras and rb1 s “ rbs, i.e. a1 ´ a “ nk
and b1 ´ b “ nl. Then pa1 ` b1 q ´ pa ` bq “ pa1 ´ aq ` pb1 ´ bq “ nk ` nl “ npk ` lq. We conclude
that ra1 ` b1 s “ ra ` bs, and the operation is well-defined.
§ The set Zn with the operation ` is an abelian group.
To verify this we check the group axioms. First, we have associativity:
ras ` prbs ` rcsq “ ras ` rb ` cs “ ra ` pb ` cqs
“ rpa ` bq ` cs “ ra ` bs ` rcs “ pras ` rbsq ` rcs.
Next, e “ r0s serves as an identity, because ras`r0s “ ra`0s “ ras and similarly r0s`ras “ ras.
Finally, an inverse for ras P Zn is r´as because ras ` r´as “ ra ` p´aqs “ ra ´ as “ r0s. Thus
pZn , `q is a group. It is abelian because ras ` rbs “ ra ` bs “ rb ` as “ rbs ` ras.
The group Zn is sometimes written Z{n or Z{nZ. When working in Zn we often drop the
brackets from the equivalence classes and write “a” instead of “ras”. The context should
make it clear that “a” means the equivalence class of a mod n, and not the integer a. Using
this convention, the following is the Cayley table for the group Z6 “ t0, 1, 2, 3, 4, 5u:
0 1
2 3 4 5
0
0 1
2 3 4 5
1
1 2
3 4 5
2
2 3
4 5
3
3 4
5
0 1 2
4
4 5
0
1 2 3
5
5
1 2 3 4
0
0
0 1
For example, in Z6 we have 1 ` 1 “ 2, 3 ` 3 “ 0 and 4 ` 4 “ 2. We can also write these
relations as 1 ` 1 ” 2 pmod 6q, 3 ` 3 ” 0 pmod 6q and 4 ` 4 ” 2 pmod 6q.
2
MTH 461: Survey of Modern Algebra, Spring 2021
Lecture 3
Cyclic groups
The group pZn , `q is a finite abelian group of order n. It is also very special because it is a
cyclic group. An arbitrary group G is called cyclic if there is some a P G such that
G “ tak ∶ k P Zu.
The element a is called a generator of the group G. The group pZ, `q is cyclic with generator
1 P Z, because any integer a P Z can be written as a “ 1 ` ⋯ ` 1. For a similar reason:
§ The group pZn, `q is a cyclic group.
To spell this out, take a “ r1s. Then “ak ” in the group pZn , `q is none other than r1s`⋯`r1s,
where r1s appears k times, which is equal to rks. Now Zn consists exactly of the classes rks
as k runs over the integers; in fact, as we saw above, k need only run over 0, 1, . . . , n ´ 1.
Thus every element of Zn is of the form “ak ” and so Zn is cyclic with generator r1s.
In turns out the groups pZ, `q and pZn , `q for positive integers n are essentially the “only”
cyclic groups, in a sense that we will make precise later.
3
MTH 461: Survey of Modern Algebra, Spring 2021
Lecture 4
Lecture 4: More modular arithmetic
Last time, for any given positive integer n, we introduced the set Zn , which is obtained from
Z by identifying integers which differ by a multiple of n. We defined a group operation on
Zn called “`” which is inherited from addition in Z. In this lecture we continue studying
further algebraic properties and structures on Zn .
Another natural operation to consider on Zn is multiplication: writing a pmod nq for the
equivalence class of a P Z, we define the product of a pmod nq and b pmod nq to be ab
pmod nq. Alternatively, if we write ras for the equivalence class of a P Z, our definition is:
rasrbs “ rabs
This is well-defined: if ra1 s “ ras and rb1 s “ rbs, then a1 ´ a “ nk and b1 ´ b “ nl for some
k, l P Z, so a1 b1 ´ ab “ a1 pb1 ´ bq ` bpa1 ´ aq “ npla1 ` kbq, and therefore ra1 b1 s “ rabs.
§ The operations of addition and multiplication on Zn satisfy the properties:
(Associativity for `)
a ` pb ` cq ” pa ` bq ` c pmod nq
(Associativity for ˆ)
apbcq ” pabqc pmod nq
(Identity for `)
a ` 0 ” 0 ` a ” a pmod nq
(Identity for ˆ)
1 ¨ a ” a ¨ 1 ” a pmod nq
(Inverses for `)
a ` p´aq ” p´aq ` a ” 0 pmod nq
(Distributivity)
apb ` cq ” ab ` ac pmod nq
(Commutativity for `)
a ` b ” b ` a pmod nq
(Commutativity for ˆ)
ab ” ba pmod nq
In short, all the formal properties you are familiar with in Z hold in Zn . A structure with two
operations (“addition” and “multiplication”) satisfying all of the above formal properties is
called a (commutative) ring. However we will hold off on studying general rings.
Included in the above list are the axioms for pZn , `q to be an abelian group. However, except
in the degenerate case n “ 1 for which 0 ” 1 pmod 1q, the set Zn with multiplication does not
form a group. This is because 0 P Zn does not have a multiplicative inverse. The problem is
not just 0, however. For example, in Z4 “ t0, 1, 2, 3u we have:
2 ¨ 0 ” 0 pmod 4q,
2 ¨ 1 ” 2 pmod 4q,
2 ¨ 2 ” 0 pmod 4q,
2 ¨ 3 ” 2 pmod 4q
Thus there is no element of Z4 which is a multiplicative inverse for 2; such an element x P Z4
would have to have 2 ¨ x ” 1 pmod 4q. After reviewing some basic properties of the integers
we will show how to “correct” this problem, by eliminating certain elements from Zn so that
it becomes a group with multiplication.
1
MTH 461: Survey of Modern Algebra, Spring 2021
Lecture 4
The group Zˆ
n
An integer d is a divisor of an integer a if a “ dk for some k P Z. An positive integer d
is a greatest common divisor of a and b, written d “ gcdpa, bq, if it satisifes the following
property: for any integer d1 dividing both a and b, we have that d1 divides d. A good exercise
is to check that there is a unique greatest common divisor for any a, b P Z. As an example,
we have gcdp9, 24q “ 3. The key property we are after is:
§ Let a, b P Z be non-zero integers.
Then there exist integers r, s P Z such that
gcdpa, bq “ ar ` bs
As an illustration, we can see directly that this is true for a “ 9, b “ 24:
9p3q ` 24p´1q “ 3
so upon choosing r “ 3, s “ ´1 we have the desired relation.
To prove the statement in general, we proceed by considering the subset of Z defined by
S “ tam ` bn ∶ m, n P Z, am ` bn ą 0u
As a, b are non-zero, the set S is non-empty. For example, with m “ a and n “ b we have
am ` bn “ a2 ` b2 ą 0, so a2 ` b2 is in S. Let d be the smallest element in S. Then
d “ ar ` bs for some r, s P Z. The claim is that d “ gcdpa, bq. To prove this we use division
with remainder for integers, applied to a divided by d: that is, we can write
a “ dq ` r1
where q, r1 P Z and 0 ď r1 ă d (the remainder). We can then write
r1 “ a ´ dq “ a ´ par ` bsqq “ ap1 ´ rqq ` bpsqq
If r1 ą 0 then r1 P S and is less than d, a contradiction to our minimality assumption on d.
Thus r1 “ 0, and a “ dq, so d divides a. A similar argument shows d divides b. Thus d divides
both a and b. Finally, we must show that if d1 divides both a and b then it divides d. If d1 divides a then a “ d1 k and if d1 divides b then b “ d1 l. So d “ ar ` bs “ d1 kr ` d1 ls “ d1 pkr ` lsq,
and thus d1 divides d. Therefore d “ gcdpa, bq. This completes the proof.
§ In Zn, a pmod nq has a multiplicative inverse if and only if gcdpa, nq “ 1.
To see this, first suppose a pmod nq has a multiplicative inverse, i.e. there is some integer b
such that ab ” 1 pmod nq, or equivalently ab ´ 1 “ nk for some integer k. Thus ab ` nk “ 1.
If d divides a and n, it divides ab ` nk “ 1, so d divides 1. Thus gcdpa, nq “ 1. Conversely,
suppose gcdpa, nq “ 1. There exists r, s P Z such that gcdpa, nq “ ar ` ns. Then ar ´ 1 “ ns,
so ar ” 1 pmod nq. Thus r pmod nq is a multiplicative inverse for a pmod nq.
2
MTH 461: Survey of Modern Algebra, Spring 2021
Lecture 4
If gcdpa, bq “ 1 then a, b are said to be relatively prime. This motivates the following
definition: we let Zˆ
n denote the subset of Zn consisting of elements relatively prime to n:
Zˆ
n “ t a pmod nq ∶ gcdpa, nq “ 1 u
§ The set Zˆn equipped with the operation of multiplication defines a group.
Let us look at some examples. First, consider the integers mod 4, i.e. Z4 . Then we have
Zˆ
4 “ t1, 3u Ă Z4 “ t0, 1, 2, 3u
As is often done, we have just written “1” etc. for the equivalence class “1 pmod 4q” which
we also previously wrote as “r1s”. In conclusion, Zˆ
4 is a finite abelian group of order 2.
Next, consider Z10 , the integers modulo 10. In this case we find:
Zˆ
10 “ t1, 3, 7, 9u Ă Z10 “ t0, 1, 2, 3, 4, 5, 6, 7, 8, 9u
Thus Zˆ
10 is a finite abelian group of order 4. For example, 3 ¨ 7 ” 21 ” 1 pmod 10q, so the
inverse of 3 pmod 10q is 7 pmod 10q, and conversely. Here is the Cayley table for pZˆ
10 , ˆq:
1
3 7 9
1
1
3 7 9
3
3
9
1 7
7
7
1
9 3
9
9
7 3
1
ˆ
When n is a prime number p, then Zˆ
p “ t1, . . . , p ´ 1u. For example, Z7 “ t1, 2, 3, 4, 5, 6u.
§ Suppose gcdpa, nq “ 1 and b any integer.
Then the equation in Zn given by
ax ” b pmod nq
can always be solved for x, and the solution x is unique as an element of Zn .
To see that this statement is true, we use the fact that a pmod nq has an inverse in Zˆ
n and
multiply both sides of the equation by this inverse.
For example, consider the equation 7x ” 6 pmod 10q in Z10 . Then multiply both sides by
3 pmod 10q to get x ” 18 ” 8 pmod 10q. On the other hand, we saw earlier that 2x ” 1
pmod 4q has no solutions, but in this case gcdp2, 4q “ 2 ‰ 1.
3