Problem:
Determine all integers with the following property:
For arbitrary, not necessarily distinct integers , whose sum is not divisible by , there exists an index such that none of the numbers
is divisible by . (Here let for .)
Problem:
Determine all integers with the following property:
For arbitrary, not necessarily distinct integers , whose sum is not divisible by , there exists an index such that none of the numbers
is divisible by . (Here let for .)
Solution:
The numbers sought are precisely the primes.
Partial proof 1: No non-prime number satisfies all the conditions.
Let with be a factorization of into two proper divisors. We choose for as well as . Then the sum is obviously not divisible by , since neither factor is divisible by .
Now, for an arbitrary index , we choose the index and obtain . With this counterexample the partial proof is complete.
Partial proof 2: Every prime satisfies all the conditions.
Now let be a prime. For a proof by contradiction we assume that for the numbers , whose sum is not divisible by , there exists for every index a number such that the sum is divisible by . Here we even have , since the sum of all is not divisible by .
Now, for , we construct a finite sequence of integers with (1), by choosing . The starting index is arbitrary, and the new index is chosen to be the smallest possible one after when proceeding cyclically .
By the pigeonhole principle, among this sequence of indices there exist two distinct numbers and with that are congruent . For these we have , since this holds for every bracketed sum.
On the other hand, from it follows that there exists a positive integer with . By (1), , so it follows that . Then cannot be a multiple of , since is prime and neither nor are multiples of — contradiction!