Numbers and Sets | Part IA, 2005

Let RR be a relation on the set SS. What does it mean for RR to be an equivalence relation on SS ? Show that if RR is an equivalence relation on SS, the set of equivalence classes forms a partition of SS.

Let GG be a group, and let HH be a subgroup of GG. Define a relation RR on GG by aRba R b if a1bHa^{-1} b \in H. Show that RR is an equivalence relation on GG, and that the equivalence classes are precisely the left cosets gHg H of HH in GG. Find a bijection from HH to any other coset gHg H. Deduce that if GG is finite then the order of HH divides the order of GG.

Let gg be an element of the finite group GG. The order o(g)o(g) of gg is the least positive integer nn for which gn=1g^{n}=1, the identity of GG. If o(g)=no(g)=n, then GG has a subgroup of order nn; deduce that gG=1g^{|G|}=1 for all gGg \in G.

Let mm be a natural number. Show that the set of integers in {1,2,,m}\{1,2, \ldots, m\} which are prime to mm is a group under multiplication modulo mm. [You may use any properties of multiplication and divisibility of integers without proof, provided you state them clearly.]

Deduce that if aa is any integer prime to mm then aϕ(m)1(modm)a^{\phi(m)} \equiv 1(\bmod \mathrm{m}), where ϕ\phi is the Euler totient function.

Typos? Please submit corrections to this page on GitHub.