## Monthly Archives: January 2010

### Characterize the normalizer of a cyclic subgroup

Let $G$ be a finite group and let $x \in G$.

1. Prove that if $g \in N_G(\langle x \rangle)$ then $gxg^{-1} = x^a$ for some integer $a$.
2. Show conversely that if $gxg^{-1} = x^a$ for some integer $a$, then $g \in N_G(\langle x \rangle)$. [Hint: Show first that $gx^kg^{-1} = (gkg^{-1})^k = x^{ak}$ for any integer $k$, so that $g \langle x \rangle g^{-1} \leq \langle x \rangle$. If $x$ has order $n$, show that the elements $gx^ig^{-1}$ are distinct for $i \in \{ 0, 1, \ldots, n-1 \}$, so that $|g \langle x \rangle g^{-1}| = |\langle x \rangle| = n$ and conclude that $g \langle x \rangle g^{-1} = \langle x \rangle$.]

1. Let $g \in N_G(\langle x \rangle)$. By definition, we have $gxg^{-1} \in \langle x \rangle$, so that $gxg^{-1} = x^a$ for some integer $a$.
2. We prove some lemmas.

Lemma 1: Let $G$ be a group and let $x,g \in G$. Then for all integers $k$, $gx^kg^{-1} = (gxg^{-1})^k$. Proof: First we prove the conclusion for nonnegative $k$ by induction on $k$. If $k = 0$, we have $gx^0g^{-1} = gg^{-1} = 1 = (gxg^{-1})^0$. Now suppose the conclusion holds for some $k \geq 0$; then $gx^{k+1}g^{-1} = gxx^kg^{-1}$ $= gxg^{-1}gx^kg^{-1}$ $= gxg^{-1}(gxg^{-1})^k$ $= (gxg^{-1})^{k+1}$. By induction, the conclusion holds for all nonnegative $k$. Now suppose $k < 0$; then $gx^kg^{-1} = (gx^{-k}g^{-1})^{-1}$ $= (gxg^{-1})^{-k^{-1}}$ $= (gxg^{-1})^k$. Thus the conclusion holds for all integers $k$. $\square$

Lemma 2: Let $G$ be a group and let $x,g \in G$ such that $gxg^{-1} = x^a$ for some integer $a$. Then $g \langle x \rangle g^{-1}$ is a subgroup of $\langle x \rangle$. Proof: Let $gx^kg^{-1} \in g \langle x \rangle g^{-1}$; by Lemma 1 we have $gx^kg^{-1} = (gxg^{-1})^k = x^{ak}$, so that $gxg^{-1} \in \langle x \rangle$. Thus $g \langle x \rangle g^{-1} \subseteq \langle x \rangle$. Now let $gx^bg^{-1}, gx^cg^{-1} \in g \langle x \rangle g^{-1}$. Then $gx^bg^{-1}(gx^cg^{-1})^{-1}$ $= gx^bg^{-1}gx^{-c}g^{-1}$ $= gx^{b-c}g^{-1}$ $\in g \langle x \rangle g^{-1}$. By the Subgroup Criterion, then, $g \langle x \rangle g^{-1} \leq \langle x \rangle$. $\square$

Lemma 3: Let $G$ be a group and let $x,g \in G$ such that $gxg^{-1} = x^a$ for some integer $a$ and such that $|x| = n$, $n \in \mathbb{Z}$. Then $gx^ig^{-1}$ are distinct for $i \in \{ 0, 1, \ldots, n-1 \}$. Proof: Choose distinct $i,j \in \{ 0, 1, \ldots, n-1 \}$. By a previous exercise, $x^i \neq x^j$. Suppose now that $gx^ig^{-1} = gx^jg^{-1}$; by cancellation we have $x^i = x^j$, a contradiction. Thus the $gx^ig^{-1}$ are distinct. $\square$

Now to the main result; suppose $gxg^{-1} = x^a$ for some integer $a$. Since $G$ has finite order, $|x| = n$ for some $n$. By Lemma 2, $g \langle x \rangle g^{-1} \leq \langle x \rangle$, and by Lemma 3 we have $|g \langle x \rangle g^{-1}| = |\langle x \rangle|$. Since $G$ is finite, then, we have $g \langle x \rangle g^{-1} = \langle x \rangle$. Thus $g \in N_G(\langle x \rangle)$.

