View topic - A 23 • Art of Problem Solving

Peter wrote:

(Wolstenholme's Theorem) Prove that if
$1 + \frac {1}{2} + \frac {1}{3} + \cdots + \frac {1}{p - 1}$
is expressed as a fraction, where $p \ge 5$ is a prime, then $p^{2}$ divides the numerator.

This is an updated version of an older MathLinks post of mine, and I am submitting it here since I will refer to it in a number of other proofs.

I will generalize the problem, but first I explain some preliminaries about primes.

1. p-adic evaluation

Let $p$ be an arbitrary prime. We denote by $\mathbb{Z}_{p}$ the field of residues of integers modulo $p$ .

For any rational number $x$ , we will now define a so-called $p$ -adic evaluation of $x$ . This evaluation will be denoted by $v_{p}\left(x\right)$ , and it is defined as follows: If $x\neq 0$ , then $v_{p}\left(x\right)$ is the greatest integer $k$ such that $\frac {x}{p^{k}}$ can be written as a fraction of two integers with the denominator not being divisible by $p$ . Besides, we set $v_{p}\left(0\right) = + \infty$ , where $+ \infty$ is just a symbol satisfying $+ \infty > a$ and $+ \infty + a = + \infty$ for any integer $a$ (what we will mainly need is that $v_{p}\left(0\right) > v_{p}\left(x\right)$ for any nonzero $x$ ).

We can easily see how to compute $v_{p}\left(x\right)$ for rationals $x\neq 0$ :
If $x$ is a nonzero integer, then $v_{p}\left(x\right)$ is the greatest integer $k$ such that $p^{k}$ divides $x$ (particularly, $v_{p}\left(x\right) = 0$ if $p$ doesn't divide $x$ ); if $x$ is a fraction of two nonzero integers, say $x = \frac {a}{b}$ with integers $a$ and $b$ , then $v_{p}\left(x\right) = v_{p}\left(a\right) - v_{p}\left(b\right)$ .

Note that there is a simple way to interpret the sign of the $p$ -adic evaluation $v_{p}\left(x\right)$ of a rational number $x$ : If we write $x$ as a reduced fraction (i. e. a fraction with numerator and denominator coprime; if $x$ is an integer, then just write it in the form $x = \frac {x}{1}$ ), and it turns out that the numerator is divisible by $p$ , then $v_{p}\left(x\right) > 0$ ; if neither the numerator nor the denominator is divisible by $p$ , then $v_{p}\left(x\right) = 0$ ; if the denominator is divisible by $p$ , then $v_{p}\left(x\right) < 0$ .

It is rather easy to prove that for any two rational numbers $x$ and $y$ , we have $v_{p}\left(xy\right) = v_{p}\left(x\right) + v_{p}\left(y\right)$ and $v_{p}\left(x + y\right)\geq\min\left(v_{p}\left(x\right);\;v_{p}\left(y\right)\right)$ .

2. Working with fractions modulo p

We will also need some familiarity with fractions in $\mathbb{Z}_{p}$ . The main idea is to extend the notion of congruence modulo $p$ from integers to rational numbers with nonnegative $p$ -adic evaluation: If $x$ and $y$ are two rational numbers such that $v_{p}\left(x\right)\geq 0$ and $v_{p}\left(y\right)\geq 0$ , then we say that $x\equiv y\mod p$ if and only if $v_{p}\left(x - y\right) > 0$ . Thus we have defined an equivalence relation (that it is an equivalence relation is easy to prove - do it for yourself) on the set of all rational numbers with nonnegative $p$ -adic evaluation. Now one could expect that, in this way, we would obtain a kind of new group of remainders, say $\mathbb{Q}_{p}$ - but in fact, we get nothing but our old familiar $\mathbb{Z}_{p}$ , since for every rational number $x$ , there is one and only one integer $n$ satisfying $0\leq n < p$ such that $x\equiv n\mod p$ (this is again easy to prove). Hence, you can work with rational numbers whose $p$ -adic evaluation is nonnegative in the same way as you work with remainders modulo $p$ . This also means that modulo $p$ , you can uniquely divide by any integer not divisible by $p$ . [A nice application of this is problem 4 of the IMO 2005 - see Fedor Petrov's proof in post #2.]

3. Generalization of Wolstenholme's Theorem

Now, the problem A 23 asks us to show that if $p$ is a prime number such that $p\geq 5$ , then $v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k}\right)\geq 2$ . This is a particular case (namely, the $u = 1$ case) of the following result:

Theorem 1. If $p$ is a prime number and $u$ is an odd integer such that $p\geq u + 3$ and $u\geq 0$ , then

$v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^{u}}\right)\geq 2$ .

