Library / /29 of 120

, 2012

Algebra Difficulty 4.9 AIME Prove it Saudi Arabia

Let $S$ be the set of positive integers. Determine all functions $f: S \to S$ such that $x^2 + f(y)$ divides $f(x)^2 + y$ for every pair of positive integers $x$ and $y$ .

Solution

Consider $x = y = 1$ . Then we get that $\frac{1 + f^2(1)}{1 + f(1)}$ is an integer, so $1 + f(1)$ divides $2f(1)$ . It follows $1 + f(1) = 2$ , that is $f(1) = 1$ .

For $y = 1$ , we obtain $x^2 + 1$ divides $f^2(x) + 1$ . Therefore $x^2 \leq f^2(x)$ , which means that $x \leq f(x)$ for every positive integer $x$ .

For $x = 1$ , we get $1 + f(y)$ divides $1 + y$ , and hence $f(y) \leq y$ , for every positive integer $y$ .

From the above inequalities it follows that the unique function is $f(x) = x$ , $x \in S$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.