Comparing coefficients of polynomial congruences.

[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.

 

[fresh_42]

Your question is: When are we allowed to conclude $\mu a^m \equiv \nu a^m \,\operatorname{mod} n \Longrightarrow \mu \equiv \nu \,\operatorname{mod}n\,?$

The equation lives in the ring $\mathbb{Z}_n$, so the question is: When is $a^m \in \mathbb{Z}_n$ a unit, in which case we can cancel it and are left with $\mu \equiv \nu\,\operatorname{mod}n\,.$ And $a^m$ is a unit, if it is coprime to $n$. Since $(a,n)=1$ are coprime, so are $(a^{(p^k)},n)=1\,.$ Here we use, that $\binom{n}{p^k}$ is the coefficient at $a^{(p^k)}\,.$