Agrawal's conjecture

In number theory, Agrawal's conjecture, due to Manindra Agrawal in 2002, forms the basis for the cyclotomic AKS test. Agrawal's conjecture states formally:

Let $n$ and $r$ be two coprime positive integers. If

$(X-1)^{n}\equiv X^{n}-1{\pmod {n,X^{r}-1}}\,$

then either $n$ is prime or $n^{2}\equiv 1{\pmod {r}}$

Ramifications

If Agrawal's conjecture were true, it would decrease the runtime complexity of the AKS primality test from ${\tilde {O}}(\log ^{6}n)$ to ${\tilde {O}}(\log ^{3}n)$.

Truth or falsehood

Agrawal's conjecture has been computationally verified for $r<100$ and $n<10^{10}$; however, a heuristic argument by Carl Pomerance and Hendrik W. Lenstra suggests there are infinitely many counterexamples. In particular, the heuristic shows that such counterexamples have asymptotic density greater than ${\tfrac {1}{n^{\varepsilon }}}$ for any $\varepsilon >0$.

Assuming Agrawal's conjecture is false by the above argument, a modified version (the Agrawal–Popovych conjecture) may still be true:

Let $n$ and $r$ be two coprime positive integers. If

$(X-1)^{n}\equiv X^{n}-1{\pmod {n,X^{r}-1}}$

and

$(X+2)^{n}\equiv X^{n}+2{\pmod {n,X^{r}-1}}$

then either $n$ is prime or $n^{2}\equiv 1{\pmod {r}}$.