2
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ "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? $\endgroup$
    – Victor Protsak
    Commented Aug 20, 2010 at 17:03
  • $\begingroup$ 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. $\endgroup$
    – Lasse Rempe
    Commented Aug 21, 2010 at 15:36

2 Answers 2

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ It is in Galois's paper on finite fields. $\endgroup$
    – Felipe Voloch
    Commented Aug 20, 2010 at 19:09
  • $\begingroup$ That's an excellent reference - many thanks! $\endgroup$
    – Lasse Rempe
    Commented Aug 21, 2010 at 15:36
5
$\begingroup$

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 .

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks - yes, I know how to prove it. Thank you for the reference to the Frobenius endomorphism, which is a term I wasn't familiar with and which should make a literature search easier. Do you know when this was first observed, either in general for commutative rings of characteristic p or for polynomial rings? $\endgroup$
    – Lasse Rempe
    Commented Jul 28, 2010 at 22:20
  • $\begingroup$ I don't have any precise historical data on this but since one of the proofs of Fermat's theorem (for integers) is based on that observation, one that Fermat himself could have made, I suspect it's very old indeed. The term "Frobenius endomorphism" is too recent to reflect this (but the term is used in more advanced contexts). $\endgroup$
    – lhf
    Commented Jul 28, 2010 at 22:35
  • $\begingroup$ Yes, that's what I suspected as well - the result looks so classical that one would think it should have been noted somewhere for polynomials before even the terminology existed to state it for rings. Do you know where and why the term "Frobenius endomorphism" was first used? $\endgroup$
    – Lasse Rempe
    Commented Jul 29, 2010 at 9:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .