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

  • $\begingroup$ 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^*$ ??). $\endgroup$ – 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$.

  • $\begingroup$ 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$? $\endgroup$ – I want to make games Dec 24 '18 at 21:29
  • $\begingroup$ Yes, exactly. (Nothing new here, actually.) $\endgroup$ – metamorphy Dec 24 '18 at 21:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.