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?
 A: 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.
