Problem:
Suppose are integers whose greatest common divisor is 1 . Let be a set of integers with the following properties.
a. For .
b. For (not necessarily distinct), .
c. For any integers , if , then .
Prove that must be equal to the set of all integers.
Solution:
We may as well assume that none of the is equal to 0 . We start with the following observations.
d. by (b).
e. whenever , by (a) and (d).
f. If and , then by (b) and (e).
By (f) plus strong induction on , we have that for any whenever .
By (d) and (e), the same holds even if , and so we have the following.
g. For contains all multiples of .
We next verify that
h. For and any integers .
We do this by induction on . If and , this follows from (b), (d), (f), so we may assume that
Suppose without loss of generality (by switching with and/or negating both and ) that ; then
and we have by the induction hypothesis, and again by the induction hypothesis. So by (f), and (h) is verified.
Let be the largest integer such that divides ; without loss of generality we may assume that . Let be the greatest common divisor of . We prove by induction on that contains all multiples of for ; the case is the desired result. Our base cases are and , which follow from (g) and (h), respectively.
Assume that contains all multiples of , for some . Let be the set of integers such that is divisible by and for all integers . Then contains nonzero positive and negative numbers, namely any multiple of by (h). By (c), if and divisible by (so in ) satisfy , then . By taking , we deduce that ; by induction (as in the proof of ), we have for any integer (positive, negative or zero).
From the way we ordered the , we see that the highest power of 2 dividing is greater than or equal to the highest power of 2 dividing . In other words, is odd. We can thus find integers with even such that . (Choose such a pair without any restriction on , and replace with if needed to get an even .) Then for any integer , we have and so . This completes the induction and the proof of the desired result.
Problem originally by Kiran Kedlaya.
The problems on this page are the property of the MAA's American Mathematics Competitions