In their famous 'Primes is in P' paper Agrawal, Kayal and Saxena stated the following conjecture:



> 
> If for coprime integers $n$ and $r$ the equality $(X-1)^n = X^n - 1$ holds in $\mathbb{Z}\_n[X]/(X^r-1)$ then either $n$ is prime or $n^2 = 1 \pmod{r}$.
> 
> 
> 


If true this would give a beautiful characterization of primes that could be easily transformed into a fast ($O(\log^{3+\epsilon}{n})$) and deterministic primality test.


Shortly after publishing 'Primes is in P' Hendrik Lenstra noticed that the conjecture may not be valid for $r=5$ and $n$ of the very special form (see [Lenstra's and Pomerance's note](http://www.aimath.org/WWN/primesinp/primesinp.pdf), p.30). It was unknown whether any such $n$ existed but Carl Pomerance gave a heuristic argument convincing that there should be infinitely many $n$'s sharing these, apparently rare, properties. I'm not aware of any strict proof for this.


It may also happen that the conjecture in a modified form (if we restrict $r$ to be greater than $\log{n}$) can be still true.


Martin Mačaj (see [Some remarks and questions about the AKS
algorithm and related conjecture](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.144.7953&rep=rep1&type=pdf)) gave another version of this conjecture together with a proof that relied on yet another unsolved problem.


Does anyone know if there were any advances in this area in the recent years?



What is the current status of Agrawal's conjecture?
I had some students look at this problem during an REU. A group proved that the conjecture is true if $r > n/2$, that's not too hard and can certainly be improved. Another group tried to find a counterexample using the computer for $r=5$, without success. I agree with Lenstra and Pomerance that the conjecture should be false in general.


Link to REU page: <http://www.ma.utexas.edu/users/voloch/reu.html>


