1. ## Independence with mod

How would I go about proving that $\displaystyle \sum_{i=1}^{p-1}a_ix^i \equiv 0 \ (mod \ p) \Rightarrow a_i \equiv 0 \ (mod \ p)$ for all $\displaystyle a_i$.

The way I'm doing it now assumes that there is one coefficient which is not congruent to 0 mod p. This implies that the variable must be congruent to 0 mod p, but since the summation is true for all x, we get our contradiction.

My problem is that I'm assuming that there is only one coefficient which isn't congruent to 0 mod p. In the case of 2 coefficients not congruent to 0, I think I can do it by showing that the two terms have to be additive inverses, and eventually we get back to x being forced to zero (contradiction). What do I do in the case of more than 2 coefficients not being congruent to 0 mod p?

2. Prove that if $\displaystyle a_n \not\equiv 0 (\bmod.p)$ then $\displaystyle p(x)=a_n\cdot x^n +...+a_1\cdot x + a_0$ can have at most $\displaystyle n$ roots module $\displaystyle p$ - try induction-. (*)

Now in your case, suppose $\displaystyle a_i \not\equiv 0 (\bmod.p)$ for some $\displaystyle 0<i<p$ then by (*) it can have at most $\displaystyle k$ roots module p for some $\displaystyle k<p$ -the greatest nonzero coefficient mod. p-, but it has $\displaystyle p$ roots! Contradiction

3. Um ... wouldn't my case have p-1 roots? Since the highest power is p-1. So the contradiction wouldn't quite work ....

4. Originally Posted by Bingk
Um ... wouldn't my case have p-1 roots? Since the highest power is p-1. So the contradiction wouldn't quite work ....
How many remainders are there module p? Each of them is a root of your polynomial - mod. p-

5. Can you use algebra?
It is a theorem that if $\displaystyle F$ is a field, the polynomial ring $\displaystyle F[x]$ is a unique factorization domain. Since $\displaystyle \mathbb{Z}/p\mathbb{Z} = \mathbb{F}_p$ is a field, $\displaystyle \mathbb{F}_p[x]$ is a unique factorization domain, which implies that a polynomial having degree $\displaystyle n$ can have at most $\displaystyle n$ roots in $\displaystyle \mathbb{F}_p$. In particular, a nonzero polynomial of degree $\displaystyle \leq p-1$ can have at most $\displaystyle p-1$ roots. In other words, if it has $\displaystyle p$ roots it must be the zero polynomial.

6. AH!!! Okay ... I think it just clicked together ... sorry, alot of the stuff you guys are saying is kinda advanced for me, hehehe. Um, I didn't study number theory with an algebra approach, so I'm not too familiar with all that notation about fields, rings, and such ... but I did look it up .

I think the two of you are kinda doing the same thing ... and this is what I basically get.

The polynomial I gave has p roots (since it works for all 0<=x<p). But, the polynomial is of order p-1, so it should have at most p-1 roots. Which is the contradiction that PaulRS was talking about, so all the coefficients should be congruent to 0 mod p. As for Bruno, I'm not sure how/why we can say that (aside from PaulRS way ) it must be the zero polynomial. This is probably because I don't know enough about fields and such .

Thanks