Numerator of p-1th Harmonic Number is Divisible by Prime p

From ProofWiki
Jump to navigation Jump to search


Let $p$ be an odd prime.

Consider the harmonic number $H_{p - 1}$ expressed in canonical form.

The numerator of $H_{p - 1}$ is divisible by $p$.

Proof 1

Add the terms of $H_{p - 1}$ using the definition of rational addition to obtain $\dfrac m n$.

Do not cancel common prime factors from $m$ and $n$.

It is seen that $n = \paren {p - 1}!$

Hence $p$ is not a divisor of $n$.

The numerator $m$ is seen to be:

$m = \dfrac {\paren {p - 1}!} 1 + \dfrac {\paren {p - 1}!} 2 + \cdots + \dfrac {\paren {p - 1}!} {p - 1}$

Thus it is sufficient to show that $m$ is a multiple of $p$.

Each term in this sum is an integer of the form $\dfrac {\paren {p - 1}!} k$.

For each $k \in \set {1, 2, \ldots, p - 1}$, define $k'= - \dfrac {\paren {p - 1}!} k \bmod p$.

By Wilson's Theorem

$k k' \equiv -\paren {p - 1}! \equiv 1 \pmod p$


$k' \equiv k^{-1} \pmod p$

From the corollary to Reduced Residue System under Multiplication forms Abelian Group:

$\struct {\Z'_p, \times}$ is an abelian group.

Since Inverse in Group is Unique, the set:

$\set {1', 2', \ldots, \paren {p - 1}'}$

is merely the set:

$\set {1, 2, \ldots, p - 1}$

in a different order.


\(\ds m\) \(=\) \(\ds \dfrac {\paren {p - 1}!} 1 + \dfrac {\paren {p - 1}!} 2 + \cdots + \dfrac {\paren {p - 1}!} {p - 1}\)
\(\ds \) \(\equiv\) \(\ds 1 + 2 + \cdots + p - 1\) \(\ds \pmod p\)
\(\ds \) \(\equiv\) \(\ds \frac {p \paren {p - 1} } 2\) \(\ds \pmod p\) Closed Form for Triangular Numbers
\(\ds \) \(\equiv\) \(\ds 0\) \(\ds \pmod p\)


Proof 2

From Polynomial x^p - x is Congruent mod p to x to the p-1 Rising:

$x^{\overline p} \equiv x^p - x$

Thus from Sum over k of Unsigned Stirling Numbers of First Kind by x^k:

$\displaystyle \left[{p \atop k}\right] \equiv \delta_{k p} - \delta _{k 1}$


$\displaystyle \left[{p \atop k}\right]$ denotes an unsigned Stirling number of the first kind
$\delta$ is the Kronecker delta.

The result follows from Harmonic Number as Unsigned Stirling Number of First Kind over Factorial.

Historical Note

Donald E. Knuth reports in his The Art of Computer Programming: Volume 1: Fundamental Algorithms, 3rd ed. ($1997$) that this result was established by Edward Waring in $1782$, but he gives no further details.