Does there exist a sequence a1,a2,a3,… of positive integers such that the sum of every n consecutive elements is divisible by n2 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 a1,a2,…,ak satisfying the given conditions. We prove that there exists a positive integer ak+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-1If 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)