$x^p-x \equiv x(x-1)(x-2)\cdots (x-(p-1))\,\pmod{\!p}$
I got a question to show that :
If $p$ is prime number, then $$x^p - x \equiv x(x-1)(x-2)(x-3)\cdots (x -(p-1))\,\,\text{(mod }\,p\text{)}$$
Now I got 2 steps to show that the two polynomials are congruent:
- Show they have same roots.
- Show the leading term's coefficients on both sides are the same.
For step 2, I know it is obvious $x^p$ has coefficient 1 on both sides. For step 1, but I am not sure how to find all the solutions for $x^p -x$ modulo $p$.
Solution 1:
It is not clear if we are asked to prove equality as polynomial functions (i.e. they have the same values) or as formal polynomials (i.e. they have the same coefficients).
For the former, by little Fermat both sides are $\equiv 0\,$ for $\,x\equiv 0,1,\ldots, p\!-\!1.\,$ And, for the latter, let $\,f(x) =$ LHS $-$ RHS. Since LHS and RHS have same lead coefs we deduce that $f$ has degree $< p,$ and, by little Fermat, $\,f\,$ has $\,p\,$ distinct roots $\,1,2,\ldots p\,$ in the field $\,\Bbb Z/p.\,$ Therefore $\,f\,$ must be the zero polynomial (i.e. all coefs $\equiv 0)$ since a nonzero polynomial over a field (or domain) has no more roots than its degree (a proof follows by iteratively applying the Factor Theorem, and using the fact that the difference of any two distinct roots is nonzero so cancellable). See also the BiFactor Theorem.
Remark $ $ This may fail in non-domains, e.g. mod $\,8\!:\,\ x^2-1\,$ has $\,4\,$ roots $\, x\equiv \pm1,\,\pm 3,\,$ i.e. ${\rm odd}^2\equiv 1\pmod 8$
Solution 2:
Fermat's little theorem says that $x^p\equiv x$ modulo $p$. So the left hand side of your equation is $0$. The right hand side of your equation is also $0$, because one of the numbers
$$x,x-1,x-2,\dots,x-(p-1)$$
is divisible by $p$.