Proof of Theorem 1. We will first work in $\mathbb{Q}$ and only later come over into $\mathbb{Z}_{p}$ . Note that $p > 2$ (since $p\geq u + 3$ and $u\geq 0$ ). We start with the Gauss trick:

$2\sum_{k = 1}^{p - 1}\frac {1}{k^{u}} = \sum_{k = 1}^{p - 1}\frac {1}{k^{u}} + \sum_{k = 1}^{p - 1}\frac {1}{\left(p - k\righ...$ .

Now denote $s_k=\sum_{i=2}^u\left(-1\right)^{u-i}\binom{u}{i}p^{i-2}k^{u-i}$ for every $k\in\left\{1,2,...,p-1\right\}$ . Obviously, $s_k$ is an integer for every $k$ . We can expand $\left(p - k\right)^{u}$ according to the binomial formula:

$\left(p - k\right)^{u}=\sum_{i=0}^u\left(-1\right)^{u-i}\binom{u}{i}p^ik^{u-i}$
$=\left(-1\right)^{u-0}\binom{u}{0}p^0k^{u-0}+\left(-1\right)^{u-1}\binom{u}{1}p^1k^{u-1}+\sum_{i=2}^u\left(-1\right)^{u-i}\bi...$
$=\left(-1\right)^uk^u+\left(-1\right)^{u-1}upk^{u-1}+p^2\sum_{i=2}^u\left(-1\right)^{u-i}\binom{u}{i}p^{i-2}k^{u-i}$
$=\left(-1\right)^uk^u+\left(-1\right)^{u-1}upk^{u-1}+p^2s_k=\left(-1\right)k^u+1upk^{u-1}+p^2s_k$ (since u is odd, so that $\left(-1\right)^u=-1$ and $\left(-1\right)^{u-1}=1$ )
$=-k^u+upk^{u-1}+p^2s_k$ .

Thus, $k^u+\left(p-k\right)^u = upk^{u-1}+p^2s_k$ for every $k\in\left\{1,2,...,p-1\right\}$ , and therefore

$2\sum_{k = 1}^{p - 1}\frac {1}{k^{u}} = \sum_{k = 1}^{p - 1}\frac {k^{u} + \left(p - k\right)^{u}}{k^{u}\left(p - k\right)^{u...$
$= p \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}}$ .

But since $2$ isn't divisible by $p$ (since $p > 2$ ), we have $v_{p}\left(2\right) = 0$ , so that

$v_{p}\left(2\sum_{k = 1}^{p - 1}\frac {1}{k^{u}}\right) = \underbrace{v_{p}\left(2\right)}_{=0} + v_{p}\left(\sum_{k = 1}^{p ...$ .

On the other hand,

$v_{p}\left(2\sum_{k = 1}^{p - 1}\frac {1}{k^{u}}\right) = v_{p}\left( p \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left...$
$= 1 + v_{p}\left( \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}} \right)$ .

Thus,

$v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^{u}}\right) = 1 + v_{p}\left( \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\lef...$ .

Hence, instead of showing $v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^{u}}\right)\geq 2$ , it will be enough to prove $v_{p}\left( \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}} \right)\geq 1$ . This is equivalent to $v_{p}\left( \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}} \right) > 0$ , i. e. to $\sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}} \equiv 0\mod p$ . Now we start working in $\mathbb{Z}_{p}$ . In fact, for every $k\in\left\{1,2,...,p-1\right\}$ , we can consider the fraction $\frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}}$ in $\mathbb{Z}_{p}$ , since it has a nonnegative $p$ -adic evaluation (because its denominator, $k^{u}\left(p - k\right)^{u}$ , is not divisible by $p$ , since $1\leq k\leq p - 1$ and since $p$ is a prime). Modulo $p$ , the numerator $uk^{u-1}+ps_k$ of this fraction can be simplified to $uk^{u - 1}$ (since $p\equiv 0\mod p$ , and thus all terms containing $p$ can be omitted). Also, the denominator can be simplified: Since $p - k\equiv - k\mod p$ , we have $k^{u}\left(p - k\right)^{u}\equiv k^{u}\left( - k\right)^{u} = \left( - 1\right)^{u}k^{2u} \mod p$ . Hence, $\frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}} \equiv \frac {uk^{u-1}}{\left(-1\right)^u k^{2u}}\mod p$ . Therefore,

