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
,
![$\displaystyle (k^2 + n)^2 = \{[k^2 + f(n]+[n-f(n)]\}^2 = A[k^2 + f(n)] + [n-f(n)]^2$](http://latex.artofproblemsolving.com/0/1/d/01da59a7f55e9aa25e9dd7aec58acaae15736f64.png)
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
![$[f(n_0)]^2+1, \ldots, [f(n_0)]^2 + p$](http://latex.artofproblemsolving.com/6/8/4/684b026415b8a25f8aaba34d9cb1cf3993015881.png)
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
,
![$[f(n_0)]^2 \equiv n_0^2 \pmod{p}$](http://latex.artofproblemsolving.com/a/b/5/ab5ce8d89d0fcd1076a91a4df13974276ff76270.png)
By the Chinese Remainder Theorem, then,
![$[f(n_0)]^2 \equiv n_0^2 \pmod{\varpi(n_0)}$](http://latex.artofproblemsolving.com/a/b/b/abb709d3fda09c05fbef106ae1e063a4d094926f.png)
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.