Solution

Assume that $u(x)$ is squarefree and satisfies

$$ u(x)=p_1(x)p_2(x)\cdots p_r(x), $$

as in (6). Let $v(x)$ be any polynomial satisfying

$$ v(x)^p\equiv v(x)\pmod{u(x)}. $$

Equation (10) gives

$$ v(x)^p-v(x)

\prod_{0\le s<p}(v(x)-s). $$

Since $v(x)^p\equiv v(x)\pmod{u(x)}$, the polynomial $u(x)$ divides the left-hand side; hence

$$ u(x)\mid \prod_{0\le s<p}(v(x)-s). $$

The factors $v(x)-s$ and $v(x)-t$ are relatively prime whenever $s\ne t$, because

$$ (v(x)-s)-(v(x)-t)=t-s, $$

and $t-s\not\equiv0\pmod p$. Therefore

$$ \gcd(v(x)-s,;v(x)-t)=1 \qquad (s\ne t). $$

Since $u(x)$ is squarefree, each irreducible factor $p_j(x)$ of $u(x)$ divides exactly one of the factors $v(x)-s$. Consequently the polynomials

$$ g_s(x)=\gcd(v(x)-s,;u(x)) \qquad (0\le s<p) $$

are pairwise relatively prime, and every irreducible factor of $u(x)$ occurs in exactly one of them.

Because the product of the $g_s(x)$ contains every irreducible factor $p_j(x)$ exactly once, and because $u(x)$ itself is the product of those distinct irreducible factors, we obtain

$$ u(x)=\prod_{0\le s<p} g_s(x). $$

Substituting the definition of $g_s(x)$ yields

$$ u(x)

\prod_{0\le s<p} \gcd(v(x)-s,;u(x)), $$

which is equation (14).

This completes the proof.

∎

TAOCP 4.6.2 Exercise 7

Solution

$$ v(x)^p-v(x)

$$ u(x)