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.