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?



Fermat for polynomials, as used in the AKS (Agrawal-Kayal-Saxena) algorithm
Your first theorem occurs as an easily proved statement on p. 287 of Schönemann's article *Grundzüge einer allgemeinen Theorie der höhern Congruenzen, deren Modul eine reelle Primzahl ist*, J. Reine Angew. Math. 31 (1846), 269--325. Schönemann was one of the first mathematicians (not counting Gauss, who eliminated the corresponding Section 8 from his Disquisitiones at the last minute; see G. Frei's article "The Unpublished Section Eight: On the Way to Function Fields over a Finite Field" in *The shaping of arithmetic after C.F. Gauss's Disquisitiones Arithmeticae*) who studied the arithmetic of polynomials modulo primes. It might very well occur somewhere in Galois's papers, but it surely was considered to be essentially trivial by all of them. 


This lemma also has a habit of showing up in various proofs of the irreducibility of the cyclotomic equation.


