# Fermat for polynomials, as used in the AKS (Agrawal-Kayal-Saxena) algorithm

The basis for the deterministic polynomial-time algorithm for primality of Agrawal, Kayal and Saxena is (the degree one version of) the following generalization of Fermat's theorem.

## Theorem

Suppose that P is a polynomial with integer coefficients, and that p is a prime number. Then $(P(X))^p\equiv P(X^p)\ (\mod p)$.

Surely this result was known previously, but I have not been able to find a reference in the literature on the AKS algorithm (which means that the authors also did not know of a reference). Does anyone here know of one?

Furthermore, there is a converse to the lemma in the AKS paper:

## Lemma

If n is a composite number, then $(X+a)^n\not \equiv X^n+a\ (\mod n)$ whenever a is coprime to n.

Again, it is easy to generalize this statement. For example, if P is a polynomial which has at least two nonzero coefficients and such that all nonzero coefficients are coprime to n, then $P(X)^n\not\equiv P(X^n)\ (\mod n)$ for composite n.

On the other hand, clearly some conditions are necessary; for example $(3X+4)^6\equiv 3X^6+4\ (\mod 6)$.

Is there a best possible statement? And, again, is there a reference?

• "I have not been able to find a reference in the literature on the AKS algorithm (which means that the authors also did not know of a reference)": that is a fallacious argument. There is a certain minimum background assumed in writing mathematical articles. If a result is standard, e.g. if it can be found in most textbooks, it may not be necessary to reference it. If you needed to use the fact that the ring of polynomials has no zero divisors, would you give a reference? If you didn't, would that imply that you didn't know of one? – Victor Protsak Aug 20 '10 at 17:03
• A good point. Indeed, with a fact considered to be classical, one would not necessarily give a reference, and if a proof is given, I would usually preface it with a comment that it is well-known. And indeed, in Agrawal and Biswas's paper, they state "This identity is, in fact, a well known property of finite fields that is used in many places". I am not sure how I missed that. I clearly should have looked more carefully before asking the questions. Many thanks for the comments. – Lasse Rempe Aug 21 '10 at 15:36

The theorem is elementary: it is a consequence of the fact that $p \choose k$ is a multiple of $p$ for $0 < k < p$. See http://en.wikipedia.org/wiki/Frobenius_endomorphism .