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?