# Comparing coefficients of polynomial congruences.

1. Aug 15, 2011

### Yuqing

Today I read about the AKS - Primality test in which the simple theorem

For gcd(a, n) = 1, we have
$$(X - a)^n\equiv X^n - a\ (mod\ n)$$if and only if n is prime.

was proven. The if direction is quite trivial from the fact that $\binom{p}{k}\equiv 0\ (mod\ p)$ for $1\leq k < p$. The other direction comes as follows (sketch):

Suppose $(X - a)^n\equiv X^n - a\ (mod\ n)$ and that n was composite. Let p be a prime divisor of n and $p^k$ the largest power of p which divides n. Then $p^k$ does not divide $\binom{n}{p^k}$ so we have on the left a coefficient of $x^{p^k}$ which is non-zero and on the right a coefficient which is 0. By comparison of coefficients, we reach a contradiction.

The problem I have with the proof is the last step, the comparison of coefficients. I thought that this cannot be done in general with congruences. This brings me to a more general question which is: When can comparison of coefficients be done for congruent polynomials.