Skip to main content
Logo image

Section 2.6 Additional exercises

Exercises Exercises

1. The group of units in \(\Z_n\).

Let \(U_n\) denote the set of elements in \(Z_n\) that have multiplicative inverses, that is,
\begin{equation*} U_n = \{x\in \Z_n\colon \exists y, xy=1\pmod{n}\}. \end{equation*}
  1. Show that \(x\) is in \(U_n\) if and only if \(x\) is relatively prime to \(n\text{.}\)
  2. Show that \(U_n\) with the binary operation of multiplication mod \(n\) is an Abelian group.
  3. Show that \(U_n\) is isomorphic to \(\Aut(\Z_n)\) via \(x\to [a\to ax]\text{.}\)
Terminology: The group \(U_n\) is called the the group of (multiplicative) units in \(\Z_n\text{.}\) The function \(n\to |U_n|\text{,}\) important in number theory, is called the Euler phi function, written \(\phi(n)=|U_n|\text{.}\)

2. Fermat’s Little Theorem.

For every integer \(x\) and every prime \(p\text{,}\) we have \(x^p = x \pmod{p}\text{.}\)
First, reduce \(x\) mod \(p\text{,}\) that is, write \(x=qp+r\) with \(0\leq r\leq p-1\text{.}\) Now consider two cases. The case \(r=0\) is trivial. If \(r\neq 0\text{,}\) apply the fact \(r^{|G|}=e\) (see Exercise 2.3.8) to the group \(G=U_p\text{.}\)

3. An alternative approach to parity of permutations.

This exercise gives a way to define even and odd permutations that is different from the method used in Exercise 2.5.1.
  1. Suppose that the identity permutation \(e\) in \(S_n\) is written as a product of transpositions
    \begin{equation*} e=\tau_1\tau_2\cdots \tau_r. \end{equation*}
    Show that \(r\) is even.
  2. Suppose that \(\sigma\) in \(S_n\) is written in two ways as a product of transpositions.
    \begin{equation*} \sigma = (a_1b_1)(a_2b_2)\cdots (a_sb_s) = (c_1d_1)(c_2d_2)\cdots (c_td_t) \end{equation*}
    Show that \(s,t\) are either both even or both odd. The common evenness or oddness of \(s,t\) is called the parity of the permutation \(\sigma\text{.}\)
  3. Show that the parity of a \(k\)-cycle is even if \(k\) is odd, and the parity of a \(k\)-cycle is odd if \(k\) is even.
  1. Consider the two rightmost transpositions \(\tau_{r-1}\tau_{r}\text{.}\) They have one of the following forms, where \(a,b,c,d\) are distinct.
    \begin{equation*} (ab)(ab), (ac)(ab), (bc)(ab), (cd)(ab) \end{equation*}
    The first allows you to reduce the transposition count by two by cancelling. The remaining three can be rewritten.
    \begin{equation*} (ab)(bc), (ac)(cb), (ab)(cd) \end{equation*}
    Notice that the index of the rightmost transposition in which the symbol \(a\) occurs has been reduced by 1 (from \(r\) to \(r-1\)). Finish this reasoning with an inductive argument.

4. The size of the alternating group.

Show that \(|A_n|=|S_n|/2\) for \(n\geq 2\text{,}\) that is, that half of the elements of \(S_n\) are even, and half are odd.

5. The order of a permutation.

Let \(\sigma\in S_n\) be written as a product of disjoint cycles. Show that the order \(\sigma\) is the least common multiple of the lengths of those disjoint cycles.

6. Alternative approach to multiplication in a factor group.

Given subsets \(S,T\) of a group \(G\text{,}\) define the set \(ST\) by
\begin{equation*} ST = \{st\colon s\in S,t\in T\}. \end{equation*}
Now suppose that \(H\) is a subgroup of \(G\text{.}\) Show that \((xH)(yH)=xyH\) for all \(x,y\) in \(G\) if and only if \(H\) is a normal subgroup of \(G\text{.}\)

7. Semidirect product.

