In which we think about cyclic groups, and renew an old friendship with equivalence relations.
- Theorem 21: Let be a cyclic group. Let be a subgroup of . Then is cyclic. We proved this using the division algorithm. We said that if contains something other than the identity, then we can pick the smallest positive integer with . Clearly , and to show the reverse inclusion we used the division algorithm to argue that if then divides and so .
- Proposition 22: Let , be integers. Let , be positive integers such that and . Then
- and ;
- there are integers , such that ; [Bézout‘s Lemma]
- if and , then ;
- and ;
- if and , then .
These were all reasonably straightforward to check. Parts (i), (ii), (iv) and (v) all had a similar flavour, whereas (iii) followed from (ii). For example, for (i) we said that , so , and similarly for .
- Definition of the highest common factor (hcf) and least common multiple (lcm) of two integers.
- Lemma 23: Let be a group. Let be an element with finite order . Then if and only if . One direction is almost immediate, for the other direction we used the division algorithm, in an argument of a familiar kind.
- Theorem 24 (Chinese Remainder Theorem): Let , be coprime positive integers. Then is cyclic, and is isomorphic to . We showed that if and , then has order , using Lemma 23 and Bézout at appropriate points, and then noted that is a group of order containing an element of order .
- Definition of a (binary) relation on a set .
- Definition of an equivalence relation.
- Proposition 25: Let be an integer. Define a relation on by if and only if is a multiple of . Then is an equivalence relation. This was a routine check using the definition of an equivalence relation (we checked that is reflexive, symmetric and transitive).
- Definition of congruence modulo .
- Definition of what it means for two elements of a group to be conjugate (building on a definition for permutations).
- Proposition 26: Let be a group. Conjugacy in is an equivalence relation. This was another routine check.
A student pointed out to me at the end of the lecture that I had at least one typo on the board (and very possibly more). When we used the division algorithm (in the proofs of Theorem 21 and Lemma 23), I meant to write something like , but the minus sign in the final exponent might have been missing. Very sorry if it caused any confusion, happily it doesn’t make a difference of any substance (apart from making the equation true…).
Understanding today’s lecture
I gave a couple of examples of equivalence relations (in addition to the ones in Propositions 25 and 26), can you show that they really are equivalence relations?
I’ve written about Bézout’s lemma (or theorem or whatever) before on this blog. I’ve also written about the Chinese Remainder Theorem, phrased in a different way. Linking that version of the theorem with the group theory one we saw today is a good exercise.
I mentioned that our work on highest common factors fits into a bigger and more general picture in rings. You will learn lots more about this if you take the second-year Rings and Modules course (which has online notes available at that webpage). The key concepts I mentioned were that of a ring, a Euclidean domain (that’s two links hidden in there), and a principal ideal domain. You can read a little more about Euclid’s algorithm for the integers in my blog post on Bézout’s lemma (or theorem or whatever).
For an important approach to common factors, you should watch this short video by Vi Hart.
Preparation for Lecture 7
Remind yourself of the definition of an equivalence class. Can you show that the equivalence classes for an equivalence relation form a partition of the set on which the relation is defined? If I give you a partition, must it necessarily correspond to an equivalence relation? You might want to use some of these ideas when working on Sheet 3, but you’ve had a sneak preview in the Introduction to University Level Maths course, which should help.