2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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$. $\endgroup$
    – guest
    Commented Nov 3, 2014 at 2:03
  • $\begingroup$ Thanks. I'm new to this site, and any advice any formatting posts, phrasing questions, etc. can help. $\endgroup$
    – Nelly
    Commented Nov 3, 2014 at 2:09
  • $\begingroup$ 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)$? $\endgroup$
    – Jyrki Lahtonen
    Commented Nov 3, 2014 at 18:17
  • $\begingroup$ 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. $\endgroup$
    – Jyrki Lahtonen
    Commented Nov 3, 2014 at 18:19

1 Answer 1

Reset to default
3
$\begingroup$

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.

So that's a place to start trying to approach the problem.

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.

There are surely many different places to start. Pick any of them and try to learn more about the problem: maybe you'll see a path to the solution, or maybe just something interesting or useful, or you might go nowhere at all. You won't know until you try, though.

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).

$\endgroup$
2
  • $\begingroup$ Thanks for the tip, I have been attempting to find a solution; experimenting with Euclid's Alogirthm, etc. Maybe I'm on the wrong track but I'll keep up the research. $\endgroup$
    – Nelly
    Commented Nov 3, 2014 at 2:18
  • 2
    $\begingroup$ 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. $\endgroup$
    – guest
    Commented Nov 3, 2014 at 2:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .