- #1

- 38

- 0

(a) If [tex]d[/tex] divides [tex]n[/tex], show [tex]x^d-1[/tex] divides [tex]x^n-1[/tex] in [tex]F[x][/tex], and explain why [tex]x^d-1[/tex] has [tex]d[/tex] distinct roots in [tex]G[/tex].

(b) For any [tex]k[/tex] let [tex]\psi(k)[/tex] be the number of elements of [tex]G[/tex] having order [tex]k[/tex]. Explain why [tex]\sum_{c|d}\psi(c)=d=\sum_{c|d}\phi(c)[/tex], where [tex]\phi[/tex] is the Euler [tex]\phi[/tex]-function.

(c) Use Mobius Inversion to conclude [tex]\psi(n)=\phi(n)[/tex]. Why does this tell us [tex]G[/tex] is cyclic?

**Here is what I have so far:**

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

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

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

I am still confused on all of the parts. I am not sure if I am doing this right. Any ideas/comments would be great.