🏠

Groups and group actions problem sheet 4

 
  • Feb 01, 2022
  1. (i) Let $x, n$ be integers with $n \geqslant 2$ and $n$ not dividing $x$. Show that the order $o(\bar{x})$ of $\bar{x} \in \mathbb{Z}_{n}$ is$$o(\bar{x})=\frac{n}{\operatorname{hcf}(x, n)} .$$(ii) Let $G, H$ be finite groups with $g \in G$ and $h \in H$. Show that the order of $(g, h)$ in $G \times H$ is given by$$o((g, h))=\operatorname{lcm}\{o(g), o(h)\}.$$Proof.
    (i)Let $\operatorname{hcf}(x,n)=d,x=x'd,n=n'd,$ then $n'\bar x=n'd\overline{x'}=n\overline{x'}=\overline0⇒o(\bar x)|n'$. On the other hand, $o(\bar x)\overline{x}=\overline{0}⇒n|o(\bar x)x⇒n'd|o(\bar x)x'd⇒n'|o(\bar x)x'$, but $\operatorname{hcf}(x',n')=1$, so $n'|o(\bar x)$, therefore $n'=o(\bar x)$.
    (ii)Let $o((g,h))=n$, $\operatorname{lcm}\{o(g),o(h)\}=m$.
    $n(g,h)=(ng,nh)=(e,e)$, so $o(g)|n,o(h)|n$, so $m|n$. On the other hand, $m(g,h)=(mg,mh)=(e,e)$, so $n|m$. Therefore $n=m$.
  2. $\bar{x}\in\mathbb{Z}_n$ is said to be a unit if there exists $\bar{y} \in \mathbb{Z}_n$ such that $\bar{x} \bar{y}=\overline1\pmod n$.
    (i) Show that the units of $\mathbb{Z}_{n}$ form a group under multiplication. We denote this group $\mathbb{Z}_{n}^{*}$.
    (ii) Use Bézout's Lemma to show that $\bar{x}$ is a unit of $\mathbb{Z}_{n}$ if and only if $\operatorname{hcf}(x, n)=1$.
    (iii) List the units in $\mathbb{Z}_9$ and write out the Cayley table for $\mathbb{Z}_9^*$.
    (iv) Show that $\mathbb{Z}_9^*$ is cyclic. What are the generators of $\mathbb{Z}_9^*$ ?
    Proof.
    (i) Let $\overline{x_1},\overline{x_2}$ be units of $\Bbb Z_n$, then there exists $\overline{y_1},\overline{y_2}$ such that $\overline{x_1}\overline{y_1}=\overline{x_2}\overline{y_2}=\overline{1}\pmod n$, then $\overline{x_1}\overline{y_1}(\overline{x_2}\overline{y_2})^{-1}=\overline1\pmod n$, $\overline{x_1}(\overline{x_2})^{-1}\overline{y_1}(\overline{y_2})^{-1}=\overline1\pmod n$, therefore $\overline{x_1}(\overline{x_2})^{-1}$ is a unit, therefore the units of $\Bbb Z_n$ form a group under multiplication.
    (ii)If $\operatorname{hcf}(x, n)=1$, by Bézout's Lemma, $∃a,b\in\mathbb Z:ax+bn=1$, so $\bar a\bar x=1\pmod n$, so $\bar x$ is a unit of $\Bbb Z_n$.
    If $\bar x$ is a unit of $\Bbb Z_n$, then $∃a\in\mathbb Z:\bar a\bar x=1\pmod n$, so $∃b\in\mathbb Z:ax+bn=1$. Since $\operatorname{hcf}(x, n)|a$ and $\operatorname{hcf}(x, n)|b$, we have $\operatorname{hcf}(x, n)|ax+bn=1$, so $\operatorname{hcf}(x, n)=1$.
    (iii)Units in $\mathbb{Z}_9$:1,2,4,8,7,5\begin{array}{c|cc}\Bbb Z_9^*&1&2&4&8&7&5\\\hline1&1&2&4&8&7&5\\2&2&4&8&7&5&1\\4&4&8&7&5&1&2\\8&8&7&5&1&2&4\\7&7&5&1&2&4&8\\5&5&1&2&4&8&7\end{array}(iv)$⟨2⟩=\{1,2,4,8,7,5\}=\Bbb Z_9^*$, so $\Bbb Z_9^*$ is cyclic. generators:2,5
  3. (i) Use Fermat's Little Theorem to compute $5^{15}\pmod 7$ and $7^{13}\pmod{11}$.
    (ii) Use the Fermat-Euler Theorem to compute $4^{43}\pmod{15}$ and $2^{51}\pmod{21}$.
    (iii) Show that $5^{14}=10\pmod{15}$. [You might try to find $5^{14}$ modulo 3 and modulo 5 first.]
    Solution.
    (i)$5^{15}\pmod 7=(5^6)^25^3\pmod 7=5^3\pmod 7=6$, $7^{13}\pmod{11}=7^{10}7^3\pmod{11}=7^3\pmod{11}=2$
    (ii)$\phi(15)=2·4=8⇒4^{43}\pmod{15}=4^{5·8+3}\pmod{15}=4^3\pmod{15}=4$, $\phi(21)=2·6=12⇒2^{51}\pmod{21}=2^{12·4+3}\pmod{21}=2^3\pmod{21}=8$
    (iii)$5^{14}\pmod{3}=5^{2·7}\pmod{3}=1,5^{14}\pmod{5}=0,$ by the Chinese Remainder theorem, $5^{14}=10\pmod{15}$.
  4. Let $p$ be a prime and let $g,h$ be elements, both of order $p$, in a group $G$. What are the possible orders of $\langle g\rangle\cap\langle h\rangle$ ?
    Show that if $G$ is finite then the number of elements of order $p$ in $G$ is a multiple of $p-1$.
    Proof.
    $\langle g\rangle\cap\langle h\rangle\le\langle g\rangle$ but $\langle g\rangle$ has order $p$. By Lagrange's theorem, $\langle g\rangle\cap\langle h\rangle$ has order 1 or $p$. If $|⟨g⟩∩⟨h⟩|=p$, then $⟨g⟩=⟨h⟩$.
    If $G$ is finite then elements of order $p$ in $G$ are partitioned into sets $⟨g_i⟩∖\{e\}$ of $p-1$ elements, so the number of elements of order $p$ is a multiple of $p-1$.
    Deduce that a group of order 35 contains an element of order 5 and an element of order 7 .
    Proof.
    By Lagrange's theorem, every element must have order 1, 5, 7, or 35. If there is an element $g$ of order 35 then the group is cyclic, then $g^5$ has order 7, and $g^7$ has order 5.
    Now suppose there is no element of order 35. Only the identity has order 1, so every non-identity element must have order 5 or order 7.
    We proved the number of elements of order 5 is a multiple of 4 and the number of elements of order 7 is a multiple of 6, neither can fill out 34 non-identity elements, so there exists an element of order 5 and an element of order 7.
  5. (i)Suppose that every element $x$ in a group $G$ satisfies $x^2=e$. Prove that $G$ is Abelian.
    (ii)Show also that if $H$ is any subgroup of $G$ and $g \in G \backslash H$ then $K=H\cup gH$ is a subgroup of $G$.
    (iii)Show further that $K$ is isomorphic to $H×C_2$.
    (iv)Deduce that if $G$ is finite then $G$ is isomorphic to $\left(\mathbb{Z}_2\right)^n$ for some non-negative integer $n$.
    Proof.
    (i)∀$x,y∈G$, $xy=(xy)^{-1}=y^{-1}x^{-1}=yx$, so $G$ is Abelian.
    (ii)∀$x,y∈H\cup gH$, if $x,y∈H$, $xy^{-1}∈H$, so $xy^{-1}∈H\cup gH$; if $x∈H,y∈gH$, then $∃y'∈H:y=gy'$, $xy^{-1}=g(xy')∈gH$; if $x∈gH,y∈H$, similar to previous case; if $x,y∈gH$, then $∃x',y'∈H:x=gx',y=gy'$, $xy^{-1}=x'y'∈H$. Hence $H\cup gH$ is a subgroup of $G$.
    (iii)Consider a map $f:H×C_2→K,C_2=⟨a⟩,f(h,e)=h,f(h,a)=gh$. Clearly $f$ is bijective. $(h_1,e)(h_2,e)=(h_1h_2,e),f(h_1,e)f(h_2,e)=h_1h_2=f(h_1h_2,e)$; $(h_1,a)(h_2,e)=(h_1h_2,a),f(h_1,a)f(h_2,e)=gh_1h_2=f(h_1h_2,a)$; $(h_1,e)(h_2,a)=(h_1h_2,a),f(h_1,e)f(h_2,a)=h_1gh_2=gh_1h_2=f(h_1h_2,a)$; $(h_1,a)(h_2,a)=(h_1h_2,e),f(h_1,a)f(h_2,a)=gh_1gh_2=g^2h_1h_2=h_1h_2=f(h_1h_2,e)$. Therefore $g$ is an isomorphism from $H×C_2$ to $K$.
    (iv)If $G$ is cyclic then $|G|=1,2$ so $G≌\{e\},\Bbb Z_2$. If $G$ is non-cyclic, take $g,h∈H∖\{e\},g\notin H=⟨h⟩$, by (iii) we construct an infinite sequence $H<K<⋯$, such that $K≌H×\Bbb Z_2,⋯$. Since $G$ is finite, the sequence terminate at $G$ then $G\cong\left(\mathbb{Z}_2\right)^n$ for some non-negative integer $n$.
  6. Let $G_1$ and $G_2$ be finite groups and let $K \leqslant G_1\times G_2$.
    (i) Set $H_1=\left\{g \in G_1:(g, e)\in K\right\}$ and $H_2=\left\{g \in G_2:(e, g) \in K\right\}$. Show that$$H_1\leqslant G_1;\quad H_2\leqslant G_2;\quad H_1\times H_2\leqslant K.$$(ii) Suppose that $\left|G_1\right|$ and $\left|G_2\right|$ are coprime. Show that $K=H_1×H_2$.
    (iii) Show that this result need not follow if $\left|G_1\right|$ and $\left|G_2\right|$ are not coprime.
    Proof.
    (i)From $(e,e)∈K$ we have $e\in H_1,e\in H_2$. $∀g_1,g_2\in H_1$, we have $(g_1,e),(g_2,e)\in K$, then $(g_1g_2^{-1},e)=(g_1,e)(g_2,e)^{-1}\in K$, so $g_1g_2^{-1}\in H_1$, so $H_1\le G_1$. Similarly $H_2\le G_2$. $∀(g_1,g_2),(h_1,h_2)\in H_1\times H_2$, we have $(g_1,e),(e,g_2),(h_1,e),(e,h_2)\in K$, then $(g_1,g_2)(h_1,h_2)^{-1}=(g_1h_1^{-1},g_2h_2^{-1})=(g_1,e)(e,g_2)(h_1,e)^{-1}(e,h_2)^{-1}\in K$, so $H_1×H_2\le K$.
    (ii)Suppose $a = |G_1|,b = |G_2|,$ are coprime, by Bézout's theorem, there are integers $u,v$ such that $au + bv = 1$.
    Let $(g_1, g_2) \in K$. Applying Lagrange's theorem to $G_1$, $g_1^a = e$, so $e=g_1^{au}=g_1^{1-bv}$, so $g_1^{bv} = g_1$, and similarly $g_2^{au} = g_2$.
    $(g_1, g_2)^{bv}= (g_1^{bv}, g_2^{bv}) =(g_1,e)∈K$, by definition $g_1 \in H_1$. Similarly using $g_2^{au} = g_2$, we get $g_2 \in H_2$.
    Since $(g_1,g_2)$ is an arbitrary element of $K$, we have $K\subset H_1×H_2$, but from (i), $H_1×H_2≤K$, therefore $K=H_1×H_2$.
    (iii)$G_1=G_2=\Bbb Z_2,K=\{(0,0),(1,1)\}$, then $H_1=H_2=\{0\}$, so $H_1×H_2=\{(0,0)\}≠K$.
    S1. In this question we work in $\mathbb{Z}_8$. For each $a\in\mathbb{Z}_8$, find $a^7$. How does this relate to Fermat's Little Theorem and to the Fermat-Euler Theorem?\begin{array}{c|cccccccc}a& 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\a^7& 0 & 1 & 0 & 3 & 0 & 5 & 0 & 7\end{array}This shows that Fermat's Little Theorem doesn't hold in $\mathbb{Z}_{8}$ : we don't have $a^{7} \equiv 1\pmod{8}$ for all $a$ coprime to 8. Of course, the theorem only claimed that this would hold for primes, and 8 is not prime, so this is not a counterexample, but it does show that we cannot simply extend the result to non-primes.
    We have $\phi(8)=4$, so the Fermat-Euler Theorem says that $a^4\equiv 1\pmod{8}$ for all $a$ coprime to 8. This does not tell us about 7 th powers. In fact, we find that $a^{2} \equiv 1\pmod{8}$ for all $a$ coprime to 8, so in this case there is a stronger result than Fermat-Euler.
    S2. Consider the dihedral group $D_{8}=\left\{e, r, r^{2}, r^{3}, s, r s, r^{2} s, r^{3} s\right\}$ with the notation from lectures. Find all the left cosets of $\langle r\rangle$ in $D_{8}$. Find all the right cosets of $\langle r\rangle$. How do these lists compare? Now repeat for the subgroup $\langle s\rangle$.
    We have $\langle r\rangle=\left\{e, r, r^{2}, r^{3}\right\}$. Now we find the left cosets of $\langle r\rangle$ in $D_{8}$.\begin{align*} e\langle r\rangle &=\left\{e, r, r^{2}, r^{3}\right\} \\ r\langle r\rangle &=\left\{r, r^{2}, r^{3}, e\right\} \\ r^{2}\langle r\rangle &=\left\{r^{2}, r^{3}, e, r\right\} \\ r^{3}\langle r\rangle &=\left\{r^{3}, e, r, r^{2}\right\} \\ s\langle r\rangle &=\left\{s, r^{3} s, r^{2} s, r s\right\} \\ r s\langle r\rangle &=\left\{r s, s, r^{3} s, r^{2} s\right\} \\ r^{2} s\langle r\rangle &=\left\{r^{2} s, r s, s, r^{3} s\right\} \\ r^{3} s\langle r\rangle &=\left\{r^{3} s, r^{2} s, r s, s\right\} \end{align*}—so there are two left cosets of $⟨r⟩$ in $D_8$, as we expect from Lagrange’s theorem (since $|D_8| = 8$ and $|⟨r⟩| = 4$.)
    And the right cosets:\begin{align*} \langle r\rangle e &=\left\{e, r, r^{2}, r^{3}\right\} \\ \langle r\rangle r &=\left\{r, r^{2}, r^{3}, e\right\} \\ \langle r\rangle r^{2} &=\left\{r^{2}, r^{3}, e, r\right\} \\ \langle r\rangle r^{3} &=\left\{r^{3}, e, r, r^{2}\right\} \\ \langle r\rangle s &=\left\{s, r s, r^{2} s, r^{3} s\right\} \\ \langle r\rangle r s &=\left\{r s, r^{2} s, r^{3} s, s\right\} \\ \langle r\rangle r^{2} s &=\left\{r^{2} s, r^{3} s, s, r s\right\} \\ \langle r\rangle r^{3} s &=\left\{r^{3} s, s, r s, r^{2} s\right\} \end{align*}There are two right cosets, and in fact the left cosets are the same as the right cosets (we have $g\langle r\rangle=\langle r\rangle g$ for all $g ∈ D_8$). This relates to the notion of a normal subgroup, which will play an important role in the second half of this course.
    Now $⟨s⟩=\{e,s\}$, and the left cosets of $⟨s⟩$ in $D_8$ are\begin{align*} e\langle s\rangle &=\{e, s\} \\ r\langle s\rangle &=\{r, r s\} \\ r^{2}\langle s\rangle &=\left\{r^{2}, r^{2} s\right\} \\ r^{3}\langle s\rangle &=\left\{r^{3}, r^{3} s\right\} \\ s\langle s\rangle &=\{s, e\} \\ r s\langle s\rangle &=\{r s, r\} \\ r^{2} s\langle s\rangle &=\left\{r^{2} s, r^{2}\right\} \\ r^{3} s\langle s\rangle &=\left\{r^{3} s, r^{3}\right\} \end{align*}while the right cosets are\begin{align*} \langle s\rangle e &=\{e, s\} \\ \langle s\rangle r &=\left\{r, r^{3} s\right\} \\ \langle s\rangle r^{2} &=\left\{r^{2}, r^{2} s\right\} \\ \langle s\rangle r^{3} &=\left\{r^{3}, r s\right\} \\ \langle s\rangle s &=\{s, e\} \\ \langle s\rangle r s &=\left\{r s, r^{3}\right\} \\ \langle s\rangle r^{2} s &=\left\{r^{2} s, r^{2}\right\} \\ \langle s\rangle r^{3} s &=\left\{r^{3} s, r\right\} \end{align*}Lagrange’s theorem tells us that we should have 4 different left cosets (and 4 different right cosets), and indeed we do.
    Note that this time it is not always the case that the left and right cosets are the same, for example $r\langle s\rangle \neq\langle s\rangle r$. Again, this relates to the concept of a normal subgroup-more precisely, it shows that $\langle s\rangle$ is not a normal subgroup of $D_{8}$, whereas $\langle r\rangle$ is.
    S3. For each of the following, give a proof or a counterexample.
    (i) A group with order 20 cannot have a subgroup of order 10.
    (ii) A group with order 22 cannot have a subgroup of order 10.
    (iii) A group with order 10 cannot have a subgroup of order 22.
    (iv) A group with order 10 must have a subgroup of order 10.
    (v) A group with order 12 must have a subgroup of order 6.
    Solution.
    (i) This is false. For example, consider $C_{20}=\langle g\rangle$, then the subgroup $\left\langle g^{2}\right\rangle$ has order 10.
    (ii) This is true, by Lagrange's Theorem, because $10 \nmid 22$.
    (iii) This is true, because any subgroup of a group of order 10 contains at most 10 elements.
    (iv) This is true, because if $G$ is a group with order 10, then $G$ is a subgroup of order 10.
    (v) This is false. The alternating group $A_4$ has order 12, but contains no subgroup of order 6.

    P1. Let $F=2^{32}+1$. Let $p$ be a prime dividing $F$. What is the order of 2 in $\mathbb{Z}_{p}^{*}$ ? Deduce that $p \equiv 1\pmod{64}$. Use this to show that $F$ is not prime.
    Solution.
    If $p \mid F$, then $F \equiv 0\pmod{p}$, so $2^{32} \equiv-1\pmod{p}$. Squaring both sides gives $2^{64} \equiv 1\pmod{p}$, which means that the order of 2 in $\mathbb{Z}_p^*$ divides 64. But since $2^{32}$ is not 1 in $\mathbb{Z}_{p}^{*}$, the order does not divide 32, so in fact the order of 2 in $\mathbb{Z}_{p}^{*}$ is exactly 64 .
    Now Fermat's Little Theorem (since $p$ is prime and 2 is certainly coprime to $p$) tells us that $2^{p-1} \equiv 1\pmod{p}$, and hence the order of 2 in $\mathbb{Z}_p^*$ divides $p-1$, so $p \equiv 1\pmod{64}$.
    This significantly shrinks the pool of potential prime factors of $F$, so we can just go through and check. We find that $F=4294967297$, and if we check numbers of the form $1+64 k$ for $k \geqslant 1$ (even without worrying whether these numbers are prime), we find that 641 is a factor of $F$, and so $F$ is not prime.
    The number $F$ in this question is a Fermat number: it is of the form $2^{2^{n}}+1$. In fact it is the smallest Fermat number not to be a prime. This has an interesting history, and you can read more about it.
    P2. We say that $n \geqslant 2$ is a Carmichael number if $n$ is not prime and $a^{n-1} \equiv 1\pmod n$ for all $a$ coprime to $n$. Show that if $n=(6 k+1)(12 k+1)(18 k+1)$ where $k$ is a positive integer such that $6 k+1,12 k+1$ and $18 k+1$ are all prime, then $n$ is a Carmichael number. Use this construction to find two Carmichael numbers.
    Solution.
    Take $n=(6 k+1)(12 k+1)(18 k+1)$ where $6 k+1,12 k+1$ and $18 k+1$ are all prime. Take $a$ coprime to $n$.
    Then certainly $a$ is coprime to $6 k+1$, to $12 k+1$ and to $18 k+1$, and so by Fermat's Little Theorem we have\begin{align*}a^{6 k} & \equiv 1 & &\pmod{6k+1} \\a^{12 k} & \equiv 1 & &\pmod{12k+1} \\a^{18 k} & \equiv 1 & &\pmod{18k+1}\end{align*}Thus $a^{36 k} \equiv 1\pmod{p}$ where $p$ is each of the primes $6 k+1,12 k+1$ and $18 k+1$.
    A quick piece of algebra shows that $36 k$ divides $n-1$, and so $a^{n-1} \equiv 1\pmod{p}$ where $p$ is each of the three primes.
    Now $6 k+1,12 k+1$ and $18 k+1$ are pairwise coprime and each divide $a^{n-1}-1$, so their product divides $a^{n-1}-1$, so $a^{n-1} \equiv 1\pmod n$.
    This shows that $n$ is a Carmichael number.
    Taking $k=1,6$ (where happily the factors all turn out to be prime) gives the Carmichael numbers $7 \times 13 \times 19=1729$ and $37 \times 73 \times 109=291708$.
    There are many interesting things to say about Carmichael numbers. A very readable place to start would be this article by Andrew Granville (one of the three mathematicians who, in 1992, proved that there are infinitely many Carmichael numbers)
    P3. Let $G$ be a group of order $n$ with a subgroup $H$ of order $n-1$. What can you say about $n$?
    Solution.
    By Lagrange's Theorem, we see that $n-1 \mid n$. But then $n-1$ divides both $n-1$ and $n$, so it divides their difference $n-(n-1)=1$. Since $n-1 \geqslant 1$, we see that in fact $n-1=1$, so $n=2$.
    This tells us that $G$ is isomorphic to $C_{2}$, which is (up to isomorphism) the only group of order 2.