Let \(K,H\) be groups, and let \(\phi\colon H\to \Aut(K)\) be a homomorphism. The semidirect product, denoted \(K\times_{\phi} H\text{,}\) or \(K\rtimes H\) if \(\phi\) is understood, is the set consisting of all pairs \((k,h)\) with \(k\in K\text{,}\) \(h\in H\)
The notation \(K\times H\) is understood to be the direct product group, so we do not write use the Cartesian product notation to describe semidirect product, to avoid confusion, even though the underlying set for the direct product and the semidirect product are in fact the same Cartesian product \(K\times H\text{.}\)
with the group multiplication operation \(\ast\) given by
\begin{equation*} (k_1,h_1)\ast (k_1,h_2) = (k_1\phi(h_1)(k_2),h_1h_2). \end{equation*}
Two examples demonstrate why this is a useful construction. The dihedral group \(D_n\) is (isomorphic to) the semidirect product \(C_n\rtimes C_2\text{,}\) where \(C_n\) is the cyclic group generated by the rotation \(R_{1/n}\) (rotation by \(1/n\) of a revolution) and \(C_2\) is the two-element group generated by any reflection \(R_L\) in \(D_n\text{.}\) The map \(\phi\colon C_2 \to \Aut(C_n)\) is given by \(F_L \to [R_{\theta} \to R_{-\theta}]\text{.}\) The Euclidean group of congruence transformations of the plane is (isomorphic to) the group \(\R^2\rtimes O(2)\text{,}\) where \((\R^2,+)\) is the additive group of \(2\times 1\) column vectors with real entries, and \(O(2)\) is the group of \(2\times 2\) real orthogonal matrices. The map \(\phi\colon O(2)\to \Aut(\R^2)\) is given by \(g\to [v\to gv]\text{,}\) that is to say, the natural action of \(O(2)\) on \(\R^2\text{.}\) [The Euclidean group element \((v,g)\) acts on the point \(x\in\R^2\) by \(x\to gx+v\text{.}\)]
  1. Do all the necessary details to show that \(K\rtimes H\) is indeed a group.
  2. (Characterization of semidirect products) Suppose that \(K,H\) are subgroups of a group \(G\text{.}\) Let \(KH=\{kh\colon k\in K,h\in H\}\text{.}\) Suppose that \(K\) is a normal subgroup of \(G\text{,}\) that \(G=KH\text{,}\) and that \(K\cap H=\{e\}\text{.}\) Show that \(\phi\colon H\to \Aut(K)\text{,}\) given by \(\phi(h)(k)=hkh^{-1}\text{,}\) is a homomorphism. Show that \(\psi\colon K\times_\phi H\to G\text{,}\) given by \(\psi(k,h)=kh\text{,}\) is an isomorphism.
  3. Show that \(D_n\approx C_n\rtimes C_2\text{,}\) as described above.
  4. Show that the following requirement holds for the Euclidean group action. We have
    \begin{equation*} [(v_1,g_1)(v_2,g_2)]x = (v_1,g_1)[(v_2,g_2)x], \end{equation*}
    for all \(v_1,v_2,x\in \R^2\) and \(g_1,g_2\in O(2)\text{.}\)
  5. Suppose that \(\phi\colon H\to \Aut(K)\) is the trivial homomorphism (that is, \(\phi(h)\) is the identity homomorphism on \(K\text{,}\) for all \(h\in H\)). Show that \(K\times_{\phi} H\approx K\times H\) in this case.

8. Group action on functions on a \(G\)-space.

Suppose that a group \(G\) acts on a set \(X\text{.}\) Let \({\mathcal F}(X,Y)\) denote the set of functions
\begin{equation*} {\mathcal F}(X,Y) = \{f\colon X\to Y\} \end{equation*}
from \(X\) to some set \(Y\text{.}\) Show that the formula
\begin{equation*} (g\cdot \alpha)(x) = \alpha(g^{-1}\cdot x) \end{equation*}
defines an action of \(G\) on \({\mathcal F}(X,Y)\text{,}\) where \(g\in G\text{,}\) \(\alpha \in {\mathcal F}(X,Y)\text{,}\) and \(x\in X\text{.}\)