Maths Olympiad Prep

Track / Stage 8 / 89 of 180 #1789 of 1964

Problem 1789

IMO Shortlist mid-range; USAMO P2/P5
Number theory Difficulty 8.2 Find the answer imo_shortlist

Determine all integers n2 n\geq 2 having the following property: for any integers a1,a2,,ana_1,a_2,\ldots, a_n whose sum is not divisible by nn, there exists an index 1in1 \leq i \leq n such that none of the numbers ai,ai+ai+1,,ai+ai+1++ai+n1a_i,a_i+a_{i+1},\ldots,a_i+a_{i+1}+\ldots+a_{i+n-1} is divisible by nn. Here, we let ai=aina_i=a_{i-n} when i>ni >n.

[i]

A number or a short expression. Spacing and $ signs are ignored.

Official solution

We are tasked with determining all integers n2 n \geq 2 such that for any integers a1,a2,,an a_1, a_2, \ldots, a_n , whose sum is not divisible by n n , there exists an index 1in 1 \leq i \leq n such that none of the numbers

ai,ai+ai+1,,ai+ai+1++ai+n1 a_i, a_i + a_{i+1}, \ldots, a_i + a_{i+1} + \ldots + a_{i+n-1}

is divisible by n n , with the circular definition ai=ain a_i = a_{i-n} when i>n i > n .

To solve this problem, we will utilize properties of numbers and modular arithmetic.

### Step-by-Step Analysis:

1. Total Sum and Modular Arithmetic:

Considering the circular nature and divisibility, note: for each index i i , the complete sum:

Si=ai+ai+1++ai+n1 S_i = a_i + a_{i+1} + \ldots + a_{i+n-1}

If we assume S=a1+a2++ank(modn) S = a_1 + a_2 + \ldots + a_n \equiv k \pmod{n} (where k0 k \neq 0 ), then there must exist at least one index i i such that:

Si≢0(modn) S_i \not\equiv 0 \pmod{n}

2. Condition for Prime Numbers:

If n n is a prime number, then the structure of the cyclic groups and the behavior under modular arithmetic facilitates that no full sum Si S_i may default to a zero residue without contradicting Smodn0 S \mod n \neq 0 per problem condition.

3. Non-Prime Numbers:

Conversely, if n n is composite, there's potential to construct sequences where every partial sum Si0(modn) S_i \equiv 0 \pmod{n} due to factorization properties allowing divisions of full cycles into complete sub-cycles within the sequence subset.

### Conclusion:

Our primary result emerges from contradiction upon assumption, hence: for the described property to hold, the modulus n n must be prime. This way, there exists an index i i that satisfies the n n -cyclic non-divisibility—able to subvert any aligning presence of zero residues across the complete rotation of terms.

Therefore, all integers n2 n \geq 2 with the described property are precisely all prime numbers. The final answer is:
All prime numbers \boxed{\text{All prime numbers}}

Through this reasoning, it is confirmed that all and only prime numbers possess the trait of guaranteed non-zero residues in any set and rotation under restricted modulus sums, in compliance with the reference answer.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.