n^2 divides sum of every n consecutive elements

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

n^2 divides sum of every n consecutive elements

G H J

Reveal topic tags

modular arithmetic

number theory proposed

L

G H BBookmark kLocked kLocked NReply

Source: Baltic Way 2006

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1347 posts

WakeUp

#1 h Dec 4, 2010, 7:43 PM • 5 Y

Y by son7, centslordm, HWenslawski, Adventure10, Mango247

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$ ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1343 posts

jgnr

#2 h Dec 5, 2010, 2:14 AM • 4 Y

Y by centslordm, HWenslawski, Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

26 posts

#3 h Jun 2, 2021, 8:50 PM • 1 Y

Y by centslordm

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)$

This post has been edited 2 times. Last edited by TigranCauchy, Jun 2, 2021, 8:53 PM
Reason: typo correction

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a