The AKS algorithm is based on the following fully deterministic primality check:
Let input $n>1$ and $a \in \mathbb{N}$ 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)$$ for values of $a$ between $1$ and $\lfloor\sqrt{\phi(r)}\log{n}\rfloor$. I have checked equation (2) on the first 10 million 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$?