1
$\begingroup$

I'm pretty new to modular arithmetic and not having a good knowledge of algebra, so sorry for perhaps a basic question.

Suppose that I have a Galois field modulo $N$ and a primitive root $\omega$. I understand that $\omega$ is also a primitive $\phi(N)$-th root of unity modulo $N$.

Knowing the value of $\omega$, is there a fast way, for an arbitrary $n, compute one of the primitive $n$-th roots of unity modulo $N$?

I searched the Wikipedia and didn't find anything, but I could have been inattentive.

  • 1
    My best guess is that you're confusing, for example, the Galois field ${\mathbb F}_9$ with 9 elements with the ring ${\mathbb Z}/9{\mathbb Z}$. Both of their multiplicative groups of units, ${\mathbb F}_9^\times$ and $({\mathbb Z}/9{\mathbb Z})^\times$, are cyclic; but $\#{\mathbb F}_9^\times = 9-1 = 8 \ne \phi(9)$ and $\#({\mathbb Z}/9{\mathbb Z})^\times = \phi(9) = 6$.2012-01-31

1 Answers 1

4

If you have a generator $\omega$ of any cyclic group (regardless of whether it comes from a field or not), it is easy to construct elements of any order you want. Say the cyclic group (and hence $\omega$ as well) has order $k$. Then for any $d$ dividing $k$ (which are all the possible orders), the element $\omega^{k/d}$ will have order $d$.

Assuming your question is asking about the multiplicative group $({\mathbb Z}/N{\mathbb Z})^\times$, then an element of order $d$ is the same thing as a primitive $d$th root of unity modulo $N$.

  • 0
    $({\mathbb Z}/N{\mathbb Z})^\times$ is only cyclic if $N$ is the power of an odd prime, or twice the power of an odd prime. Also, if N is the power of a prime, the multiplicative group of $\mathbb{F}_N$ and of $\mathbb{Z}_N$ are two different things (unless N is prime).2012-01-30