Past exam of the mathematics course of the University of Cambridge / 2005 / ia / Paper 4 / 6E (Numbers and Sets)

An equivalence relation is reflexive, symmetric and transitive: for all $a,b,c\in S$, one has $aRa$; $aRb$ implies $bRa$; and $aRb$, $bRc$ imply $aRc$. Define the equivalence class $[a]=\{b\in S:aRb\}$. Reflexivity puts $a$ in its class, so these classes cover $S$ and are nonempty. If $[a]$ and $[b]$ share $c$, symmetry and transitivity give $aRb$; the same properties show that every element of either class is in the other. Thus two classes are equal or disjoint. The distinct equivalence classes form a partition of the set.

For the relation defined by a subgroup $H\le G$, $a^{-1}a=1\in H$ proves reflexivity. If $a^{-1}b\in H$, its inverse $b^{-1}a$ belongs to $H$, proving symmetry. If also $b^{-1}c\in H$, their product is $a^{-1}c\in H$, proving transitivity. Finally,These are exactly the left cosets. The map $H\to gH$, $h\mapsto gh$, is a bijection, with inverse $x\mapsto g^{-1}x$. If $G$ is finite and has $r$ such cosets, their disjoint union gives $|G|=r|H|$. This proves the Lagrange theorem:For $g\in G$, finitely many possible powers imply $g^a=g^b$ for some $a<b$, so a positive power is the identity element. If its least positive exponent is $n$, the powers $1,g,\dots ,g^{n-1}$ are distinct: equality of two would produce a smaller positive exponent. They are closed under products and inverses by reducing exponents modulo $n$, hence form the cyclic subgroup $⟨g⟩$ of cardinality $n$. The Lagrange theorem gives $n\mid |G|$, and consequentlyNow take a positive modulus $m$. On residue classes modulo $m$, consider the classes with representatives coprime to $m$. The following integer facts are used: multiplication is associative; reducing representatives respects products; a prime dividing a product divides a factor; and the Bezout identity gives $ra+sm=1$ when $\gcd (a,m)=1$. If $a,b$ are coprime to $m$, no prime divisor of $m$ divides $ab$, so their product class is again in the set. The class of $1$ is its identity element. The Bézout equation gives $ra\equiv 1(\mathrm{mod}m)$, and $r$ is also coprime to $m$ because any common divisor of $r,m$ would divide $1$. Thus every class has an inverse, and these classes form the group of units modulo an integer.

Representing classes in $\{1,\dots ,m\}$ gives precisely the group in the question; for $m=1$ this is the one-element group. Its cardinality is the Euler totient function $\phi (m)$. Applying the finite-group exponent result yields the Fermat-Euler theorem:For $m=1$ the congruence is automatic.