most recent 30 from http://mathoverflow.net 2013-05-25T06:49:26Z http://mathoverflow.net/feeds/question/33675 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/33675/fermat-for-polynomials-as-used-in-the-aks-agrawal-kayal-saxena-algorithm Lasse Rempe-Gillen 2010-07-28T16:31:59Z 2010-08-20T16:29:07Z

<p>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.</p> <hr> <h2>Theorem</h2> <p>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)$.</p> <hr> <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?</p> <p>Furthermore, there is a converse to the lemma in the AKS paper:</p> <hr> <h2>Lemma</h2> <p>If n is a composite number, then $(X+a)^n\not \equiv X^n+a\ (\mod n)$ whenever a is coprime to n.</p> <hr> <p>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. </p> <p>On the other hand, clearly some conditions are necessary; for example $(3X+4)^6\equiv 3X^6+4\ (\mod 6)$. </p> <p>Is there a best possible statement? And, again, is there a reference?</p>

http://mathoverflow.net/questions/33675/fermat-for-polynomials-as-used-in-the-aks-agrawal-kayal-saxena-algorithm/33685#33685 lhf 2010-07-28T17:03:15Z 2010-07-28T17:03:15Z

<p>The theorem is elementary: it is a consequence of the fact that $p \choose k$ is a multiple of $p$ for $0 &lt; k &lt; p$. See <a href="http://en.wikipedia.org/wiki/Frobenius_endomorphism" rel="nofollow">http://en.wikipedia.org/wiki/Frobenius_endomorphism</a> .</p>

http://mathoverflow.net/questions/33675/fermat-for-polynomials-as-used-in-the-aks-agrawal-kayal-saxena-algorithm/36202#36202 Franz Lemmermeyer 2010-08-20T16:28:38Z 2010-08-20T16:28:38Z

<p>Your first theorem occurs as an easily proved statement on p. 287 of Sch&ouml;nemann's article <em>Grundz&uuml;ge einer allgemeinen Theorie der h&ouml;hern Congruenzen, deren Modul eine reelle Primzahl ist</em>, J. Reine Angew. Math. 31 (1846), 269--325. Sch&ouml;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 <em>The shaping of arithmetic after C.F. Gauss's Disquisitiones Arithmeticae</em>) 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. </p> <p>This lemma also has a habit of showing up in various proofs of the irreducibility of the cyclotomic equation.</p>