Sum Ways to Simplify a Some

Many moons ago, I was met with this incredible fact:

$\begin{aligned} \frac1x + \frac1{x+1} + \cdots + \frac1{x+p-1} \equiv \frac{-1}{x^p-x} \quad (\text{mod } p),\end{aligned}$

where $p$ is any prime. It’s so surprising that it’s stuck with me until now, so I figured I should probably talk about it.

How would anyone go about showing this? Well, polynomials in a modulo system $\mathbb{Z}/p\mathbb{Z}$ can behave in interesting ways, since two polynomials which take on the same output for each of $0, 1, 2, \ldots, p-1$ over $\mathbb{Z}/p\mathbb{Z}$ can be considered essentially the same polynomial.

The natural thing to try turns out to be a good first move in this case: Let’s reduce the left side of the equivalence into a single fraction to turn

$\begin{aligned} \frac1x + \frac1{x+1} + \cdots + \frac1{x+p-1}\end{aligned}$

into

$\begin{aligned} \frac{(x+1)\cdots(x+p-1) + x(x+2)\cdots(x+p-1) + \cdots + x\cdots(x+p-2)}{x(x+1)\cdots(x+p-1)} \end{aligned}.$

Then, notice that if we plug in any value for $x$ , all the products in the numerator vanish except one, which in each case equals to $(p-1)!$ (Yes, this is very exciting, but the exclamation point here denotes factorial.)

Now, our sum has reduced into the much simpler expression $\begin{aligned} \frac{(p-1)!}{x(x+1)\cdots(x+p-1)} \end{aligned}.$ Since the set $\{0, -1, -2, \ldots, -(p-1)\},$ which is equivalent to the set $\{0, 1, 2, \ldots, p-1\}$ modulo $p,$ comprise precisely the set of roots of the polynomial $x^p-x,$ (by Fermat’s Little Theorem) we have that $x(x+1)\cdots(x+p-1)\equiv x^p-x (\text{mod } p).$

Finally, we can conclude that

$\begin{aligned} \frac{(p-1)!}{x^p-x} \equiv \frac{-1}{x^p-x} \quad (\text{mod } p),\end{aligned}$

by Wilson’s Theorem.

An astute reader may have noticed that our initial expanded numerator looks like a product rule expansion. And indeed,

$\frac{d}{dx} [x(x+1)\cdots(x+p-1)]$
$= (x+1)\cdots(x+p-1) + x(x+2)\cdots(x+p-1) + \cdots + x\cdots(x+p-2).$

We therefore immediately get that

$\begin{aligned} \frac{\frac{d}{dx} [x(x+1)\cdots(x+p-1)]}{x^p-x} \equiv \frac{\frac{d}{dx} (x^p-x)}{x^p-x} \equiv \frac{px^{p-1}-1}{x^p-x} \equiv \frac{-1}{x^p-x} \quad (\text{mod } p),\end{aligned}.$

This method is more direct, but it feels mildly suspicious, because what does it really mean to take derivatives modulo some number?

If you think this is suspicious, then our last method is going to seem extremely dubious. But it’s also kind of awesome. It relies on the observation that $\frac{d}{dx} \ln(f) = \frac{f'}{f},$ for any function $f$ of $x$ :

$\begin{aligned} \frac1x + \frac1{x+1} + \cdots + \frac1{x+p-1} &\equiv \frac{d}{dx} (\ln(x) + \ln(x+1) + \cdots + \ln(x+p-1)) \\ &\equiv \frac{d}{dx} \ln(x(x+1)\cdots(x+p-1)) \\ &\equiv \frac{d}{dx} \ln(x^p-x) \\ &\equiv \frac{\frac{d}{dx} (x^p-x)}{x^p-x}\\ &\equiv \frac{-1}{x^p-x} \quad (\text{mod } p),\end{aligned}$

A Few Clarifications

I think part of the reason this equivalence is so surprising is because at first, it makes no sense. If we plug in any value to $x$ as is, we get something undefined on both sides, since we’re dividing by $0$ (which here means multiplying by the inverse of $0,$ a value that does not exist). The slightly less glamorous equivalence we’re actually showing is the following:

$\begin{aligned} (x+1)\cdots(x+p-1) + x(x+2)\cdots(x+p-1) + \cdots + x\cdots(x+p-2) \equiv -1 \\(\text{mod } p),\end{aligned}$

which we get from the original just by multiplying $x^p-x$ on both sides.

I also lied a little bit before when I claimed that two polynomials which are equal for all values modulo an integer are considered the same—our assertion only worked because the degree of the two polynomials in our equivalence (left side has degree $p-1$ ; right side has degree $0$ ) are both less than $p,$ the number of points we tested the polynomials against. This is analogous to polynomials in non-modulo systems like $\mathbb{R},$ since for example, three points determine a quadratic.

Little formalities aside, I had a lot of fun thinking of ways to solve this problem! I’d love to know if there are others I haven’t thought of, so if you think of any, feel free to let me know.

Source: Dr.V’s Finite Fields class.

Sophia Liao

Sum Ways to Simplify a Some

Leave a comment Cancel reply