# 2004 IMO Shortlist Problems/N3

## Problem

(*Mohsen Jamali, Iran*)
A function from the set of positive integers to itself is such that for all the number is divisible by . Prove that for each .

**Comment by the proposer.** A possible version of this question is:

Find all functions such that for all , the number is divisible by .

*This alternative form was also Problem 3 of the 2005 5th Romanian TST, Problem 1 of the 3rd independent study of the 2005 3rd Taiwan TST, and Problem 3 of the 2005 French Mathematical Olympiad, Dossier 4.*

*Note: Although strictly speaking, denotes , in this context it is clear that it means .*

## Solutions

### Solution 1

**Lemma 1.** .

*Proof.* We must have . But for any integer , , so we must have . ∎

**Lemma 2.** For all natural , , with equality only when .

*Proof.* We note that divides . But if , then , a contradiction. Now, if , then we must have ; since , , so we know that . ∎

**Lemma 3.** For any prime , .

*Proof.* We know . Since is positive, either , or . But , so by Lemma 2, . ∎

Now, for any natural number and any natural number that is one less than a prime, we have . But for some integer ,

Hence . This means that has infinitely many divisors, i.e., it is equal to zero. Hence for all natural , .

### Solution 2

We use Lemmata 1–3 of the previous solution.

For natural , we define to be product of all primes less than or equal to .

**Lemma 4.** For all , .

*Proof.* We will use strong induction. We note that , and , and , so . Now, for all integers ,

This establishes our base case. Now, for , suppose that the lemma holds for all integers . By Bertrand's Postulate, there exists a prime greater than and less than or equal to . Thus

.

Thus our lemma holds by strong induction. ∎

We will now prove that for all natural , .

If this is not true, then there is a least for which this is not true.

**Lemma 5.** If exists, then it is not prime.

*Proof.* Suppose the contrary. One of the numbers must be divisible by . But since must divide , none of which can be divisible by , we conclude that and hence . Furthermore, for any prime , cannot be divisible by , since it is a divisor of , which is not divisible by , so . Since , it follows that is the only prime divisor of and again since , , a contradiction. ∎

**Lemma 6.** If exists, then none of the numbers is prime.

*Proof.* Suppose, on the contrary, that is prime, for some integer . We know . But since , we must have , which implies , a contradiction. ∎

We now claim that does not exist. Since neither nor may be prime (by Lemmata 5 and 3), the only possibilities for are 8, 9, 14, and 15. But , , , and are all prime, by Lemma 6, we conclude that . But for each prime less than , one of the numbers

must be divisible by . Since these divide , the only one of these which can be divisible by is , where is the integer between 1 and such that . It follows that for all primes less than ,

By the Chinese Remainder Theorem, then,

But by Lemma 4, the only solutions to this congruence other than are negative numbers (which are clearly impossible), and solutions which imply . But by Lemma 2, this implies , a contradiction. Thus does not exist, so there is no integer such that . Q.E.D.

*Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.*