1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Comparing coefficients of polynomial congruences.

  1. Aug 15, 2011 #1
    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.
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted