Tag Archives: modulo

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<i<p, 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<i<p.

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.

Advertisements

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

table110

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