# Finding primitive $n$-th root of unity modulo $N$ having a primitive root

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<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.

• What do you mean by "Galois field modulo $N$"? Do you mean a finite field of cardinality $N$? If so, then a primitive root will have order $N-1$, not $\phi(N)$. Perhaps you mean instead the multiplicative group of units in the ring ${\mathbb Z}/N{\mathbb Z}$. – Greg Martin Jan 30 '12 at 11:38
• $\phi(N)=N-1$ in a finite field, so it should be the same. Yes, I meant finite fields. – wh1t3cat1k Jan 30 '12 at 12:11
• You do realize (as in Greg's answer) that $n$ has to be a factor of $N-1$, don't you? Otherwise you need to go to an extension field $GF(N^m)$ and cannot do it all in $GF(N)$. In that case you have to first find the smallest integer $m$ such that $n|N^m-1$. If $n$ has a common factor with $N$, then it cannot be done no matter what. – Jyrki Lahtonen Jan 30 '12 at 12:56
• @wh1t3cat1k $\phi(N) = N-1$ if $N$ is prime, but in general not if $N$ is a power of a prime. – Emilio Ferrucci Jan 30 '12 at 13:34
• 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$. – Greg Martin Jan 31 '12 at 2:02

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$.
• $({\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). – Emilio Ferrucci Jan 30 '12 at 13:25