Problem:
Determine which integers have the property that there exists an infinite sequence of nonzero integers such that the equality
holds for every positive integer .
Solution:
We will show that the sequence exists for all .
For , the sequence cannot exist: If it existed, we would have for all , from which for all by induction. Then would have to be divisible by for all , which is impossible for .
Now fix . We will show that the desired sequence exists. The construction is basically a repeated application of the Chinese Remainder Theorem, but the details require substantial care.
First we prove two lemmas.
Lemma 1 It is possible to partition the positive integers into subsets so that for every positive integer ,
(i) the numbers and are in the same subset, and
(ii) the numbers are all in strictly earlier subsets than .
Proof To show this, define a function from positive integers to positive reals as follows. Let be the set of primes dividing . No element of divides . For any number , write its prime factorization , and then define
Notice that for every positive integer ,
whereas for each ,
Also notice that for each , which implies that for any fixed , there can only be finitely many values of with . The latter fact means that the elements of the image of can be arranged in increasing order, . Now just let for each . The sets are a partition of the positive integers, and (1) and (2) ensure that they satisfy (i) and (ii) respectively.
Lemma 2 Let be relatively prime positive integers and arbitrary integers. Then it is possible to choose nonzero integers such that
Proof We first prove existence of a sequence of integers satisfying (3) for each , by induction on . If , then since are relatively prime, we can find such that . Then, and satisfy (3). Now suppose we have satisfying (3) for . If we choose any integer , and replace each with , then (3) still holds for , and . Since are relatively prime, we can choose so as to make congruent to modulo , and then we take . Then the numbers satisfy (3) for .
This shows that we can find satisfying (3), but they may not all be nonzero. However, once again, we can make the replacements for any integer , and the new sequence still satisfies (3). By an appropriate choice of , we can ensure each is nonzero.
Now both lemmas are proven, and we resume the main proof. We will construct terms of the sequence inductively, but not in the order .
Suppose is any set of positive integers, and we have chosen nonzero integers for each . Say that there is a conflict in if there exists some such that are all in , and
Let be as given by Lemma 1 We will inductively define our sequence as follows:
Step 1: Choose nonzero values for all simultaneously, without creating a conflict in .
Step : Given the values of for chosen at previous steps, choose nonzero integers for all simultaneously, without creating a conflict in .
If we can show that each step of this process can indeed be carried out, then it will eventually define for all positive integers , meeting the required condition
for all (since no conflicts are created).
For step 1 , Lemma 1 implies we can choose arbitrarily for without creating any conflicts, since for all . Now for step , suppose have been assigned already for all . We need to assign for to avoid creating any new conflicts. This just requires that the new assignments satisfy (4) for all integers such that and are in : for any other value , either so no conflict can be created, or else Lemma 1 implies so that the corresponding constraint (4) has been dealt with at an earlier step.
Thus for each such that , we have a constraint
where is determined by the assignments made at previous steps. We just need to show that it is possible to choose for all such that all these constraints are satisfied.
Form a directed graph whose vertices are the elements of , with an edge leading from to whenever both numbers are in . Then every component of this graph is either a single vertex or a (directed) path. We wish to show that nonzero integer values can be assigned to elements of so that for each edge, the corresponding constraint (5) is satisfied. It suffices to show this for each component of the graph. If the component is a single vertex, any nonzero value works. Otherwise, it is a path , and Lemma 2 ensures that we can choose nonzero integer values for so as to satisfy (5) for each edge.
This shows that each step of our constructive process can indeed be performed successfully, and iterating eventually constructs every term of the sequence.
This problem and solution were suggested by Gabriel Carroll.
The problems on this page are the property of the MAA's American Mathematics Competitions