Determine all integers satisfying the following property: for all integers whose sum is not divisible by , there exists an index such that none of the numbers
is divisible by (for , we set ).
Determine all integers satisfying the following property: for all integers whose sum is not divisible by , there exists an index such that none of the numbers
is divisible by (for , we set ).
These are exactly the prime numbers!
Indeed, if , we can take and . The sum of the is , which is not divisible by . However, for any , if , then the number is divisible by . If , then the number is divisible by .
Conversely, suppose is prime, and let be integers whose sum is not divisible by . If does not satisfy the property, then for any index , there exists with such that
is divisible by . Furthermore, since the sum of the is not divisible by , we cannot have , so . We then define by induction a sequence of indices by and . We know that for all , the integer
is divisible by ; therefore, by summing, for all indices , the integer
is divisible by . By the pigeonhole principle, there exist such that . The number of terms in the sum (1) is then , which is divisible by , so each of the appears exactly times. Moreover, we know that for all and that , so . The sum (1) is therefore
But and cannot be divisible by , and the sum of the is not divisible by either. Since is prime, the sum (1) is not divisible by , leading to a contradiction.