Comparing coefficients of polynomial congruences.

  • Thread starter Yuqing
  • Start date
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.
 

fresh_42

Mentor
Insights Author
2018 Award
10,011
6,751
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)}\,.##
 

Want to reply to this thread?

"Comparing coefficients of polynomial congruences." You must log in or register to reply here.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top