nt.number theory - 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))^pequiv 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)^nnot 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)^nnotequiv P(X^n) (mod n)$ for composite n.

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

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

• Next ag.algebraic geometry - Size of a Groebner basis
• Previous co.combinatorics - To what degree do min-cuts specify the cut function of a graph?