Roots modulo a prime

81 Views Asked by At

Let us consider the following result:

Note that in the ring of polynomials with coefficients $mod p$, the product $x(x-1)(x-2)...(x-p+1)$ has all possible roots, and equals $x^p-x$ by Fermat's Little Theorem and unique factorization in this ring.

I am trying to prove it but without any suscess. I wante to see a proof or a reference about this.

My second question is about the validity of this result for multivariate polynomials, say three variables.

2

There are 2 best solutions below

2
On BEST ANSWER

By Fermat's Little Theorem, $x^p - x \in \mathbb{F}_p[x]$ has root $x=a$ for all $a \in \mathbb{F}_p$; therefore, each $x - a \mid x^p - x$. Since $\mathbb{F}_p[x]$ is a UFD (because $\mathbb{F}_p$ is a field) and each $x - a$ is irreducible and distinct, it follows that $x(x-1) \cdots (x-p+1) \mid x^p - x$. The left and right hand sides have equal degree and therefore the quotient must be a constant polynomial; and by looking at the coefficient of $x^p$ on both sides you can conclude that constant must be 1.

As for the case of multivariate polynomials, you might think of the ideal of all polynomials in $\mathbb{F}_p[x,y,z]$ which are zero when evaluated at any point in $\mathbb{F}_p^3$. This would be equal to $\bigcap_{a,b,c \in \mathbb{F}_p} \langle x-a, y-b, z-c \rangle$. I'm not sure off the top of my head what exactly this ideal is - though a reasonable conjecture would be $\langle x^p - x, y^p - y, z^p - z \rangle$.

0
On

For single variables, the standard approach would be to first prove the following lemma:

If $f(x)$ is a polynomial of degree $n >0$ in $F_p[x]$ and $f(a)=0$ for some $a\in F_p$, then there exists a polynomial $g(x)$ of degree $n-1$ with $$f(x) = (x-a)g(x).$$

You can prove this lemma by proving that polynomial division works in $F_p[x]$, and then showing that if $a$ is a root of $f(x)$, the remainder when dividing $f(x)$ by $x-a$ must be zero.

You can then prove that $x^p-x$ has the factorization you list by inductively pulling out roots.

All of this is covered in any intro text on elementary number theory.