(1) $\sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}}\equiv\sum_{k = 1}^{p - 1}\frac {uk^{u - 1}}{\left( - ...$ .

But by Fermat's small theorem, $k^{p - 1}\equiv 1\mod p$ for every integer $k$ such that $1\leq k\leq p - 1$ . Thus, $k^{ - u - 1}\equiv k^{ - u - 1}k^{p - 1} = k^{p - u - 2}\mod p$ , and the relation (1) becomes

$\sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}}\equiv\frac {u}{\left( - 1\right)^{u}}\sum_{k = 1}^{p ...$ .

Now, $p - u - 2\geq 1$ (since $p\geq u + 3$ ) and $p - u - 2\leq p - 2$ . Also, $p$ is an odd prime (since $p$ is a prime and $p > 2$ ). Now, according to http://www.problem-solving.be/pen/viewtopic.php?t=676 part a) (and also http://www.artofproblemsolving.com/Forum/viewtopic.php?t=40171 ), we have:

Theorem 2. If $p$ is an odd prime and $\rho$ is an integer such that $1\leq\rho\leq p - 2$ , then $p\mid\sum_{k = 1}^{p - 1}k^{\rho}$ .

Applying this Theorem 2 to our prime $p$ and $\rho = p - u - 2$ (we know that $p$ is an odd prime and $\rho = p - u - 2$ satisfies $1\leq p - u - 2\leq p - 2$ ), we get $p\mid\sum_{k = 1}^{p - 1}k^{p - u - 2}$ , so that $\sum_{k = 1}^{p - 1}k^{p - u - 2}\equiv 0\mod p$ , and thus

$\sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}}\equiv\frac {u}{\left( - 1\right)^{u}} \underbrace{\su...$ .

This completes the proof of Theorem 1.

4. A divisibility by $p^3$

We can use almost the same tactics to prove a similar result:

Theorem 3. If $p$ is a prime number such that $p>3$ , then

$v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^p}\right)\geq 3$ .

Proof of Theorem 3. It is known that for every integer $i$ such that $0<i<p$ , we have $p\mid \binom{p}{i}$ (since $p$ is prime); in other words, $\binom{p}{i}\equiv 0\mod p$ .

Besides, $p-2>0$ (since $p>3>2$ ).

Set $u=p$ . Also, denote $s_k=\sum_{i=2}^u\left(-1\right)^{u-i}\binom{u}{i}p^{i-2}k^{u-i}$ for every $k\in\left\{1,2,...,p-1\right\}$ . Obviously, $s_k$ is an integer for every $k$ . Then, every $k\in\left\{1,2,...,p-1\right\}$ satisfies

