Let \(f(x)\in\FF_p[x]\) and let \[ g(x)=x^p-x. \] Show that \(\gcd(f,g)\) is the product of the distinct linear factors of \(f\) in \(\FF_p[x]\).
Solution
Let \[ A\coloneqq\{a\in\FF_p:f(a)=0\} \] and define \[ h(x)\coloneqq\prod_{a\in A}(x-a), \] with the empty product interpreted as \(1\).
1. In \(\FF_p[x]\),\[ x^p-x=\prod_{a\in\FF_p}(x-a), \]and all these linear factors are distinct.
Every \(a\in\FF_p\) satisfies \[ a^p=a, \] so every element of \(\FF_p\) is a root of \(x^p-x\). These are \(p\) distinct roots of a monic polynomial of degree \(p\), so the displayed factorization follows. Equivalently, its derivative is \[ (x^p-x)'=px^{p-1}-1=-1 \] in characteristic \(p\), which is nonzero and confirms that none of the roots is repeated.
2. The polynomial \(h\) divides both \(f\) and \(g\).
For each \(a\in A\), the factor theorem gives \[ x-a\mid f. \] The distinct linear polynomials \(x-a\) are pairwise coprime, so their product \(h\) divides \(f\). By step 1, the same product is a subproduct of the factorization of \(g\), hence \(h\mid g\).
3. Every common divisor of \(f\) and \(g\) divides \(h\).
Let \(d\) be a monic common divisor of \(f\) and \(g\). Since \(d\mid g\), step 1 and unique factorization in \(\FF_p[x]\) show that \(d\) is a product of some of the distinct factors \[ x-a, \qquad a\in\FF_p. \] If \(x-a\) occurs in \(d\), then \(x-a\mid f\) because \(d\mid f\), so the factor theorem gives \(f(a)=0\). Thus \(a\in A\). Every factor of \(d\) therefore occurs in \(h\), and hence \(d\mid h\).
4. The monic greatest common divisor is\[ \boxed{ \gcd(f,x^p-x)=\prod_{\substack{a\in\FF_p\\f(a)=0}}(x-a), } \]the product of the distinct linear factors of \(f\) over \(\FF_p\).
Step 2 shows that \(h\) is a common divisor, and step 3 shows that every common divisor divides \(h\). Hence \(h\) is the monic greatest common divisor. Its factors are exactly the monic linear factors \(x-a\) of \(f\), each occurring once.
5. Q.E.D.
Step 4 is the required identity.