field, cyclic group, Mobius Inversion

**riemannsph12** · December 9th, 2008, 03:27 PM

The parts of this problem form a proof of the fact that if $G$ is a finite subgroup of $F^*$ , where $F$ is a field (even if $F$ is infinite), then $G$ cyclic. Assume $|G|=n$ .
(a) If $d$ divides $n$ , show $x^d-1$ divides $x^n-1$ in $F[x]$ , and explain why $x^d-1$ has $d$ distinct roots in $G$ .
(b) For any $k$ let $\psi(k)$ be the number of elements of $G$ having order $k$ . Explain why $\sum_{c|d}\psi(c)=d=\sum_{c|d}\phi(c)$ , where $\phi$ is the Euler $\phi$ -function.
(c) Use Mobius Inversion to conclude $\psi(n)=\phi(n)$ . Why does this tell us $G$ is cyclic?

**ThePerfectHacker** · December 9th, 2008, 08:44 PM

Originally Posted by riemannsph12

The parts of this problem form a proof of the fact that if $G$ is a finite subgroup of $F^*$ , where $F$ is a field (even if $F$ is infinite), then $G$ cyclic. Assume $|G|=n$ .
(a) If $d$ divides $n$ , show $x^d-1$ divides $x^n-1$ in $F[x]$ , and explain why $x^d-1$ has $d$ distinct roots in $G$ ?

This is not necessarily true. If $\text{char}(F) = p>2$ and $x^p - 1$ divides $x^n - 1$ then $x^p - 1 = (x-1)^p$ has just one root.
---

Since you are looking for a proof that finite subgroups of the multiplicative group are cyclic here is another way that you might like. But first we need to remind ourselves of a fact about finite abelian groups. If $G$ is a finite abelian group (like here) and $m$ is the maximal order of an element then the order of all elements divides $m$ . If $g\in G$ then $g^m = 1$ and so all $g\in G$ are roots of $x^m - 1$ . We see that all elements of $G$ are roots of $x^m -1$ . The polynomial has at least $m$ roots, therefore, $n\leq m \implies n=m$ . It follows that $G$ has an element with maximal order equal to $|G|=n$ i.e. $G$ is cyclic.

**riemannsph12** · December 10th, 2008, 06:18 PM

I like that proof a lot more than this one. Here is what I have so far [let me know if you have any comments]:

a) The first part is trivial [ $y - 1$ divides $y^k - 1$ , there values of $y$ and $k$ will give us our result - I need to show this]. If $|G| = n$ then the roots of $x^n - 1$ are precisely the elements of $G$ , which are distinct. (Note how strong this result is. Specifying the order of $G$ specifies $G$ uniquely.) Since the roots of $x^d - 1$ are a subset of the roots of $x^n - 1$ , they must also consist of $d$ distinct elements of $G$ .

b) $\sum_{c | d} \psi(c)$ is the number of elements having order dividing $d$ , and those are precisely the roots of $x^d - 1$ . On the other hand, $x^d - 1 = \prod_{c | d} \Phi_c(x)$ where $\text{deg } \Phi_c = \phi(c)$ .

c) The first part is trivial [we use Möbius inversion to uniquely extract the value of $\psi$ from the equation. But the equation is the same for $\phi$ ]. Since $\psi(n) > 0$ , $G$ has elements of order exactly $n$ .

**riemannsph12** · December 11th, 2008, 05:22 PM

Also, I think the characteristic $p$ of $F$ does not divide $n$ , this is because: if it did then the derivative of $f(x)=x^n-1$ would be zero, and $\text{gcd}(f, f')= f$ and $f$ would have multiple roots.

**ThePerfectHacker** · December 11th, 2008, 07:58 PM

Originally Posted by riemannsph12

I like that proof a lot more than this one. Here is what I have so far [let me know if you have any comments]:

a) The first part is trivial [ $y - 1$ divides $y^k - 1$ , there values of $y$ and $k$ will give us our result - I need to show this]. If $|G| = n$ then the roots of $x^n - 1$ are precisely the elements of $G$ , which are distinct. (Note how strong this result is. Specifying the order of $G$ specifies $G$ uniquely.) Since the roots of $x^d - 1$ are a subset of the roots of $x^n - 1$ , they must also consist of $d$ distinct elements of $G$ .

b) $\sum_{c | d} \psi(c)$ is the number of elements having order dividing $d$ , and those are precisely the roots of $x^d - 1$ . On the other hand, $x^d - 1 = \prod_{c | d} \Phi_c(x)$ where $\text{deg } \Phi_c = \phi(c)$ .

c) The first part is trivial [we use Möbius inversion to uniquely extract the value of $\psi$ from the equation. But the equation is the same for $\phi$ ]. Since $\psi(n) > 0$ , $G$ has elements of order exactly $n$ .

Originally Posted by riemannsph12

Also, I think the characteristic $p$ of $F$ does not divide $n$ , this is because: if it did then the derivative of $f(x)=x^n-1$ would be zero, and $\text{gcd}(f, f')= f$ and $f$ would have multiple roots.

Here is how you can prove this result in the way you wanted to prove it.

1)Let $|G|=n$ then by Lagrange's theorem $x^n = 1$ and so $x^n - 1 =0$ . This polynomial at most $n$ roots but all elements in $G$ are roots, so $x^n - 1$ has exactly $n$ roots. If $d|n$ then it means $x^d - 1$ divides $x^n-1$ . The polynomial $x^d - 1$ factors linearly into distinct factors because it divides $x^n - 1$ which only has simple roots. Consequently, $x^d - 1$ has exactly $d$ roots.

2)For $d|n$ let $\psi (d)$ be the number of elements that have order $d$ . Any element in $G$ has order dividing $n$ and there are $\psi (d)$ elements that have the order. Thus, by counting we see that $n = \sum_{d|n} \psi (d)$ . Therefore, $\sum_{d|n}\psi (d) = \sum_{d|n}\phi(d)$ by property of $\phi$ .

3)Let $G_d$ be the subgroup of $G$ consisting of elements of order dividing $d$ i.e. $G_d = \{ x\in G : x^d = 1 \}$ . By part 1 we see that $G_d$ is a subgroup with $|G_d| = d$ . Now let $a\in G$ have order $d$ , then $a$ generates the subgroup $G_d$ . The number of generators of $G_d$ is therefore $\phi (|G_d|) = \phi (d)$ . Thus, we see that if $d|n$ satisfies $\psi (d) > 0$ (i.e. there is an element of order $d$ ) then $\psi (d) = \phi (d)$ , otherwise, $\psi (d) = 0$ . Therefore, for $d|n$ we have that $\psi (d) \leq \phi(d)$ . But by 2 we see that $\sum_{d|n}\psi (d) = \sum_{d|n} \phi(d)\implies \psi (d) = \phi(d) \text{ for }d|n$ .
Therefore, $\psi (n) = \phi (n) > 0$ .

Math Help Forum: field, cyclic group, Mobius Inversion

LinkBack

Thread Tools

Display

field, cyclic group, Mobius Inversion

Similar Math Help Forum Discussions

How to apply Mobius inversion formula

Mobius Inversion problem

Mobius Inversion Formula

Mobius Inversion Formula

Mobius Inversion