2002 USAMO Problems/Problem 5
Let be integers greater than 2. Prove that there exists a positive integer and a finite sequence of positive integers such that , , and is divisible by for each ().
We may say that two integers and are connected (and write ) if there exists such a sequence of integers as described in the problem. For reference, we note that is an equivalence relation: it is reflexive (), symmetric ( implies ), and transitive ( implies ).
Note that for any divisor of some , , so . It follows that in fact , for any nonnegative integer , and
for any positive integer .
For all integers , there exists some integer such that . Let
But we also have
Hence , so , as desired.
We note that for any integer , , for
It follows that for ,
Thus all integers greater than 2 are connected.
We note that if and only if
Therefore for any divisor of , .
Now, for ,
This means that all positive multiples of 4 are connected.
Furthermore, for ,
which implies that every even number greater than 2 is connected to a multiple of 4.
Finally, for ,
Since is even, this means that all integers greater than or equal to 2 are connected to some even number.
Together, these imply that all integers greater than 2 are connected.
We note that if is a divisor of , then .
We say a positive integer is safe if for all integers , . Note that the product of two safe numbers is also a safe number. Define () to be the smallest divisor of that is greater than 2. We will prove that 2 is safe, by strong induction on . For the case , we have . If , we note that , since must be less than all the divisors of . Thus the inductive hypothesis gives us . Furthermore, we have and , both from our initial note. Thus .
We will now prove that every prime is safe, by strong induction. We have already proven the base case . Now, for odd , is the product of odd primes less than , so is safe. Then we have
Thus the induction is complete, and all primes are safe.
We have now shown that all integers greater than 1 are safe. Specifically, and are safe, and .
Similarly to the first solution, we observe that for any integer and any positive integers ,
We also note that if , then for any positive integer , , for implies .
It is sufficient to prove that for any , . If is composite, then there exist such that , and
If, on the other hand, is prime, then we use strong induction. For the base case, , we note . Now, assuming that and that this holds for all primes less than (we know it holds for all composites), it is sufficient to show that , since is composite and therefore . But since and are both even, it suffices to show that . But this is true, since either composite, or a prime less than , and it is greater than 3, since . Thus the induction is complete.