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, 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) 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?
Best Answer
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