# PRIMES in P paper - Lemma 4.7 - why are the polynomials $X^m$ distinct in $F$?

I'm working through the original AKS paper, available here: https://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf.

There's a single transition which I don't know how to justify, I will describe the setting and hopefully capture everything that's relevant. In doubt, feel free to see Lemma 4.7 in the paper.

We have the following setting:

$$p$$ is prime, $$p > r$$.

$$h(X)$$ is an irreducible polynomial over $$F_p$$ that divides $$X^r-1$$ and has degree greater than $$1$$.

$$F := F_p[X]/(h(X))$$.

There's $$(n, r) = (p, r) = 1$$.

$$m_1$$ and $$m_2$$ are distinct elements of $$G$$, the multiplicative group generated by $$n$$ and $$p$$ modulo $$r$$ (so $$G$$ is a subgroup of $$\mathbb{Z}_r^*$$).

Now, from that information they somehow infer that $$X^{m_1}$$ and $$X^{m_2}$$ are distinct in $$F$$. I don't know how.

If you want to refer to the paper, the sentence this is paraphrasing is 'Hence there will be $$|G| = t$$ distinct roots of $$Q(Y)$$ in $$F$$.' The preceding sentence is 'Since $$(m, r) = 1$$ ($$G$$ is a subgroup of $$\mathbb{Z}_r^*$$), each such $$X^m$$ is a primitive $$r^\text{th}$$ root of unity.'

With a little work I think I'll be able to show that $$X^m$$ is a primitive $$r^\text{th}$$ root of unity in $$F$$, however I don't see how that connects to the statement that the $$X^m$$ are distinct in $$F$$ for distinct $$m \in G$$. Perhaps I'm missing some elementary background that makes this transition obvious.

Below is some work that I've done trying to solve this, but it might be wrong because I have never learned any of this theory properly :(

Below I'm often quietly using the fact that $$h(X)$$ can't divide any $$X^d$$ for $$d \in \mathbb{Z}$$.

If I haven't made a mistake along the way, I think this problem can be reduced to showing that:

$$$$h(X) \not | \ X^{m_1-m_2} - 1$$$$

If I understand primitive roots of unity correctly, we have that $$m_1 = m_2k$$ for some integer $$k$$ (because $$X^{m_1}$$ generates, among other roots also the root $$X^{m_2}$$), and so $$X^{m_1-m_2} - 1 = X^{(k-1)m_2} - 1$$.

We also already know $$h(X) | X^{r} - 1$$ and I think if we assume (looking for a contradiction from here) that $$h(X) | \ X^{m_1-m_2} - 1$$ then we can get $$h(X) | X^{\text{gcd}(r, (k-1)m_2)} - 1 = X^{\text{gcd}(r, k-1)} - 1$$ from that. That would be great if we can show that $$(r, k-1) = 1$$ cause we'd get a contradiction because $$\deg h > 1$$.

However I don't know how to show that $$(r, k-1) = 1$$, if that's even true... I'd think that $$(k, r) = 1$$ because $$(m_1, r) = 1$$ and $$m_1 = m_2k$$. That seems to suggest $$(k-1, r) = 1$$ is quite unlikely to hold? (That's not a rigorous argument of course.)

• I'm not clear how integer $n$ enters the picture. The references to $n$ appear (twice) in the problem setup, but it is not explicitly mentioned thereafter (although implicitly $m_1,m_2$ are said to be "distinct elements of $G$". a subgroup of $\mathbb Z_p^*$ ??). – hardmath Dec 24 '18 at 22:02

The proof of Lemma $$4.7$$ begins with noting that $$X$$ is a primitive $$r$$-th root of unity in $$F$$.
This means that if $$X^m=1$$ in $$F$$, then $$r\mid m$$. Thus if $$X^{m_1}=X^{m_2}$$ in $$F$$, then $$m_1\equiv m_2\pmod r$$. For $$m_1,m_2\in G$$ this translates into $$m_1=m_2$$.
• Thanks a lot! Primitive roots are a newish concept to me. Is saying that $X$ is a primitve $r$-th root of unity in $F$ the same as saying that the multiplicative order of $X$ in $F$ is $r$? – I want to make games Dec 24 '18 at 21:29