# AKS algorithm pseudoprimes

The AKS algorithm is based on the following fully deterministic primality check:

Let input $n>1$ and $a \in \mathbb{Z}$ such that $(a,n)=1$. Then $n$ is prime if and only if $$\tag{1}(x+a)^n \equiv x^n + a \ (\text{mod}\ n).$$ This check involves computing $n$ binomial coefficients, which is too slow. AKS sped up their algorithm by reducing equation (1) modulo $x^r-1$ for an appropriate small $r$. However, in their paper, the authors claim "The problem now is that some composites $n$ may also satisfy the equation for a few values of $a$ and $r$ (and indeed they do)."

I am curious about the likelihood of encountering such a composite $n$, an "AKS-pseudoprime" if you will. The time-consuming part of the AKS algorithm is evaluating $$\tag{2}(x+a)^n \equiv x^n + a \ (\text{mod}\ x^r-1,n)\label{}$$ for values of $a$ between $1$ and $\lfloor\sqrt{\phi(r)}\log{n}\rfloor$. I have checked equation (2) on the first 4 million or so values of $n$, with $a=1$, and the equality fails immediately for all composite $n$ (i.e. it is unnecessary to increment $a$) Does anyone have an example of a composite number $n$ that satisfies equation (2) for any value of $a$?

-
Identical cross-post: mathoverflow.net/questions/120886/aks-algorithm-pseudoprimes –  Greg Martin Feb 5 '13 at 18:41
I posted on both sites in hopes of getting a greater audience for this rather specific question. Is that frowned upon? –  Dominick Reinhold Feb 5 '13 at 18:55