$s_k=\sum_{i=2}^u\left(-1\right)^{u-i}\binom{u}{i}p^{i-2}k^{u-i}=\sum_{i=2}^p\left(-1\right)^{p-i}\binom{p}{i}p^{i-2}k^{p-i}$ (since $u=p$ )
$=\sum_{i=2}^{p-1}\left(-1\right)^{p-i}\underbrace{\binom{p}{i}}_{\substack{\equiv 0\mod p,\\ \text{ since } 0<i<p}}p^{i...$
$\equiv \underbrace{\sum_{i=2}^{p-1}\left(-1\right)^{p-i}0p^{i-2}k^{p-i}}_{=0}+\underbrace{\left(-1\right)^{p-p}\binom{p}{p}0k...$ .

We will first work in $\mathbb{Q}$ and only later come over into $\mathbb{Z}_{p}$ . Just as in the proof of Theorem 1, we can show that

(2) $v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^{u}}\right) = 1 + v_{p}\left( \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\lef...$ .

Since $u=p$ , we have

$v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^{u}}\right) = v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^p}\right)$

and

$v_{p}\left( \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}} \right) = v_{p}\left( \sum_{k = 1}^{p - 1...$
$= v_{p}\left( p\cdot \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \right)$ (since $\sum_{k = 1}^{p - 1} \frac {pk^{p-1}+ps_k}{k^p\left(p - k\right)^p} = \sum_{k = 1}^{p - 1} \frac {p\left(k^{p-1}+s_k\right)}{...$ )
$= \underbrace{v_p\left(p\right)}_{=1} + v_p\left( \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \right) =...$ .

Thus, (2) becomes

$v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^p}\right) = 1 + \left(1 + v_p\left( \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\l...$ .

In other words,

$v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^p}\right) = 2 + v_p\left( \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\...$ .

Hence, instead of showing $v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^{p}}\right)\geq 3$ , it will be enough to prove $v_p\left( \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \right)\geq 1$ . This is equivalent to $v_p\left( \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \right) > 0$ , i. e. to $\sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \equiv 0\mod p$ . Now we start working in $\mathbb{Z}_{p}$ . In fact, for every $k\in\left\{1,2,...,p-1\right\}$ , we can consider the fraction $\frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p}$ in $\mathbb{Z}_{p}$ , since it has a nonnegative $p$ -adic evaluation (because its denominator, $k^p\left(p - k\right)^p$ , is not divisible by $p$ , since $1\leq k\leq p - 1$ and since $p$ is a prime). Modulo $p$ , the numerator $k^{p-1}+s_k$ of this fraction can be simplified to $k^{p-1}$ (since $s_k\equiv 0\mod p$ , and thus the term $s_k$ can be omitted). Also, the denominator can be simplified: Since $p - k\equiv - k\mod p$ , we have $k^p\left(p - k\right)^p\equiv k^p\left( - k\right)^p = \left( - 1\right)^pk^{2p} \mod p$ . Hence, $\frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \equiv \frac {k^{p-1}}{\left( - 1\right)^pk^{2p}} \mod p$ . Therefore,

(3) $\sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \equiv \sum_{k = 1}^{p - 1}\frac {k^{p-1}}{\left( - 1\right...$ .

But by Fermat's small theorem, $k^p\equiv k\mod p$ for every integer $k$ . Thus, $\left(k^p\right)^2\equiv k^2\mod p$ , so that $k^{2p}=\left(k^p\right)^2\equiv k^2\mod p$ . Hence, the relation (3) becomes

$\sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \equiv \frac{1}{\left(-1\right)^p} \sum_{k = 1}^{p - 1}\und...$ .

Now, $p-3\geq 1$ (since $p>3$ yields $p-3>0$ , and $p-3\in\mathbb{Z}$ ) and $p-3\leq p-2$ . Also, $p$ is an odd prime (since $p$ is a prime and $p > 2$ ). Applying Theorem 2 to our prime $p$ and $\rho = p - 3$ (we know that $p$ is an odd prime and $\rho = p-3$ satisfies $1\leq p-3\leq p - 2$ ), we get $p\mid\sum_{k = 1}^{p - 1}k^{p - 3}$ , so that $\sum_{k = 1}^{p - 1}k^{p - 3}\equiv 0\mod p$ , and thus

$\sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \equiv \frac{1}{\left(-1\right)^p} \underbrace{\sum_{k = 1}...$ .

This completes the proof of Theorem 3.

[EDIT: Made the proof of Theorem 1 slightly more formal, and added section 4. See the other thread for the old version of this post.]

Darij

A 23

Login