*in which apply Lagrange’s Theorem to prime order groups, meet equivalence relations and further explore multiplication modulo n.
*

We continued with some **corollaries of Lagrange**: last time we saw that the order of an element divides the order of the group, and this time we proved that for all in a finite group , we have . We called this “the exponent divides the group order” (remember from Sheet 1: the smallest such that for all ) . We also proved that **groups of prime order are cyclic**, and are generated by any of their non-identity elements.

To prepare for some further applications of Lagrange, we defined an equivalence relation: A relation on a set is an **equivalence relation** if it is **reflexive** ( for all ), **symmetric** () and **transitive** ( and together imply ). As examples we had “is congruent mod to” on the integers, and “is isomorphic to” for groups. Such an equivalence relation gives us equivalence classes: . Equivalence classes form a partition on the set , and we saw that, for a group with subgroup , the relation is an equivalence relation on with the cosets of as equivalence classes.

As next application of Lagrange, we are working towards the Fermat-Euler Theorem, which is really a number theory theorem, but has a nice short groups proof. To get there, we looked at why **adding and multiplying “numbers mod ”** works, i.e. is well-defined. It all rests on them being cosets. To make a multiplicative group, we need to restrict attention to only those numbers which have inverses mod , which we found were exactly the (cosets of) numbers which are coprime to . We proved that the set of these cosets indeed forms a group. In the proof we used a nice trick: any injective function from a finite set to itself must also be surjective. So we showed fairly easily that “multiplication by ” gives an injective function (as long as is coprime to ), which being surjective supplies an inverse for . This group has size , where is **Euler’s totient function** “the number of elements in which are coprime to “. We will see next time how this proves Fermat-Euler, a special case of which is Fermat’s Little Theorem.

**Understanding today’s lecture**

Are you surprised by the Lagrange corollaries? I think they are very comforting :-). And we will be using them all the time throughout the course, so you should make friends with them.

For equivalence relations, there are actually quite a lot of nice instructive “non-mathematical” examples that might help you to get a feel for it: for example, if is the set of all undergraduates in Cambridge, we could have “has their birthday in the same month as”, or “is in the same College as”. Show that these are indeed equivalence relations; can you say what their equivalence classes are? Others would be “having the same height as”, “having the same haircolour as”, and so on; I’m sure you can come up with some more. Undergrads who go to the same college are definitely not the *same people*, but they have a particular property in common.

Think about what we showed about the well-definedness of addition and multiplication mod . Is this trivial? It may well be something you “knew all along” but now see the proper reason for (that happens a lot in maths…).

**Preparing for Lecture 10
**

Next time we will prove Fermat-Euler: for a natural number and an integer coprime to , we have . Perhaps you’ve come across a different, non-groups proof for it, or at least for Little Fermat (the same thing when is a prime , so ). But in our lecture we will prove it using some nice group theory. Can you find a proof using what we’ve done so far?

We will also use Lagrange to help us find subgroups of certain groups. You could have a go at some dihedral groups yourself.

**Going a little deeper**

We said that the exponent divides the group order. In fact, the exponent has all prime factors of the group order . We can only prove this later when we have Cauchy’s theorem.

I didn’t really tell you what a relation is, only when a relation (whatever it might be) is an equivalence relation. Naively, a relation is something that “relates two elements of a set”. They either are related or not. For example on the integers, on the reals, or “have the same quotient” on the set of ordered pairs of integers, where we don’t allow the second one to be . More formally, a relation on a set is a subset of the cartesian product of with itself. So it just tells you which pairs of elements are related and which aren’t. The order does usually matter (as you can see with ). If it doesn’t, then it is a symmetric relation. I can’t actually remember whether this is defined in that formality in Numbers and Sets, but I think you’ll see it in third year in Logic and Set Theory.

In some sense, is the “prototype” of an equivalence relation. We said above that being in the same equivalence class doesn’t mean being exactly the same element, but if we are concentrating on just that particular property, it might be “the same enough” for our purposes. That is what I meant when I said “isomorphic groups are the same enough for us”. We will see in the next chapter how we can “make” all the elements in one equivalence class the same by forming a quotient.