# 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.

# Recursion and Periodicity

Standard

One of the simplest recursive formula that I can think of is the one which generates the Fibonacci sequence, $F_{n+1} = F_n +F_{n-1}, n\geq 1$ with $F_0 = F_1=1$. So, I will illustrate a following general concept about recursions using Fibonacci sequence.

A sequence generated by a recursive formula is periodic modulo k, for any positive integer k greater than 1.

I find this fact very interesting because it means that a sequence which is strictly increasing when made bounded using the modulo operation (since it will allow only limited numbers as the output of recursion relation), will lead to a periodic cycle.

Following are the first 25 terms of the Fibonacci sequence:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025.

And here are few examples modulo k, for k=2,3,4,5,6,7,8

As you can see, the sequence repeats as soon as 1,0 appears. And from here actually one can see why there should be a periodicity.

For the sequence to repeat, what we need is a repetition of two consecutive values (i.e. the number of terms involved in the recursive formula) in the sequence of successive pairs. And for mod k, the choices are limited, namely k^2.  Now, all we have to ensure is that “1,0” should repeat. But since consecutive pairs can’ repeat (as per recursive formula) the repetition of “1,0” must occur within the first k^2.

For rigorous proofs and its relation to number theory, see: http://math.stanford.edu/~brianrl/notes/fibonacci.pdf