Indian Statistical Institute B.Math & B.Stat : Number Theory

Let \( a_1,a_2,_3, \dots ,a_n\) be integers. Show that there exists integers $k$ and $r$ such that the sum \[ a_k+a_{k+1}+\dots +a_{k+r} \] is divisible by $n.$ $$$$ We construct a finite sequence of partial sum of the given finite sequence as follows, \[s_1 = a_1\] \[s_2 = a_1+a_2\] \[s_3 = a_1+a_2+a_3\] \[ \dots \] \[s_n = a_1+a_2+ \dots +a_n \] If \( s_i \equiv 0(mod \quad n) \) for any admissible value of $i$ then we are done with \( k= 1 \quad and \quad r= i-1\). Therefore assume \( s_i \not\equiv 0(mod \quad n) \quad \forall \quad i \in \{1,2,\dots,n\} \implies s_i \equiv k(mod \quad n)\) where $1 \leq k \leq n-1, k \in \mathbb{N} .$ Since there are $n$ such congruences and $n-1$ possible values of $k$, $Pigeon-Hole$ principle asserts that at least two different partial sums have the same remainder, i.e, \( s_i \equiv k(mod \quad n) \quad s_j \equiv k(mod \quad n)\) for $i \neq j$. $$$$ Therefore \( s_i \equiv s_j(mod \quad n)\) (Without loss of generality assume that $ i > j $ ) $$$$ \( \implies s_i-s_j \equiv 0(mod \quad n)\) $$$$ \( \implies s_{j+1}+s_{j+2}+\dots +s_{j+i-j} \equiv 0(mod \quad n)\) This is what was asked!