# Finite Sum & Divisibility – 2

Standard

Earlier this year I discussed a finite analogue of the harmonic sum. Today I wish to discuss a simple fact about finite harmonic sums.

If $p$ is a prime integer, the numerator of the fraction $1+\frac{1}{2}+\frac{1}{3}+\ldots + \frac{1}{p-1}$ is divisible by $p$.

We wish to treat the given finite sum modulo $p$, hence we can’t just add up fractions. We will have to consider each fraction as inverse of an integer modulo p. Observe that for $0, we have inverse of each element $i$ in the multiplicative group $\left(\mathbb{Z}/p\mathbb{Z}\right)^\times$, i.e. there exist an $i^{-1}$ such that $i\cdot i^{-1}\equiv 1 \pmod p$.

For example, for $p=5$, we have $1^{-1}=1, 2^{-1}=3, 3^{-1}=2$ and $4^{-1}=4$.

Hence we have
$\displaystyle{i\cdot \frac{1}{i}\equiv 1 \pmod p ,\qquad (p-i)\cdot \frac{1}{p-i} \equiv 1 \pmod p }$
for all $0.

Hence we have:
$\displaystyle{i\left(\frac{1}{i}+\frac{1}{p-i}\right)\equiv i\cdot \frac{1}{i} - (p-i)\cdot \frac{1}{p-i} \equiv 0 \pmod p}$

Thus we have:
$\displaystyle{\frac{1}{i}+\frac{1}{p-i}\equiv 0 \pmod p}$

The desired result follows by summation.

We can, in fact, prove that the above harmonic sum is divisible by $p^2$, see section 7.8 of G. H. Hardy and E. M. Wright’s An Introduction to the Theory of Numbers for the proof.

$\displaystyle{\sum_{k=2}^{n} \frac{1}{k}}$  can never be an  integer for any value of $n$.
Firstly, observe that among the natural numbers from 2 to $n$ there is exactly one natural number which has the highest power of 2 as its divisor. Now, while summing up the reciprocals of these natural numbers we will get a fraction as the answer. In that fraction, the denominator will be an even number since it’s the least common multiple of all numbers from 2 to $n$. And the numerator will be an odd number since it’s the sum of $(n-2)$ even numbers with one odd number (corresponding to the reciprocal of the number with the highest power of 2 as the factor). Since under no circumstances an even number can completely divide an odd number, denominator can’t be a factor of the numerator. Hence the fraction can’t be reduced to an integer and the sum can never be an integer.