### The group of units in ZZ/(2^n) is not cyclic for n at least 3

Show that $(\mathbb{Z}/(2^n))^\times$ is not cyclic for any $n \geq 3$. (Hint: find two distinct subgroups of order 2.)

Note that $(2^n-1)^2 = (-1)^2 = 1$ mod $2^n$, so $\langle 2^n-1 \rangle$ is a subgroup of order 2 in $(\mathbb{Z}/(2^n))^\times$. Moreover, by the previous exercise, $(1 + 2^{n-1})^2 = 1$ mod $2^n$, so $\langle 1 + 2^{n-1} \rangle$ is also a subgroup of order 2. Clearly these two are not equal since $n \neq 1$; thus $(\mathbb{Z}/(2^n))^\times$ has two distinct subgroups of order 2. Thus $(\mathbb{Z}/(2^n)^\times$ is not cyclic.

### Compute the order of 5 in the integers mod a power of 2

Let $n$ be an integer with $n \geq 3$. Use the Binomial Theorem to show that $(1+2^2)^{2^{n-2}} = 1$ mod $2^n$ but that $(1+2^2)^{2^{n-3}} \neq 1$ mod $2^n$. Deduce that 5 is an element of order $2^{n-2}$ in the group $(\mathbb{Z}/(2^n))^\times$.

We begin with some lemmas.

Lemma 1: Let $k$ be a positive integer and write $k = 2^m \cdot a$, where $2$ does not divide $a$. Then $m+2 \leq 2k$. Proof: If $k = 1$, we have $m=0$. Then $0 + 2 \leq 2 \cdot 1$, so the conclusion holds for $k=1$. If $k \geq 2$, we have $m < k$ by a lemma to a previous exercise; then $m+2 < k+k = 2k$. Thus the lemma holds for $k \geq 2$. $\square$

Lemma 2: Let $k$ be a positive integer with $k \geq 2$, and write $k = 2^m \cdot a$ where $2$ does not divide $a$. Then $m+3 \leq 2k$. Proof: If $k = 2$, we have $m = 1$. Then $1+3 \leq 2 \cdot 2$, so the conclusion holds. If $k \geq 3$, we have $m < k$ by a lemma to the previous exercise. Now $m+3 < k+k = 2k$, so the conclusion holds for all $k \geq 3$. $\square$.

Now to the main result.

By the Binomial Theorem, we have

 $(1+2^2)^{2^{n-2}} = \displaystyle\sum_{k=0}^{2^{n-2}} {2^{n-2} \choose k} \cdot 2^{2k}.$

Now by a lemma to the previous problem, if $2$ divides $k$ $m_k$ times, then $2$ divides $p^{n-2} \choose k$ $n-m-2$ times. Thus we have

 $(1+2^2)^{2^{n-2}} = \displaystyle\sum_{k=0}^{2^{n-2}} 2^{n+2k-m_k-2} \cdot \beta_k,$

for some integers $\beta_k$. Now by Lemma 1, $2k \geq m_k+2$ for all $k \geq 1$, so that $n+2k-m_k-2 \geq n$. Modulo $2^n$, all terms with $k \geq 1$ are zero, leaving only the $k=0$ term; thus we have

 $(1+2^2)^{2^{n-2}} \equiv 1\ \mathsf{mod}\ 2^n.$

We now consider $(1+2^2)^{2^{n-3}}$. Again by the Binomial Theorem,

 $(1+2^2)^{2^{n-3}} = \displaystyle\sum_{k=0}^{2^{n-3}} {2^{n-3} \choose k} \cdot 2^{2k},$

and using a lemma to the previous problem, if $2$ divides $k$ $m_k$ times, we have (for some integers $\beta_k$)

 $(1+2^2)^{2^{n-3}} = \displaystyle\sum_{k=0}^{2^{n-3}} 2^{n+2k-m_k-3} \cdot \beta_k.$

By Lemma 2, for all $k \geq 2$ we have $n+2k-m_k-3 \geq n$, so that, modulo $2^n$, these terms vanish. This leaves only the $k=0$ and $k=1$ terms. Thus,

 $(1+2^2)^{2^{n-3}} = 1 + 2^{n-1}$,

which is not 1 mod $2^n$.

Thus, $|5|$ divides $2^{n-2}$ but does not divide $2^{n-3}$, so that we have $|5| = 2^{n-2}$ in $(\mathbb{Z}/(2^n))^\times$.

### Use the Binomial Theorem to compute the order of an element in the integers mod a prime power

Let $p$ be an odd prime and $n$ a positive integer. Use the Binomial Theorem to show that $(1+p)^{p^{n-1}} = 1\ \mathsf{mod}\ p^n$ but that $(1+p)^{p^{n-2}} \neq 1\ \mathsf{mod}\ p^n$. Deduce that $1+p$ is an element of order $p^{n-1}$ in $(\mathbb{Z}/(p^n))^\times$.

First we prove some lemmas.

Lemma 1: Let $a$, $b$, and $c$ be integers. If $c$ divides $ab$ and $\mathsf{gcd}(a,c)= 1$, then $c$ divides $b$. Proof: We have integers $k$, $x$, and $y$ such that $ab = kc$ and $ax + cy = 1$. Now $ax = 1-yc$ and $axb= cxk$, so that $b = c(xk+yb)$. $\square$

Lemma 2: Let $n \in \mathbb{Z}^+$, let $p$ be a prime, and let $1 \leq k \leq p^n$. If $p$ divides $k$ $m$ times, then $p$ divides $p^n \choose k$ $n-m$ times. Proof: We proceed by induction on $k$. For the base case $k = 1$, we have ${p^n \choose 1} = p^n = p^{n-0}$. For the inductive step, let $1 \leq k < p^n$. Suppose that $p$ divides $k$ $\ell$ times, divides $k+1$ $m$ times, and divides $p^n \choose k$ $n-\ell$ times. Note that $\ell \leq n$. Now we have $k = p^\ell \cdot Q$, $k+1 = p^m \cdot R$, and ${p^n \choose k} = p^{n-\ell} \cdot S$, where $p$ does not divide $Q$, $R$, and $S$. Note that

 $p^n \choose k$ = ${p^n \choose k} \cdot \frac{p^n - k}{k+1}$ = $\frac{p^{n-\ell}\cdot S \cdot (p^n-p^\ell \cdot Q)}{p^m \cdot R}$ = $p^{n-m} \cdot \frac{S \cdot (p^{n-\ell} - Q)}{R}.\ (1)$

Now (1) is an integer and $\mathsf{gcd}(R,p^{n-m}) = 1$, so by Lemma 1, $R$ divides $S \cdot (p^{n-\ell} - Q)$. Moreover, $p$ does not divide $S$ or $p^{n-\ell} - Q$ (as otherwise $p$ would divide $Q$) so that, since $p$ is prime, $p$ does not divide $\frac{S \cdot (p^{n-\ell} - Q)}{R}$. Thus the highest power of $p$ which divides $p^n \choose k+1$ is $n-m$. Thus the lemma holds for $k+1$, and by induction holds for all $1 \leq k \leq p^n$. $\square$

Lemma 3: Let $p$ be a prime and $k$ a positive integer. If $p$ divides $k$ $m$ times, then $m < k$. Proof: Suppose to the contrary that $m \geq k$; then we have $k = p^m \cdot \alpha$ for some $\alpha$. Moreover, $k < p^k$ $\leq p^m$ $\leq p^m \cdot \alpha = k$, a contradiction. So $m < k$. $\square$.

Lemma 4: Let $a,b \in \mathbb{Z}$ with $a \geq 1$ and $b \geq 3$. Then $a+1 < b^a$. Proof: First we prove the case $b = 3$ by induction. Note that if $a = 1$, we have $1+1 = 2$ $< 3 = 3^1$. Suppose now that the lemma holds for some $a \geq 3$. Then $(a+1)+1 < 3^a + 1$ $< 3 \cdot 3^a$ $= 3^{a+1}$; thus the lemma holds for all $a$ and $b=3$. Now let $b \geq 3$; $a+1 < 3^{a+1} \leq b^{a+1}$. Thus the lemma holds. $\square$

Lemma 5: Let $p$ be an odd prime and $k$ a positive integer. If $p$ divides $k$ $m$ times, then $m+1 < k$. Proof: Suppose $k = p^m \cdot \alpha$. Then by Lemma 4, $m+1 < p^m \leq p^m \cdot \alpha = k$. $\square$

Now to the main result. Recall the Binomial Theorem:

 $(a+b)^n = \displaystyle\sum_{k=0}^n \left( {n \atop k} \right) a^{n-k} b^k.$

In our case, we have

 $(1+p)^{p^{n-1}} = \displaystyle\sum_{k=0}^{p^{n-1}} \left( {p^{n-1} \atop k} \right) p^k.$

By Lemma 2 above, note that ${p^{n-1} \choose k} = p^{n-m_k-1} \cdot \beta_k$, where $m_k$ is the highest power of $p$ dividing $k$ and $p$ does not divide $\beta_k$. Thus

 $(1+p)^{p^{n-1}} = \displaystyle\sum_{k=0}^{p^{n-1}} p^{n-m_k+k-1} \cdot \beta_k.$

Now since $m_k < k$ by Lemma 3, $k-m_k \geq 1$. So $n+k-m_k-1 \geq n$ for all $k \geq 1$. Modulo $p^n$, the only nonzero term is the $k = 0$ term, which is clearly 1. Thus $(1+p)^{p^{n-1}} = 1$ mod $p^n$.

Consider now $(1+p)^{p^{n-2}}$. As before, by Lemma 2, for each $k$ we have ${p^{n-2} \choose k} = p^{m_k} \cdot \beta_k$, where $p$ divides $k$ $m_k$ times and does not divide $\beta_k$. By the Binomial theorem, we have

 $(1+p)^{p^{n-2}}$ = $\displaystyle\sum_{k=0}^{p^{n-2}} {p^{n-2} \choose k} p^k$ = $\displaystyle\sum_{k=0}^{p^{n-2}} p^{n+k-m_k-2} \cdot \beta_k$.

By Lemma 5 above, if $k \geq 2$ then $k \geq m_k - 2$. Thus $n + k - m_k - 2 \geq n$, so that, modulo $p^n$, all terms with $k \geq 2$ are 0. Thus we have

 $(1+p)^{p^{n-2}} = 1 + p^{n-1}.$

Hence $(1+p)^{p^{n-2}} \neq 1$ mod $p^n$.

Finally, recall that for any element $x$ in a group $G$, $x^n = 1$ if and only if $n$ divides $|x|$. Thus we see that in $(\mathbb{Z}/(p^n))^\times$, $|1+p|$ divides $p^{n-1}$ but not $p^{n-2}$; hence $|1+p| = p^{n-1}$. $\blacksquare$

### If a prime power power of a group element is trivial, then the order of the element is a prime power

Let $p$ be a prime and $n$ a positive integer. Show that if $x$ is an element of a group $G$ such that $x^{p^n} = 1$, then $|x| = p^m$ for some $1 \leq m \leq n$.

We prove a lemma.

Lemma: Let $G$ be a group and $x \in G$ an element of finite order, say, $|x| = n$. If $x^m = 1$, then $n$ divides $m$. Proof: Suppose to the contrary that $n$ does not divide $m$; then by the Division Algorithm there exist integers $q$ and $r$ such that $0 < r < |n|$ and $m = qn + r$. Then we have $1 = x^m = x^{qn+r}$ $= (x^n)^q + x^r = x^r$. But recall that by definition $n$ is the least positive integer with this property, so we have a contradiction. Thus $n$ divides $m$. $\square$

The main result then follows because every divisor of $p^n$ is of the form $p^m$.

### There is a unique group homomorphism from ZZ to any group where the image of 1 is fixed

Show that if $H$ is a group and $h \in H$, there exists a unique homomorphism $\varphi : \mathbb{Z} \rightarrow H$ such that $\varphi(1) = h$.

Existence: Define $\varphi(n) = h^n$. We need not worry about well-definedness for $\varphi$. For all $m,n \in \mathbb{Z}$, we have $\varphi(m+n) = h^{m+n}$ $= h^mh^n = \varphi(m)\varphi(n)$, so that $\varphi$ is a homomorphism.

Uniqueness: Suppose we have another homomorphism $\psi$ such that $\psi(1) = h$. Then $\psi(n) = \psi(n \cdot 1)$ $= \psi(1)^n = \varphi(1)^n$ $= \varphi(n)$, so that $\psi = \varphi$ and so $\varphi$ is unique. (Keep in mind that we write $Z$ additively and $H$ multiplicatively.)

### If a group element has finite order n, there is a unique group homomorphism from ZZ/(n) such that the element is the image of 1

We write $Z_n = \langle x \rangle$. Show that if $H$ is any group and $h \in H$ such that $h^n = 1$, then there is a unique homomorphism $\varphi : Z_n \rightarrow H$ with $x \mapsto h$.

Existence: Define $\varphi$ by $\varphi(x^k) = h^k$.

Suppose $x^a = x^b$; then $a = b$ mod n, so that $a = qn + b$ for some $q$. Now $\varphi(x^a) = h^a = h^{qn+b} = h^b = \varphi(x^b)$, so that $\varphi$ is well defined.

Clearly now $\varphi(x^ax^b) = \varphi(x^{a+b})$ $= h^{a+b} = h^ah^b$ $= \varphi(x^a)\varphi(x^b)$, so $\varphi$ is a homomorphism.

Uniqueness: Suppose we have another homomorphism $\psi : Z_n \rightarrow H$ with $\psi(x) = h$. Then for all $x^a \in Z_n$, $\varphi(x^a) = \varphi(x)^a = \psi(x)^a = \psi(x^a)$, so that $\varphi = \psi$. Thus $\varphi$ is unique.

### Find a group presentation for Cyc(n)

Find a presentation for $Z_n$ with one generator.

We have $Z_n = \langle x \ |\ x^n = 1 \rangle$.

### The order of a product of commuting group elements divides the least common multiple of the orders of the elements

Let $G$ be a group with $x,y \in G$. Assume $|x| = n$ and $|y| = m$. Suppose that $x$ and $y$ commute; i.e., that $xy = yx$. Prove that $|xy|$ divides the least common multiple of $m$ and $n$. Need this be true if $x$ and $y$ do not commute? Give an example of commuting elements $x$ and $y$ such that the order of $xy$ is not equal to the least common multiple of $|x|$ and $|y|$.

Supposing that $xy = yx$, we saw in a previous theorem that $(xy)^k = x^ky^k$ for all $k$. In particular, $(xy)^{\mathsf{lcm}(|x|,|y|)} = (x^{|x|})^{|y|/\mathsf{gcd}(|x|,|y|)} (y^{|y|})^{|x|/\mathsf{gcd}(|x|,|y|)} = 1$. Thus by a previous exercise, $|xy|$ divides $\mathsf{lcm}(|x|,|y|)$.

Consider $S_3$. Note that $|(1\ 2)| = |(1\ 3)| = 2$, so that $\mathsf{lcm}(|(1\ 2)|, |(1\ 3)|) = 2$. However $(1\ 2)(1\ 3) = (1\ 3\ 2)$ has order 3, and 3 does not divide 2.

For a trivial example, consider $x \neq 1$ and let $y = x^{-1}$. Less trivially, consider $(x,y),(1,y) \in Z_2 \times Z_4$, where $Z_2 = \langle x \rangle$ and $Z_4 = \langle y \rangle$. Note that $|(x,y)(1,y)| = |(x,y^2)| = 2$, while $|(x,y)| = |(1,y)| = 4$. Thus $|(x,y)(1,y)| \neq \mathsf{lcm}(|(x,y)|,|(1,y)|)$.

### The direct product of two copies of the rationals is not a cyclic group

Prove that $\mathbb{Q} \times \mathbb{Q}$ is not cyclic.

Suppose $\mathbb{Q} \times \mathbb{Q}$ is cyclic. By Theorem 7 in the text, then, every subgroup of $\mathbb{Q} \times \mathbb{Q}$ is also cyclic. However, $\mathbb{Q} \times \mathbb{Q}$ has a subgroup isomorphic to $\mathbb{Z} \times \mathbb{Z}$, which we know to be not cyclic; this is a contradiction.