Does there exist a sequence $a_1,a_2,a_3,\ldots $ of positive integers such that the sum of every $n$ consecutive elements is divisible by $n^2$ for every positive integer $n$?
Problem
Source: Baltic Way 2006
Tags: modular arithmetic, induction, number theory proposed, number theory
05.12.2010 04:14
We will construct the sequence inductively. Suppose we already have a sequence $a_1,a_2,\ldots,a_k$ satisfying the given conditions. We prove that there exists a positive integer $a_{k+1}$ such that $a_{k+1}\equiv-a_k\pmod{2^2}$ $a_{k+1}\equiv-a_k-a_{k-1}\pmod{3^2}$ ... $a_{k+1}\equiv-a_k-a_{k-1}-\ldots-a_1\pmod{(k+1)^2}$ We can split each congruence into several congruences in prime modulo. Let $p^m$ be the greatest power of $p$ not exceeding $k+1$. Suppose $a_{k+1}\equiv-a_k-a_{k-1}-\ldots-a_{k-p^m+1}\equiv\pmod{p^m}$. Consider the integer $x\cdot p^y$ where $p\not|x$. Note that $a_{k+1}$ automatically satisfies $a_{k+1}\equiv-a_k-a_{k-1}-\ldots-a_{k-x\cdot p^y+1}\pmod{p^y}$, because the sum of consecutive integers $a_{k-x\cdot p^y+1},\ldots,a_{k-p^m}$ or $a_{k-p^m+1},\ldots,a_{k-x\cdot p^y}$ is divisible by $p^y$ (by the induction hypothesis). So it suffices to satisfy the congruences in prime powers modulo. But Chinese Remainder Theorem guarantees that such a solution exists. So our proof is finished.
02.06.2021 23:50
Recall the following general version of C.R.T ( Chinese Remainder Theorem) Theorem. If $m_1,m_2,...,m_k$ and $a_1,a_2,...,a_k$ are integers such that $\gcd(m_i,m_j)|a_i-a_j$ for all pairs $i,j$, then there exists an integer $n$ congruent to $a_i$ modulo $m_i$ for all $i=1,2,...k$. Now let us get back to the problem. Suppose for some positive integer $n$ we have constructed a sequence $x_1,x_2,...x_n$, which satisfies the requirements for all sums of consecutive terms of length at most $n$. We now try to construct $x_{n+1}$. For this purpose we need to fulfill the congruences $$x_{n+1}\equiv -\sum_{k=n-j}^n x_k(\text{mod}\ (j+2)^2), j=0,1,...n-1$$If we denote $a_j= -\sum_{k=n-j}^n x_k$ and $m_j=(j+2)^2$ for all $j=0,1,...n-1$, we will notice that for $s>l$ the difference $a_s-a_l=\sum_{k=n-s}^{n-l-1}x_k$ is divisible by $(s-l)^2$ by the construction of numbers $x_1,x_2,...x_n$. Consequently, the condition of the aforementioned theorem is satisfied, since $(s-l)^2$ is divisible by $\gcd(s+2,l+2)^2$, which is precisely $\gcd(m_s,m_l)$