19
$\begingroup$

From Fermat's little theorem and factor theorem, for any $x \in \mathbb{Z}/p\mathbb{Z}$, $$x(x-1)(x-2)\cdots(x-p+1)\equiv x^p-x$$ is satisfied. If we take derivative of this, we get $$\sum_{i=0}^{p-1}\prod_{j=0,i\neq j}^{p-1}(x-j)\equiv -1.$$ This formula can be derived by another way. \begin{align}&\sum_{i=0}^{p-1}\prod_{j=0,i\neq j}^{p-1}(x-j)\\ \equiv&\prod_{j=0,j\neq x}^{p-1}(x-j) +\sum_{i=0,i\neq x}^{p-1}\frac{1}{x-i}\prod_{j=0}^{p-1}(x-j) \\ \equiv&\prod_{j=1}^{p-1}j+\sum_{i=1}^{p-1}i\prod_{j=0}^{p-1}(x-j)\\ \equiv& -1 \end{align}

I prefer former way (because it's simpler!). However, I don't know why I can apply derivative although it's mod p. Can we prove it's ok to apply derivative?

$\endgroup$
2
  • 3
    $\begingroup$ You can formally define the derivative of polynomials in $F[x]$, and then prove that things like the product rule, etc, are satisfied. $\endgroup$
    – littleO
    Commented Nov 10, 2019 at 23:03
  • 4
    $\begingroup$ @littleO : I think the difficult point is how to get from a point wise equality ($P(x) \equiv Q(x)$ for all $x \in \mathbb{Z}$) to a polynomial equality ($P \equiv Q$). $\endgroup$
    – Joel Cohen
    Commented Nov 10, 2019 at 23:20

1 Answer 1

21
$\begingroup$

To be able to differentiate, you need to prove that your equality is not just true point wise, but as an equality of polynomials (which is strictly stronger).

Namely, let us denote $P \equiv Q \pmod p$ if all the coefficients of $P-Q$ are multiples of $p$ (we'll call that polynomial equality mod $p$). Notice that polynomial equality implies point wise equality :

$$P \equiv Q \pmod p \implies \forall x \in \mathbb{Z}, P(x) \equiv Q(x) \pmod p$$

But beware the converse isn't true in general (take for example $P=X^p-X$ and $Q=0$). Now we prove that the polynomial equality can be differentiated (while point wise equality cannot, using the same counter example) : indeed, if we assume $P \equiv Q \pmod p$, then we can write $P(X)-Q(X) = p R(X)$ with $R \in \mathbb{Z}[X]$. And by differentiating, we get $P'(X) - Q'(X) = p R'(X)$, so $P' \equiv Q' \pmod p$.

Now let's denote $P = X(X-1)(X-2)\ldots (X-p+1)$ and $Q = X^p -X$. And let's prove that $P \equiv Q \pmod p$, which will allow us to differentiate. Let us consider $R = P-Q$ and notice that $\deg R = p-1$ because the terms of degree $p$ of $P$ and $Q$ cancel out. Now remember that $k = \mathbb{Z}/p\mathbb{Z}$ is a field, and that $R(a) = 0$ for all $a \in k$. In other words, the polynomial $R \in k_{p-1}[X]$ has $p$ roots in $k$, so it must be $0$. Which means $P-Q \equiv 0 \pmod p$.

$\endgroup$

You must log in to answer this question.

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