Sorry if the title is not descriptive, I couldn't find a way to properly describe the problem.
In the proof of the AKS algorithm (link), the following is stated in Lemma 4.7:
"First note that since $h(X)$ is a factor of the cyclotomic polynomial $Q_r(X)$, $X$ is a primitive $r^{\text{th}}$ of unity in $F$."
I do not understand why $X$ is a primitive $r^{\text{th}}$ of unity in $F$. I can see that it is a root of unity in $F$, as $H(X)$ is a factor of $Q_r(X)$, which is in turn a factor of $X^r-1$. Hence $X^r \equiv 1 \pmod{p,H(X)}$. However, it is not clear to me why $X^k\not\equiv 1\pmod{p,H(X)}$ for all $0< k < r$.
Similar to the original AKS paper, Granville (link) states on the bottom of page 17 that
"(...), $\mathbb{F}$ contains $x$, an element of order $r$"
and on page 19, in the proof of Lemma 4.3:
"It can be shown that $x$ has order $r$ in $\mathbb{F}$ (...)"
Some background on notation:
- $p$ is a prime. $r$ is an integer less than $p$.
- $F$ and $\mathbb{F}$ refer to the finite field $(\mathbb{Z}/p\mathbb{Z})[X]/(h(X))$, where $h(X)\in (\mathbb{Z}/p\mathbb{Z})[X]$ is an irreducible factor of the cyclotomic polynomial $Q_r(X)$.
- Granville uses lower capital '$x$' to denote the indeterminate in the polynomial ring.
Thanks in advance for any help.