# Number of roots of a polynomial over a finite field

For any $g$ in $\mathbb{Z}/p\mathbb{Z}[x]$ prove that the degree of $f = \gcd(x^p - x, g(x))$ is exactly the number of distinct roots of $g$ in $\mathbb{Z}/p\mathbb{Z}$.

My main problem is that I do not really understand how to approach this problem at all. I am very new to solving proofs and any type of help would be appreciated thank you.

• You should put your question in the text, and also amend the question to read "...the number of distinct roots of $g$ in $\mathbb{Z}/p\mathbb{Z}$". Otherwise one might think you are referring to roots of $g$ in some algebraic closure of $\mathbb{Z}/p\mathbb{Z}$ and then the result does not hold: in $Z/3Z$, for instance, the polynomial $x^2+1$ is irreducible because it has no roots, but it has two distinct roots in an algebraic closure of $\mathbb{Z}/3\mathbb{Z}$ and of course its gcd with $x^3-x$ is $1$. Commented Nov 3, 2014 at 2:03
• Thanks. I'm new to this site, and any advice any formatting posts, phrasing questions, etc. can help. Commented Nov 3, 2014 at 2:09
• It sounds you are not scared of doing a little bit experimenting. Let's try this with small $p$ and a $g(x)$ we can control. No purpose in mind yet. Just trying to see how the land lies. First with $p=3$. You can tell that $g(x)=x(x+1)$ has two disting roots in $\Bbb{Z}/3\Bbb{Z}$. Check that the $\gcd$ is also quadratic. What about $g(x)=x(x-1)$? What about $g(x)=(x+1)(x-1)$? What about $g(x)=(x-1)^2$? You may have noticed something already. Try with $p=5$ and $g(x)=(x-2)(x-3)$, $g(x)=(x+1)^2$! Ok, you can check that $g(x)=x^2+2$ has no zeros modulo five. What about $g(x)=x(x^2+2)$? Commented Nov 3, 2014 at 18:17
• The point of all that experimenting was to make you wonder about the factors of $x^p-x$ (it sounded you had not seen it factored yet). Also about those of $g(x)$. Anything common? How are they related to the zeros? Reread Hurkyl's hints in light of what you learned. If you get bored with this, then read guest's comment under Hurkyl's answer instead. Commented Nov 3, 2014 at 18:19

Sometimes, just taking things straightforward can help. You are computing a "greatest common divisor", so understanding the divisors -- that is, the factors -- of $g(x)$ and $x^p - x$ is likely to be very useful, assuming you can say something about them.
You might do research: e.g. your textbook might say something about $x^p - x$ or $\gcd(x^p - x, g(x))$ or maybe just about general polynomials over this field that you could use to solve this problem.
And you can work backwards: knowing what you are supposed to prove, you can guess as to exactly what the divisors of $x^p -x$ should be (if you don't know already and can't figure it out more directly).
• Nelly, if you get involved with Euclid's algorithm you will soon be swamped. Take any element $a$ of $\mathbb{Z}/p\mathbb{Z}$. Raise it to the $p$-th power. What do you get? Remember Fermat's little theorem. It gives you a gateway to find all roots of $x^p-x$ in $\mathbb{Z}/p\mathbb{Z}$ (what is the maximum number of distinct roots of a polynomial of degree $p$?). Once you have successfully factored that polynomial, things will become much easier. Commented Nov 3, 2014 at 2:21