248 5 Number Theory
703.Prove that there exists no bijectionf:N→Nsuch that
f (mn)=f (m)+f (n)+ 3 f (m)f (n),for allm, n≥1.704.Show that there does not exist a sequence(an)n≥ 1 of positive integers such that
an− 1 ≤(an+ 1 −an)^2 ≤an, for alln≥ 2.705.Determine all functionsf:Z→Zsatisfying
f(x^3 +y^3 +z^3 )=(f (x))^3 +(f (y))^3 +(f (z))^3 , for allx, y, z∈Z.5.1.2 Fermat’s Infinite Descent Principle..........................
Fermat’s infinite descent principle states that there are no strictly decreasing infinite
sequences of positive integers. Alternatively, any decreasing sequence of positive integers
becomes stationary. This is a corollary of the fundamental property of the set of positive
integers that every subset has a smallest element. To better understand this principle, let
us apply it to an easy example.
Example.At each point of integer coordinates in the plane is written a positive integer
number such that each of these numbers is the arithmetic mean of its four neighbors.
Prove that all the numbers are equal.
Solution.The solution is an application of the maximum modulus principle. Forn≥1,
consider the square of side 2ncentered at the origin. Among the numbers covered by it,
the smallest must lie on its perimeter. Let this minimum bem(n). If it is also attained
in the interior of the square, then the four neighbors of that interior point must be equal,
and step by step we show that all numbers inside that square are equal. Hence there are
two possibilities. Eitherm( 1 )>m( 2 )>m( 3 )>···orm(n)=m(n+ 1 )for infinitely
manyn. The former case is impossible, since them(n)’s are positive integers; the latter
case implies that all the numbers are equal.
We find even more spectacular this problem from the 2004 USA Mathematical
Olympiad.
Example.Suppose thata 1 ,...,anare integers whose greatest common divisor is 1. Let
Sbe a set of integers with the following properties:
(i) Fori= 1 ,...,n,ai∈S.
(ii) Fori, j= 1 ,...,n(not necessarily distinct),ai−aj∈S.
(iii) For any integersx, y∈S,ifx+y∈S, thenx−y∈S.