I - A little elementary group theory

Summary

A set of positive integers less than N constitutes a group under multiplication modulo N if the set (a) contains 1, (b) contains the modulo-N inverse of any of its members, and (c) contains the the modulo-N products of all pairs of its members. A subset of a group meeting conditions (a)–(c) is called a subgroup. The number of members of a group is called the order of the group. An important result of the elementary theory of finite groups (Lagrang's theorem) is that the order of any of its subgroups is a divisor of the order of the group itself. This is established in the next three paragraphs.

If S is any subset of a group G (not necessarily a subgroup) and a is any member of G (which might or might not be in S), define aS (called a coset of S) to be the set of all members of G of the form g = as, where s is any member of S. (Throughout this appendix equality will be taken to mean equality modulo N.) Distinct members of S give rise to distinct members of aS, for if s and s′ are in S and as = as′, then multiplying both sides by the inverse of a gives s = s′. So any coset aS has the same number of members as S itself.