2004 IMO Shortlist Problems/N3
Contents
[hide]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.