# Matching coefficients of polynomial congruences

I was reading about the AKS Primality test when the following proof threw me off a bit. The following proof is given directly from the original paper Primes in P by Agrawal, Kayal and Saxena.

Lemma 2.1. Let $a\in \mathbb{Z}$, $n\in \mathbb{N}$, $n\geq2$, and $\gcd(a, n) = 1$. Then $n$ is prime if and only if

$(X + a)^n \equiv X^n + a\ (mod\ n)$

Proof: For $0 < i < n$, the coefficient of $x^i$ in $(X + a)^n − (X^n + a)$ is $\binom{n}{i}a^{n-i}$.

Suppose n is prime. Then $\binom{n}{i}\equiv0\ (mod\ n)$ and hence all coefficients are zero.

Suppose n is composite. Consider a prime $q$ that is a factor of $n$ and let $q^{k}$ be the highest power of $q$ to divide $n$. Then $q^k$ does not divide $\binom{n}{q}$ and is coprime to $a^{n-q}$ and hence the coefficient of $X^q$ is not zero $(mod\ n)$. Thus $(X + a)^n − (X^n + a)$ is not identically zero over $\mathbb{Z}_n$. $\square$

My problem is with the last portion of the proof where they say that $(X + a)^n − (X^n + a)$ is not identically zero over $\mathbb{Z}_n$. How can we be sure that there is no weird relationships (unlikely as it may) between the surviving coefficients that allows the polynomial to be zero even though there are terms surviving (for example, $x^p - x$ over a prime modulus). All other proofs I've found of this lemma appeal to some type of coefficient comparison, i.e. the coefficient is zero on the right hand side but non-zero on the left. Contradiction.

It is my understanding that direct comparison of polynomial coefficients cannot be done with congruences, so can someone please explain this to me? Perhaps a more general question would be: When is it permissible to equate coefficients of two polynomial congruences?

• They might mean that it's non-zero as an element of $\mathbf Z_n[X]$ -- by which I mean the ring of formal linear combinations of the $X^i$ with coefficients in $\mathbf Z_n$ with the usual multiplication -- and not as a function $\mathbf Z_n \to \mathbf Z_n$. Aug 16 '11 at 14:17

The AKS argument quoted in the question shows that if $n$ is composite, and $\gcd(a,n)=1$, then the polynomial $P(X)=(X+a)^n -(X^n+a)$ is not the zero polynomial over $\mathbb{Z}_n$. This means that at least one coefficient of $P(X)$ is not congruent to $0$ modulo $n$.

But in the statement of the result, the phrase "is not identically zero over $\mathbb{Z}_n$" is used. This prompted you to ask whether there are composite $n$ such that $P(X)$, viewed as a polynomial function from $\mathbb{Z}_n$ to $\mathbb{Z}_n$, is the identically zero function.

The answer, surprisingly, is yes, there are infinitely many such $n$. Let $n$ be a Carmichael number.

A Carmichael number is usually defined as a composite number $n$ such that $x^{n-1} \equiv 1\pmod{n}$ for every $x$ relatively prime to $n$. However, one can prove that if $n$ is a Carmichael number, then $x^n \equiv x\pmod{n}$ for every $x$. The proof uses the Korselt Criterion described in the Wikipedia article.

The smallest Carmichael number is $561=3\cdot 11\cdot 17$. The key property that makes everything work is that $3-1$, $11-1$, and $17-1$ all divide $560$. The rest follows from Fermat's Theorem.

If $n$ is a Carmichael number, then $(x+a)^n \equiv x+a \pmod{n}$ for every $x\in \mathbb{N}$. Also, $x^n+a \equiv x+a \pmod{n}$. It follows that $P(X)$, viewed as a polynomial function, is identically zero.

Note: There are infinitely many Carmichael numbers. In fact, they are moderately "common," though the proof that there are infinitely many is less than $20$ years old. This result, by Alford, Granville, and Pomerance, settled a longstanding conjecture.

• Thank you, that was very precise. But for further clarification, does that mean the proof provided for the theorem above is then invalid?
– EuYu
Aug 17 '11 at 13:44
• The proof is a valid proof that if $n$ is composite, not all the coefficients of the polynomial on the left are congruent to the corresponding coefficient of the polynomial on the right. So the coefficients of the difference polynomial are not all congruent to $0$. My example shows that it is possible for the polynomial function to be identically $0$. That's the question you asked. Here is a simple example of a similar phenomenon. Let $p$ be prime. The polynomial $X^p -X$ is not, as a polynomial, the zero polynomial, two of its coefficients are $1$, which is not congruent to $0$. Aug 17 '11 at 14:55
• (continued) However, for all $a\in \mathbb{Z}_p$, $a^p-a$ is congruent to $0$ modulo $p$. In any infinite field, if the coefficients of the polynomial $P(X)$ are not all $0$ in the field, there is an $a$ in the field such that $P(a)\ne 0$. Finite fields don't have his property. So in general one has to distinguish between polynomial and polynomial function. Aug 17 '11 at 14:59
• I'm starting to get what you are saying. I apologize for the confusion since I've never been exposed to these concepts before. I think I am misunderstanding the meaning of the theorem. The theorem is stating that the two polynomial functions must be "equal" (I think formal congruence is the term from PlanetMath) while I interpreted it as the values of the two polynomials must be congruent. Thanks again for your help by the way.
– EuYu
Aug 17 '11 at 15:07
• As I point out in the answer, "not identically zero over $\mathbb{Z}_n$" is deeply ambiguous. Probably the interpretation "as a function," which you made, is the more natural one. But that's not what they prove, what they prove is that the polynomials are not formally congruent. What my post shows is that it is possible, first case $n=561$, for the values to be always congruent. Aug 17 '11 at 15:59