Show that the numerator of $1+\frac12 +\frac13 +\cdots +\frac1{96}$ is divisible by $97$

Let $\frac{x}{y}=1+\frac12 +\frac13 +\cdots +\frac1{96}$ where $\text{gcd}(x,y)=1$. Show that $97\;|\;x$.

I try adding these together, but seems very long boring and don't think it is the right way to solving. Sorry for bad english.

Solution 1:

If you group the fractions in pairs with the first pairing to last, second pairing to next-to-last, etc, you get $$1+\frac 1{96}=\frac {97}{96}, \frac 12+\frac 1{95}=\frac {97}{190}...$$ The sums of these pairs all have a numerator of $97$, and because $97$ is prime the common denominator will not have a factor of $97$, so in $\frac xy$, $x$ is a multiple of $97$.

Solution 2:

What we need to do is as follows: $$ \begin{equation}\begin{split} 1 + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{96} & = \Big(1+\frac{1}{96}\Big) + \Big(\frac{1}{2}+\frac{1}{95}\Big) + \ldots + \Big(\frac{1}{48} + \frac{1}{49}\Big) \\ & = \frac{97}{96} + \frac{97}{2*95} + \frac{97}{3*94} + \ldots + \frac{97}{48*49} \\ & = 97 \Big( \frac{1}{96} + \frac{1}{2*95} + \frac{1}{3*94} + \ldots + \frac{1}{48*49}\Big) \end{split}\end{equation} $$

Hence, the numerator is a multiple of $97$. To see that the denominator is not a multiple of $97$, note that $97$ is a prime, and the denominator contains natural numbers less than $97$ (in fact, the reduced denominator is a factor of $96$!), hence cannot possibly be a multiple of $97$. Thus, in it's reduced form, the numerator of the expression is a multiple of $97$.

In fact, Wolstenhomme's theorem says that the numerator is a multiple of $97^2 = 9409$!

Solution 3:

This is along the lines of DanielV's proposed solution.

We know $97$ is prime. Multiplying both sides by $96!$, it's enough to show that $\sum_{n=1}^{96} \frac{96!}{n}$ (which is a sum of integers) is divisible by $97$, because $96!$ and $97$ are coprime. Let $a_n = \frac{96!}{n}$ for $n\in\{1,\ldots,96\}$. Then we have $n a_n = 96!$, so $a_n \equiv 96! n^{-1} \pmod {97}$, where $n^{-1}$ is the inverse of $n$ in the integers mod $97$. Then $\sum_{n=1}^{96} a_n$ is divisible by $97$ because $$ \sum_{n=1}^{96} a_n \equiv 96! \sum_{n=1}^{96} n^{-1} \color{red}{=} 96! \sum_{n=1}^{96} n = 96! \frac{96 \cdot 97}{2} \equiv 0 \pmod{97}.$$ The red $\color{red}{=}$ holds because the inverse $n \mapsto n^{-1}$ is a permutation of $\{1,\ldots,96\}$.

Solution 4:

If you know that 97 is prime, and that every nonzero value has a multiplicative inverse mod a prime value, and that modular inverse is a bijection due to it being an involution, then you get:

$$\sum_{k = 1}^{96} k^{-1} \equiv \sum_{j = 1}^{96} j \pmod {97}$$

And the result follows from arithmetic sum.

More explicitly, letting $p = 97$,

$p \not | y$ because $y | (p - 1)!$ and $p$ is prime and $(x,y)$ are in reduced terms. Therefore:

$xy^{-1} \equiv 0 \pmod p$ iff $x \equiv 0 \pmod p$ implies the numerator of $\frac{x}{y}$ is divisible by $p$.

Since $\frac{x}{y} = \sum_{k=1}^p k^{-1}$, follows that

$$p | x \text{ iff } \sum_{k = 1}^{p-1} k^{-1} \equiv 0 \pmod p$$

Let $S_n \equiv n^{-1} \pmod p$ with $n$ ranging from $1$ to $p-1$. Then $S$ is a bijection, so

$$\sum_{n = 1}^{p-1} S_n \equiv \sum_{n = 1}^{p-1} n \pmod {p}$$

And the result follows from

$$p(p-1)/2 \equiv 0 \pmod p$$