# 2002 USAMO Problems/Problem 5

## Contents

## Problem

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 ().

## Solutions

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 ).

### Solution 1

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

.

We have

.

But we also have

.

Hence , so , as desired.

### Solution 2

We note that for any integer , , for

It follows that for ,

.

Thus all integers greater than 2 are connected.

### Solution 3

We note that if and only if

.

Therefore for any divisor of , .

Now, for ,

.

Also,

.

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.

### Solution 4

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 .

### Solution 5

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.