Homework 15

Read: Continue with Section 4.1.

Turn in: 4.12(d,f,g,l), 4.14, 4.19, 4.24, 4.25

• 4.19 is a challenging one. There are several things to show: assuming $n$ is the smallest positive integer such that $g^n=e$, you want to prove (1) that $\langle g \rangle = \{e,g,g^2,\ldots,g^{n-1}\}$ and (2) that the elements in the list $e,g,g^2,\ldots,g^{n-1}$ are all distinct.

  For (1), you are proving equality of sets. Note that $\{e,g,g^2,\ldots,g^{n-1}\}\subseteq \langle g \rangle$ follows quickly from the definition of $\langle g \rangle$. To show $\langle g \rangle \subseteq \{e,g,g^2,\ldots,g^{n-1}\}$, you want to prove that for any $m\in \mathbb{Z}$, $g^m$ is equal to one of $e,g,g^2,\ldots,g^{n-1}$. The Division Algorithm (Theorem 4.16) is very helpful: write $m = nq+r$ with $0\le r < n$ and then $g^m = g^{nq +r}$. Keep going (using that $g^n=e$)…

  For (2), assume (towards a contradiction) that $g^i = g^j$ for $0\le i< j < n$. Try to manipulate things to contradict that $n$ is the smallest positive integer such that $g^n=e$.

• Note that 4.24 is an “if and only if” statement, so there are two things to show. For the “backward” direction, you will assume that $n$ divides $i-j$; what does this imply about $g^{i-j}$? For the “forward” direction, you assume $g^i = g^j$ and want to prove that $n$ divides $i-j$. One strategy for proving that $n$ divides $i-j$ is to use the division algorithm to write $i-j = qn +r$ for some $0\le r < n $ (where $r$ represents the remainder); then work to prove that $r = 0$.

• For 4.25, you should use 4.24 (even if you haven’t fully completed the proof of 4.24).

Extra practice: 4.12(all parts you didn’t turn in), 4.13, 4.17, 4.18, 4.22, 4.23

• When thinking about 4.17, make sure to read the hint in the paragraph right before the statement of the theorem. Remember that $\langle g\rangle = \{\ldots,g^{-2},g^{-1},e,g,g^2,\ldots\}$, so if $\langle g\rangle$ is finite, there must be repetitions in the list. For the reverse direction, assume that $g^n = e$, and try to use this to prove that for any $m\in \mathbb{Z}$, $g^m$ is equal to one of $e,g,g^2,\ldots,g^{n-1}$. This would show that $\langle g\rangle \subseteq \{e,g,g^2,\ldots,g^{n-1}\}$, implying that $\langle g\rangle$ is finite. The Division Algorithm (Theorem 4.16) is very helpful: notice that $g^{nq +r} = (g^{n})^qg^r$.