5

Let $G$ be a finite cyclic group of order $n$. If $d$ is a positive divisor of $n$, prove that equation $x^d = e$ has exactly $d$ distinct solutions in $G$

This is practice question assigned to me and I have no clue how to approach this.

vonbrand
  • 27,812
Kj Tada
  • 1,057

3 Answers3

5

Hint:

Let $g$ be an element of order $n$ in $G$, and let $m=n/d$. Then, the roots are $\{g^m, g^{2m},\dots,g^{dm}\}$.

Try to prove that these elements are roots and the other elements are not.

NECing
  • 4,095
5

Clues:

1) let $g$ be a generator of $G$. Can you show that $g^{n/d}$ solves $x^d=e$

2) can you now think of more elements in $g$ that will solve this equation?

3) once you exhausted the trick above to find as many solutions to $x^d=e$ as you can you should have $d$ solutions. These all have a particularly nice form. Now show that any element not of that form is not a solution.

Ittay Weiss
  • 79,840
  • 7
  • 141
  • 236
  • @Kj Tada: In fact for the first clue note that if $|a|=n<\infty,~~a\in G$ and $(m,n)=d$ then $$|a^m|=\frac{n}{d}$$. Nice points (+1) – Mikasa Mar 18 '13 at 02:54
  • for 1) I believe $g^{n/d}$ solves $x^d$ because ${g^{(n/d)}}^d$ = $g^n$ which equals $e$ if $g$ has order n. 2) I think for the second part only if I take positive divisors of $d$ call them $y$ will I be able to solve $g^{n/y}$ for $x^d=e$

    Am I heading in the right direction ??

     – Kj Tada Mar 18 '13 at 03:08
  • try $g^{(2n)/d}$ – Ittay Weiss Mar 18 '13 at 03:09
  • But then any multiple of $n/d$ would solve $x^d=e$. So do I need to show that there are only $d$ such multiples as @Shu Xiao Li hinted. I guess I have a hard time picturing why couldn't I have a $g^{(d+1)n/d}$ element – Kj Tada Mar 18 '13 at 03:24
  • when you consider $g^{kn/d}$ for various values of $k$ you'll see that from a certain value of $k$ the same group elements are repeated. In fact, precisely $d$ group elements are repeated. – Ittay Weiss Mar 18 '13 at 03:34
  • and by the way, there is no essential difference between my hints and those of Shu's. – Ittay Weiss Mar 18 '13 at 03:34
  • I finally understand this. Thank you all for your help/ – Kj Tada Mar 18 '13 at 03:36
  • you're welcome. – Ittay Weiss Mar 18 '13 at 03:36
3

If you are better at number theory, you can start with this.

Let $g\in G$ be a generator and $f:G\rightarrow Z_n$ be defined by $f(g^i)=i$. You can easily show that $f$ is an isomorphism between $G$ and $Z_n$ which are just integers modulo $n$. Then, your problem reduces to $dx =0 (\text{mod} \ n)$.