Is there an element of order $n$ in all roots of $x^n - 1$ modulo $q$ where $q$ is a prime number and $n \mid q-1$

Question

In the field of $\mathbb{Z}_q$ where $q$ is a prime, if $n \mid q-1$, then

$$ x^n - 1 = (x - \omega_1) (x - \omega_2) \cdots (x - \omega_n) $$

where $\omega_i$ is a root of $x^n-1$ for all $1 \leq i \leq n$. I want to prove that at least one of all the $\omega_i$ has order $n$; that is, there exists some $\omega_i$ such that $$ \omega_i^n = 1 \quad \text{and} \quad \omega_i^k \neq 1 \;\; \forall 1\leq k < n $$

I think it's true; moreover, I guess there are $\phi(n)$ such elements of order $n$ since there are when considering the $n$ roots of $x^n-1$ in complex field $\mathbb{C}$. Thank you very much.

Answer 1

$ \mathbb{Z}^*= \mathbb{Z_q} -\{0\}$ is always a cyclic group under multiplication. It has $q-1$ elements. We know that, if G is a finite cyclic group of $m$ elements and if $n|m$, then there exists a unique cyclic subgroup of order $n$. This subgroup, being cyclic, must have $\varphi(n)$ generators. And you have pointed it out right, that in the given case, there are $\varphi(n)$ elements with order $n$.

Answer 2

First of all, if you assume that $n \mid q-1$, then $q \nmid n$. Notice that, if $q \mid n$ (thus $n=kq$ with $k \in \mathbb{Z}$), then $(x^n-1) = (x^k-1)^q$, therefore a root of unity can't have order $n$ (unless $n=q$).

You can define the cyclotomic polynomials $\Phi_n(x) := \prod_{k \in \mathbb{Z}_n^*} (x-\zeta^k) \in \mathbb{Z}_q[x]$ where $\zeta \in \overline{\mathbb{Z}_q}$ (algebraic closure) is a (not necessarily primitive, we will prove it is primitive) $n$-th root of unity. You can then factor by the divisors of $n$ the polynomial $x^n-1 \in \mathbb{Z}_q[x]$ as: \begin{align*} x^n-1 = \prod_{d|n}\Phi_d(x). \end{align*} In other words, I have rephrased your question by looking specifically at a zero of $\Phi_n$, which is a root of unity. Now you wish to prove that $\zeta$ has order $n$. Assume that $\zeta$ doesn't have order $n$, let's say the order of $\zeta$ is $m$. Because we know that $\zeta^n=1$, we know that $m|n$. Then, let's look at: \begin{align*} \prod_{l|m}\Phi_l(x) = x^m-1. \end{align*} Now, it follows that: \begin{align*} \prod_{d|n}\Phi_d(x) = (x^m-1) \cdot \prod_{d|n, d \nmid m }\Phi_d(x) = x^n-1. \end{align*} We know that $n \nmid m$. The contradiction now follows if you assume that $q \nmid n$, which I will leave for you to find out (use separability of $x^n-1 \in \mathbb{Z}_q[x]$).