- #1
Yuqing
- 218
- 0
Today I read about the AKS - Primality test in which the simple theorem
For gcd(a, n) = 1, we have
[tex](X - a)^n\equiv X^n - a\ (mod\ n)[/tex]if and only if n is prime.
was proven. The if direction is quite trivial from the fact that [itex]\binom{p}{k}\equiv 0\ (mod\ p)[/itex] for [itex]1\leq k < p[/itex]. The other direction comes as follows (sketch):
Suppose [itex](X - a)^n\equiv X^n - a\ (mod\ n)[/itex] and that n was composite. Let p be a prime divisor of n and [itex]p^k[/itex] the largest power of p which divides n. Then [itex]p^k[/itex] does not divide [itex]\binom{n}{p^k}[/itex] so we have on the left a coefficient of [itex]x^{p^k}[/itex] 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.
For gcd(a, n) = 1, we have
[tex](X - a)^n\equiv X^n - a\ (mod\ n)[/tex]if and only if n is prime.
was proven. The if direction is quite trivial from the fact that [itex]\binom{p}{k}\equiv 0\ (mod\ p)[/itex] for [itex]1\leq k < p[/itex]. The other direction comes as follows (sketch):
Suppose [itex](X - a)^n\equiv X^n - a\ (mod\ n)[/itex] and that n was composite. Let p be a prime divisor of n and [itex]p^k[/itex] the largest power of p which divides n. Then [itex]p^k[/itex] does not divide [itex]\binom{n}{p^k}[/itex] so we have on the left a coefficient of [itex]x^{p^k}[/itex] 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.