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:
\begin{equation} h(X) \not | \ X^{m_1-m_2} - 1 \end{equation}
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.)
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$.