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?