Let $P(a,b)$ be the assertion: $$f(a) +b| a^2+f(a)f(b)$$Let $p$ be any prime number, $P(p, f(p))$ gives : $$2f(p)|p^2+f(p)f(f(p)) \Longrightarrow f(p)|p^2$$If there exist a prime number $p$ such that $f(p) = 1$ then $P(p, p)$ gives : $$p+1|p^2+1 \Longrightarrow p+1 |2 \Longrightarrow p=1$$And this is a contradiction. If there exist a prime number $p$ such that $f(p) = p^2$ then $P(p, p)$ gives : $$p^2+p|p^2+p^4 \Longrightarrow p+1 |p+p^3 \Longrightarrow p+1 | - 2 \Longrightarrow p=1$$And this is a contradiction. So $f(p) =p$ for every prime number $p$. Now let $p$ a prime number that is large enough and it is doesn't divide $b$. $P(p, b) $ gives : $$p+b| p^2+pf(b) \Longrightarrow p+b| p(p+f(b)) $$Since $gcd(p+b, p) =1$ so : $$p+b | p+f(b) \Longrightarrow p+b | f(b)-b$$Since $p$ is large enough so $f(b) =b $ for every positive integer $b$. $\blacksquare$

Only identity function works, and it clearly does. As usual, let $P(a,b)$ denote the assertion $f(a)+b\mid a^2+f(a)f(b)$. $$P(1,1)\implies f(1)+1\mid f(1)^2+1 \implies f(1)+1\mid 2$$or $f(1)=1$. Now we claim that Claim : For any prime $p>2019$, $f(p)=p$. Proof: First, note that $$P(p,p)\implies f(p)+p\mid p^2+f(p)^2\implies f(p)+p\mid 2p^2$$so $f(p) = p, p^2-p, 2p^2-p$. Thus it suffices to eradicate other two. We do it by note that $$P(p,1)\implies f(p)+1\mid p^2+f(p)\implies f(p)+1\mid p^2-1.$$When $f(p)=p^2-p$ or $2p^2-p$, the above relation is satisfied to only small prime $p$. More concretely, all $p>2019$ never holds. Now fix a positive integer $n$ and take prime $p > 1000\cdot\max\{|f(n)^2-n^2|,2019\}$. Thus $$P(n,p)\implies f(n)+p\mid n^2+pf(n) \implies f(n)+p\mid n^2-f(n)^2$$which forces $f(n)=n$ so we are done.

In fact,we can use Mathematical Induction to prove $$f(x)=x,\forall x\in Z_+$$Let a=b=1,we have $$f(1)+1|f(1)^2+1 \Leftrightarrow f(1)+1|f(1)^2+1-(f(1)+1)(f(1)-1)=2$$so $f(1)+1\leq 2$,because$ f(1)\in Z_+$,so$ f(1)=1$.The proposition is right when x=1. Assume that the proposition is right when$x=x_0$. Let $(a,b)=(x_0,x_0+1)$,we have$$f(x_0)+x_0+1|f(x_0)f(x_0+1)+x_0^2\Leftrightarrow2x_0+1|x_0f(x_0+1)+x_0^2$$Because $(x_0,2x_0+1)=1$,so we can get that$$2x_0+1|f(x_0+1)+x_0......(1)$$Let $(a,b)=(x_0+1,x_0)$,we have$$f(x_0+1)+x_0|f(x_0+1)f(x_0)+(x_0+1)^2\Leftrightarrow f(x_0+1)+x_0|x_0f(x_0+1)+(x_0+1)^2$$so$$ f(x_0+1)+x_0|x_0f(x_0+1)+(x_0+1)^2-x_0(f(x_0+1)+x_0)=2x_0+1......(2)$$By (1)(2),we get that $$2x_0+1=f(x_0+1)+x_0\Leftrightarrow f(x_0+1)=x_0+1$$So the proposition is right when $x=x_0+1$. So $f(x)=x,\forall x\in Z_+$,f(x)=x is all the answer.

See 2016 ISL N6 for more practice with the exact same technique

No one else surprised to see two functional equations questions in the APMO?

@2below agreed. P5 I at least found much easier than usual P5. It's not hard to solve p1 without noticing that we directly have $f(1) = 1$

Another approach : Write the divisibility as $f(a) + b | a^2 - bf(b)$ for all positive integers $a$ and $b$. Plugging in $a = b = 1$ yields $f(1) = 1$. Plugging in $b = 1$ gives $f(a) + 1 | a^2 - 1$ for all $a$. Plugging in $a = 1$ gives $b + 1 | bf(b) - 1$ for all $b$, which in turn implies that $b + 1 | f(b) + 1$ for all $b$. In particular, applying the previous relations for $a = 2$ and $b = 2$ respectively, we get that $3 | f(2) + 1 | 3$, thus $f(2) = 2$. Plugging in $a = 2$ in the initial (rewritten) divisibility, we get that $b + 2 | bf(b) - 4$, for all $b$, which in turn implies that $b + 2 | 2f(b) + 4$, for all $b$. Combined with $b + 1 | f(b) + 1$ for all $b$ and the coprimality of $b + 1$ and $b + 2$, we easily obtain that $\frac{(b+1)(b+2)}{2} | f(b) - b$ for all $b$, so if $f(b)$ differs from $b$ for some $b \geq 3$, we have that $f(b) + 1 \geq \frac{(b+1)(b+2)}{2} + b + 1 > \frac{b^2 - 1}{2}$ and since $f(b) + 1$ divides $b^2 - 1$, we get that $f(b) + 1 = b^2 - 1$, i.e. $f(b) = b^2 - 2$. Since $b + 2 | 2f(b) + 4$, we obtain $b + 2 | 2b^2$, which implies that $b + 2 | 8$, impossible if $b$ isn't equal to $6$. Thus, $f(a) = a$, for all $a$ not equal to $6$. Assuming that $6$ isn't a fixed point of $f$, previous considerations yield $f(6) = 6^2 - 2 = 34$. If we plug in $a = 6$ and $b = 3$ in the initial relation we obtain a contradiction. Hence, $f$ is the identity function, which is obviously a solution to the problem.

p_square wrote: No one else surprised to see two functional equations questions in the APMO? And both are routine

p_square wrote: No one else surprised to see two functional equations questions in the APMO? Can't wait to see how surprised ya'll be when there will be 2 FEs in the IMO. #FE #2FEs@IMO #dangerousliri #FEisTheNewCombi #RIPcombi

rmtf1111 wrote: p_square wrote: No one else surprised to see two functional equations questions in the APMO? Can't wait to see how surprised ya'll be when there will be 2 FEs in the IMO. #FE #2FEs@IMO #dangerousliri #FEisTheNewCombi #RIPcombi I usually don't propose two functionals the only time I did was in IMO 2017 but only the problem it was in the test was accepted the other functional was functional mixed with geometry so there were very different form each other. So don't worry of two functionals in IMO 2019 by me, but I would doubt there will be two functionals in test. Lets wait one more month and will se what is gonna happen hope at least one of my problem to be in test.

A cleaner approach: Plugging $b=f(a)$ we get: $$2f(a)| a^{2} + f^{2}(a) \Longrightarrow f(a)| a^{2}.$$This means that $f(1)| 1 \Longrightarrow f(1)=1.$ Plugging $a=1$ we get $$b + 1| f(b) + 1 \Longrightarrow f(x) \geq x, \forall x\in Z_+$$Plugging $b=1$ we get $$f(a) + 1| a^{2} + f(a)$$but since $f(a)| a^{2}$ we have $a^{2} = f(a)K$, meaning $$f(a) + 1| f(a)(K + 1),$$but since $gcd(f(a), f(a) + 1) = 1$, $$a + 1| f(a) + 1| K +1 \Rightarrow K \geq a,$$implying $$a^{2} = f(a)K \geq af(a) \Longrightarrow f(x) \leq x, \forall x\in Z_+$$This means that the only function is $f(x) = x$, which clearly works.

warning: long

Well deserved for its position APMO 2019 P1 wrote: Let $\mathbb{Z}^+$ be the set of positive integers. Determine all functions $f : \mathbb{Z}^+\to\mathbb{Z}^+$ such that $a^2+f(a)f(b)$ is divisible by $f(a)+b$ for all positive integers $a,b$.

here is a terrible solution The answer is $f(a) \equiv a$. It is easy to see that this solution indeed works. Let $P(a, b)$ denote the assertion. If the problem holds for all $(a, b)$, then it must hold for $(a, a)$. Moreover, it must hold for all $(p,p)$, where $p$ is a prime. From $P(p, p)$, we get $$f(p) + p | p^2 + f(p)^2.$$Now let $f(p) = p + p_i$, where $p_i \in \mathbb{Z}$. This preserves the integer condition. Notice that $$\frac{p^2 + f(p)^2}{f(p) + p} = \frac{2p^2 + 2pp_i + p_i^2}{2p + p_i} \in \mathbb{Z^{+}},$$so $$\frac{2p^2}{2p + p_i} \in \mathbb{Z^{+}}.$$Thus $2p + p_i = 2p, p^2$, or $2p^2$ whence $f(p) = p$, $p^2 - p$, or $2p^2 - p$ for all $p$. The case $f(p) = p$ is easily shown to work for all $p$. We will show that $f(p) = p^2 - p \quad (\Phi)$ and $2p^2 - p \quad (\Delta)$ do not work. Note that $P(1, 1)$ gives $f(1) + 1 | f(1)^2 + 1$ so $f(1) = 1$. $P(p, 1)$ gives $f(p) + 1 | p^2 + f(p) \Rightarrow p^2 - p + 1 | 2p^2 - p \quad (\Phi)$ which clearly does not hold for all $p$ (consider $p = 3$). Similarly, $\Delta$ gives $2p^2 - p + 1 | 3p^2 - p$ which fails at $p = 3$, so $f(p) = p$ is the only one which works. Now suppose we take $c$ sufficiently large such that $p \nmid c$. Now $P(p, c)$ gives $p + c | p^2 + pf(c)$, which forces $f(c) = c$ as desired. $\square$

Does this work? APMO 2019 P1 wrote: Let $\mathbb{Z}^+$ be the set of positive integers. Determine all functions $f : \mathbb{Z}^+\to\mathbb{Z}^+$ such that $a^2+f(a)f(b)$ is divisible by $f(a)+b$ for all positive integers $a,b$. Solution: Let $P(a,b)$ denote assertion: $$\frac{a^2+f(a)f(b)}{f(a)+b} \in \mathbb{Z}$$Then, For $P(1,1)$ $\implies$ $$\frac{1+f(1)^2}{1+f(1)}=\frac{f(1)[1+f(1)] +2 -(f(1)+1)}{1+f(1)} \implies \frac{2}{1+f(1)} \in \mathbb{Z} \implies f(1)=1$$For $P(1,x)$ for all $x \in \mathbb{N} \implies$ $$\frac{1+f(1)f(x)}{f(1)+x} \implies 1+f(x) \geq 1+ ~x \implies \boxed{f(x) \geq x} $$We, now proceed by Induction in $x$. Let $f(x)=x$ for some $x \in \mathbb{N}$, Then, $P(x+1,x) \implies$ $$\frac{(x+1)^2+f(x+1)f(x)}{f(x+1)+x}=\frac{x^2+2x+1+xf(x+1)}{f(x+1)+x}=\frac{2x+1+x[f(x+1)+x]}{f(x+1)+x} \implies \frac{2x+1}{f(x+1)+x} \in \mathbb{Z}$$$$\implies 2x+1 \geq f(x+1)+x \implies x+1 \geq f(x+1) \geq x+1$$Hence, $f(x+1) = x+1$ $\implies$ $\boxed{f(n)=n} ~ \forall n \in \mathbb{N}$ $\qquad \blacksquare$

Here's a non-prime solution... $P(a,a): a+f(a) \mid a^2 +f(a)^2 => a+f(a) \mid 2a^2$. $P(1,1): 1+f(1) \mid 2 =>f(1)=1$. $P(1,b): 1+b \mid 1+f(b) => f(b)=k(b+1)-1$. $P(a,f(a)): 2f(a) \mid a^2+f(a)f(f(a)) => f(a) \mid a^2+f(a) \cdot f(f(a)) =>f(a) \mid a^2$. Substituting $f(a)=k(a+1)-a => k(a+1)-1 \mid a^2 =>k(a+1)-1 \mid ka^2 =>ka+k-1 \mid ka^2-a(ka+k-1) =ak-a => ka+k-1 \mid k+a-1$. Thus $k+a-1 \geq ka+k-1 =>k=1$. Thus $f(a)=a+1-1=a => f(x)=x$ is the only solution.

We induct to show the only such function is $\boxed{f(a) = a}$ for all $a \in \mathbb{Z}^{+}$. This function clearly works; denote the given as $P(a,b)$. For the base case $a = 1$ taking $P(1,1)$ gives$$f(1)^2+1 \equiv 2 \equiv 0 \pmod{f(1)+1}$$hence $f(1)=1$. Now assuming $f(k)=k$, taking $P(k, k+1)$ gives $$k^2+kf(k+1) \equiv k(f(k)+k) \equiv 0 \pmod{2k+1}$$hence $2k+1 \mid f(k+1)+k$ because $\text{gcd}(2k+1,k)=1$. However taking $P(k+1,k)$ gives $$(k+1)^2+kf(k+1) \equiv 2k+1 \equiv 0 \pmod{f(k+1)+k}$$i.e. $f(k+1)+k \mid 2k+1$. So we actually must have $f(k+1)+k=2k+1 \implies f(k+1)=k+1$ as desired.

We claim $f$ is the identity function, which clearly works. Let $P(a,b)$ denote the assertion $f(a)+b \mid a^2+f(a)f(b)$. Note $P(p,p)$ for prime $p$ gives $f(p)+p \mid p^2 + f(p)^2$. Then $f(p)+p\mid p^2+f(p)^2 + (p-f(p))(f(p)+p) = 2p^2$, so $f(p)+p=2p,p^2,2p^2$. Hence $f(p)=p,p^2-p, 2p^2-p$. Now, $P(p,b)$ for prime $p$ and any $b$ gives $f(p)+b\mid p^2+f(p)f(b) - f(b)[f(p)+b]=p^2-bf(b)$. Note that $p^2-bf(b) \not = 0$ for all $b$ by taking sufficiently large $b$. Case 1: $f(p)=p$. Then $p+b\mid p^2-bf(b)$, so $p+b\mid p^2-bf(b)-(p-b)(p+b)=b^2-bf(b)$. Taking sufficiently large $p$ gives a contradiction by size unless $b^2-bf(b)=0$, or $f(b)=b$, for all $b$. Case 2: $f(p) \ge p^2-p$. Then $p^2-bf(b) \ge f(p)+b \ge p^2-p+b$. So $bf(b) \le p-b$. This gives a contradiction for $b\ge p$, so it cannot be true for all $b$. Note: Basically the same as ISL 2016 N6.

had a quick glance at all solutions, and looks like my solution isn't posted yet. So I doubt my solution is correct. Someone please verify.

@above your solution looks correct to me. As for my solution...

Now just wait for someone to prove the Twin Prime Conjecture...

We claim the only solution is the identity. We need for all $a, b$, \begin{align*} f(a) + b &\mid a^2 + f(a)f(b)\\ \iff f(a) + b &\mid a^2 - bf(b) \end{align*}Consider a prime $p$, and note that it is easily shown by taking $(1, 1)$ that $f(1) = 1$. From $(p, p)$ we have, \begin{align*} f(p) + p \mid p^2 - pf(p) \end{align*}Then assume $p \nmid f(p)$ so that, \begin{align*} f(p) + p \mid p - f(p) \end{align*}From size arguments we then find that, \begin{align*} f(p) + p < \left| f(p) - p \right| \end{align*}which can be checked to be impossible. Thus $p \mid f(p)$. Then dividing the divisibility relation by $p$ we have, \begin{align*} \frac{f(p)}{p} + 1 &\mid p - f(p)\\ \iff \frac{f(p)}{p} + 1 &\mid 2p \end{align*}Then we have a couple of cases. First we can have, \begin{align*} \frac{f(p)}{p} + 1 = 1 \iff f(p) = 0 \end{align*}which is a contradiction. Second we may have, \begin{align*} \frac{f(p)}{p} + 1 = 2 \iff f(p) = p \end{align*}which is what we have claimed. Third we may have, \begin{align*} \frac{f(p)}{p} + 1 = p \iff f(p) = p(p-1) \end{align*}This is impossible as taking $f(p, 1)$ would imply, \begin{align*} p^2-p + 1 \mid p^2 - 1\\ \end{align*}However as $2(p^2 - p + 1) > p^2 - 1 \iff p^2 - 2p + 3 > 0$ we find that this is impossible. Finally we may have $f(p) = 2p$. Taking a similar size argument as shown above gives a contradiction. Thus for all primes $p$ we have, \begin{align*} \boxed{f(p) = p} \end{align*}Taking $(a, b) = (p, r)$ with $p \nmid r$ we have, \begin{align*} p + r \mid p^2 - pf(r) \end{align*}Then noting that $\gcd(p + r, p) = 1$ we have, \begin{align*} p + r \mid p + f(r)\\ p + r \mid f(r) - r \end{align*}Taking $p$ extremely large, we force $f(r) = r$ so we are finally done.

SomeonecoolLovesMaths wrote: Anaskudsi wrote: Let $P(a,b)$ be the assertion: $$f(a) +b| a^2+f(a)f(b)$$Let $p$ be any prime number, $P(p, f(p))$ gives : $$2f(p)|p^2+f(p)f(f(p)) \Longrightarrow f(p)|p^2$$If there exist a prime number $p$ such that $f(p) = 1$ then $P(p, p)$ gives : $$p+1|p^2+1 \Longrightarrow p+1 |2 \Longrightarrow p=1$$And this is a contradiction. If there exist a prime number $p$ such that $f(p) = p^2$ then $P(p, p)$ gives : $$p^2+p|p^2+p^4 \Longrightarrow p+1 |p+p^3 \Longrightarrow p+1 | - 2 \Longrightarrow p=1$$And this is a contradiction. So $f(p) =p$ for every prime number $p$. Now let $p$ a prime number that is large enough and it is doesn't divide $b$. $P(p, b) $ gives : $$p+b| p^2+pf(b) \Longrightarrow p+b| p(p+f(b)) $$Since $gcd(p+b, p) =1$ so : $$p+b | p+f(b) \Longrightarrow p+b | f(b)-b$$Since $p$ is large enough so $f(b) =b $ for every positive integer $b$. $\blacksquare$ How did you get $$2f(p)|p^2+f(p)f(f(p)) \Longrightarrow f(p)|p^2$$Since on the LHS it had 2 but the RHS doesn't. If $2x \mid y \implies x \mid y$. So $f(p) \mid p^2 + f(p)f(f(p))$, since $f(p) \mid f(p)f(f(p)) \implies f(p) \mid p^2$.

ATGY wrote: SomeonecoolLovesMaths wrote: Anaskudsi wrote: Let $P(a,b)$ be the assertion: $$f(a) +b| a^2+f(a)f(b)$$Let $p$ be any prime number, $P(p, f(p))$ gives : $$2f(p)|p^2+f(p)f(f(p)) \Longrightarrow f(p)|p^2$$If there exist a prime number $p$ such that $f(p) = 1$ then $P(p, p)$ gives : $$p+1|p^2+1 \Longrightarrow p+1 |2 \Longrightarrow p=1$$And this is a contradiction. If there exist a prime number $p$ such that $f(p) = p^2$ then $P(p, p)$ gives : $$p^2+p|p^2+p^4 \Longrightarrow p+1 |p+p^3 \Longrightarrow p+1 | - 2 \Longrightarrow p=1$$And this is a contradiction. So $f(p) =p$ for every prime number $p$. Now let $p$ a prime number that is large enough and it is doesn't divide $b$. $P(p, b) $ gives : $$p+b| p^2+pf(b) \Longrightarrow p+b| p(p+f(b)) $$Since $gcd(p+b, p) =1$ so : $$p+b | p+f(b) \Longrightarrow p+b | f(b)-b$$Since $p$ is large enough so $f(b) =b $ for every positive integer $b$. $\blacksquare$ How did you get $$2f(p)|p^2+f(p)f(f(p)) \Longrightarrow f(p)|p^2$$Since on the LHS it had 2 but the RHS doesn't. If $2x \mid y \implies x \mid y$. So $f(p) \mid p^2 + f(p)f(f(p))$, since $f(p) \mid f(p)f(f(p)) \implies f(p) \mid p^2$. $f(p)|f(p)f(f(p))$ doesn't mean $2f(p)|f(p)f(f(p))$ or does it?

Hopefully this works.

How did you get \[ \implies f(k+1) + k \mid 2k+1 \]and \[ P(k,k+1) \implies 2k+1 \mid k^2+kf(k+1) \implies 2k+1 \mid k+f(k+1) \]] Basu_Dev wrote: Hopefully this works.

SomeonecoolLovesMaths wrote: How did you get \[ \implies f(k+1) + k \mid 2k+1 \]and \[ P(k,k+1) \implies 2k+1 \mid k^2+kf(k+1) \implies 2k+1 \mid k+f(k+1) \]] Basu_Dev wrote: Hopefully this works.

$P(k+1,k) \implies f(k+1) + f(k) \mid (k+1)^2+f(k)f(k+1) \implies f(k+1)+k \mid (k+1)^2+kf(k+1)-kf(k+1)-k^2 \implies f(k+1)+k \mid 2k+1$ $P(k,k+1) \implies f(k)+k+1 \mid k^2+kf(k+1) \implies 2k+1 \mid k(k+f(k+1)$ but since $gcd(k,2k+1)=1$ we can say $2k+1 \mid k+f(k+1)$

Notice that if $(f(a)+b)|(a^2+f(a)f(b))$ then $(f(a)+b)|(a^2+f(a)f(b)-(f(a)+b)f(b))=a^2-bf(b)$. Then, $(f(1)+1)|(1-f(1))$ so $(f(1)+1)|(1-f(1)+(f(1)+1))=2$ so $f(1)=1$. Then, $(f(2)+1)|(4-1f(1))=3$ so $f(2)=2$. Then, $(f(3)+2)|(9-2f(2))=5$ so $f(3)=3$. Then, $(f(4)+3)|(16-3f(3))=7$ so $f(4)=4$. Assume that $f(x)=x$ for some $x\ge 4$. Notice that $(f(x+1)+x)|((x+1)^2-xf(x))=2x+1$ and the largest possible proper divisor of $2x+1$ is $\frac{2x+1}{3}<x$, so $f(x+1)=x+1$. By induction, the only solution is $\boxed{f(x)=x}$.

We claim that $f(n)=n$ for every positive integer $n$. We are given \[a^2\equiv-f(a)f(b)\equiv bf(b)\pmod{f(a)+b} \ \ (\star)\]Claim: $f$ is injective. Proof. Suppose $f(a_1)=f(a_2)$. Then, $a_1^2\equiv bf(b)\equiv a_2^2\pmod{f(a_1)+b}$. So, $f(a_1)+b$ is a divisor of $a_1^2-a_2^2$. Since we can take $b$ arbitrarily large, $a_1^2-a_2^2=0$ is forced. Hence, $a_1=a_2$, which proves our claim. We now proceed by strong induction on $n$. Note, plugging $a=b=1$ in $(\star)$ gives $f(1)\equiv1\pmod{1+f(1)}$. However, $|f(1)-1|<1+f(1)$, which forces $f(1)=1$. The base case is true. Assume that $f(1)=1,f(2)=2,\ldots,f(b)=b$. Suppose $f(b)=b$ in $(\star)$ and $a=b+1$. Then, $(f(b+1)+b)\mid2b+1$. Since the function is injective, $f(b+1)\notin\{1,2,\ldots,f(b)=b\}$. So, $f(b+1)\geq b+1$. So, $f(b+1)+b\geq2b+1$, but since $(f(b+1)+b)\mid2b+1$, we have that $f(b+1)=b+1$. The induction is complete. $\blacksquare$

plug in 1, we get f(1)+1 | 1+f(1)^2, by Euclidean Algorithm f(1)+1 | 1-f(1), implying f(1)=1. Then plug in a=1 to get that 1+b | 1+f(b), implying f(x)<=x for all x as the RHS >0. By Dirichlet's theorem there exists a positive b such that a^2-bf(a) is (possible negative, nonzero) prime. Let this b be called "x". Then f(a)+x|a^2-xf(a), LHS >1, so f(a)+x=a^2-xf(a) implying f(a)-1 | a^2-f(a). Sub in a=p+1 for p>2. This implies f(p+1)-1 | (p+2)(p), if f is n Note that f(p+1)+1 | (p)(p+2), the max the LHS can be is (p+2) if f(p+1)=p+1. So we have either f(p+1)=p+1 or f(p+1)=p-1, thus f(3)=3. In general we have f(p+1) +- 1 | (p)(p+2), so we get f(4)=4. So right now we have f(1)=1 f(2)=2 f(3)=3 f(4)=4, inductive step: assume f(n)=n sub in a=b, then f(n+1) + n | n^2+2n+1 - n^2, implying f(n+1)+n | 2n+1, and then we win immediately as the left side is bounded >n and 2n+1 is an odd number, getting f(n+1)+n=2n+1 and f(n+1)=n+1. Yay.

Let $P(a,b)$ denote the assertion $f(a)+b \mid a^2+f(a)f(b)$. Let $p$ be any prime. $$P(1,1):\quad f(1)+1 \mid 1+f(1)^2 \implies f(1)+1 \mid f(1)+1 \mid 2 \implies \boxed{f(1)=1}$$$$P(p,p): \quad f(p)+p \mid p^2+f(p)^2 \implies f(p)+p \mid f(p)^2-p^2+2p^2 \implies f(p)+p \mid 2p^2$$$$P(p,f(p)): \quad 2f(p) \mid p^2+f(p)f(f(p)) \implies f(p) \mid p^2$$Therefore, we get three cases: $f(p)=1$ or $f(p)=p$ or $f(p)=p^2$ Case 1: If $\exists p$ such that $f(p)=1$, then $P(p,p) \implies p+1 \mid p^2+1 \implies p+1 \mid 2 \implies p=1$, which is a contradiction! Case 2: If $\exists p$ such that $f(p)=p^2$, then $P(p,p) \implies p+p^2 \mid p^2+p^4 \implies p+1 \mid p^3+p$ $\implies p+1\mid p(p^2+1) \implies p+1 \mid p^2+1 \implies p=1$, contradiction! Therefore, for all primes $p$, $\boxed{f(p)=p}$ $P(p,b): \quad p+b \mid p(p+f(b))$, for all primes $p \implies p+b \mid p+f(b) \implies p+b \mid f(b)-b$ If we choose $p$ to be large enough, we get that the $RHS$ becomes zero, thus $f(b)=b$ for all positive integers $b$. Thus, $\boxed{f(x) \equiv x}$ is the required solution!

Solved with blueberryfaygo_55. We claim the answer is $\boxed{f(n)\equiv n}$. It is easy to check that this works. Let $P(a,b)$ be the given assertion. $P(1,1)$ gives $f(1)+1\mid 1+f(1)^2-(f(1)+1)(f(1)-1)=2$ so $f(1)=1$. Now we apply induction on $n$. Assume the statement for $n=k$. $P(1,k+1)$ gives \[ k+2\mid 1+f(k+1) \]so $f(k+1)\geq k+1$. $P(k+1,k)$ gives \[ f(k+1)+k\mid (k+1)^2+kf(k+1)-k(f(k+1)+k)=2k+1 \]so $f(k+1)\leq k+1$. Thus $f(k+1)=k+1$ so we are done. $\square$

We claim that the only answer if $f(a) = a$ for all $a \in \mathbb{N}$ Let $P(a,b)$ denote the given assertion : Claim 1 : $f(1) = 1$ $P(1,1) \Rightarrow f(1) + 1 \mid 1 + f(1)^2 \Rightarrow f(1) + 1 \mid 2 $ (Since, $f(1) \equiv - 1 \pmod{f(1) + 1}$) $\Rightarrow f(1) + 1 \leq 2 \Rightarrow f(1) = 1$ Claim 2 : $a \leq f(a)$ $P(1,b) \Rightarrow f(1) + b \mid 1 + f(b) \Rightarrow f(1) + b \leq 1 + f(b) \Rightarrow b \leq f(b)$ Claim 3 : $f(a) = a$ We use induction, the case $a = 1$ follows from Claim 1. Suppose that we have$f(n) = n$ for some natural number, then : $P(n+1,n) \Rightarrow f(n+1) + n \mid (n+1)^2 + f(n+1)n$ (Since $f(n) = n$) $\Rightarrow f(n+1) + n \mid (n+1)^2 - n^2$ (Since $f(n+1) \equiv - n \pmod{f(n+1) + n}$) $\Rightarrow f(n+1) \leq (n+1)^2 - n^2 - n = n + 1 \Rightarrow f(n+1) = n + 1$ (Using Claim 2)

I claim that $f$ is the identity over $\mathbb{Z}^{+}$ which can be easily verified. $P(a,a)$ : $f(a)+a | a^{2}+f(a)^{2}$ thus $f(a)+a | 2f(a)a$ thus $gcd(f(a),a)>1$ if $a>1$ and $f(1)=1$. $P(1,b)$ : $1+b | 1 + f(b)$ thus $f(b) \ge b$ $P(p,f(p))$ : $2f(p) | p^{2} + f(p)f(f(p))$ thus $f(p) | p^{2}$ and $p|f(p)$ then $1+p|1+kp$ for $p \ge k$. Thus, $f(p)=p$. $P(a,p)$ : $f(a)+p | a^{2}+f(a)p$ thus $f(a)+p | f(a)^{2}-a^{2}$. Now take $p > f(a)$ thus $f(a)+p | f(a)-a $. Thus, $f(a)=a$ for all positive integers.

Very easy. Looking forward to seeing more problems like this on APMO. We claim that the answer is $f(n)=n$ for all $n\in \mathbb{N}$. It is easy to see that these functions work. Now we shall show that they are the only ones. Let $P(a,b)$ denote the assertion that $f(a)+b \mid a^2 + f(a)f(b)$ for positive integers $a$ and $b$. We start off by finding certain values of $f$. First of all note that from $P(1,1)$ we have \begin{align*} f(1)+1 &\mid 1+f(1)^2\\ f(1)+1 &\mid f(1)^2 -1 \\ f(1)+1 &\mid 2 \end{align*}which implies that $f(1)=1$. Further, $P(1,n)$ gives $n+1 \mid f(n)+1$ so $f(n) \ge n$ for all positive integers $n$. Now, we prove the following claim. Claim : All primes are fixed points of $f$, i.e for all primes $p$, $f(p)=p$. Proof : Consider a prime $p$. From $P(p,p)$ we have, \begin{align*} f(p)+p & \mid p^2 + f(p)^2 \\ f(p) + p & \mid p^2 + pf(p)\\ f(p) + p & \mid pf(p) + f(p)^2\\ f(p)+p & \mid f(p)^2 - p^2\\ f(p) + p &\mid 2p^2 \end{align*}Thus, $f(p)+p$ is a factor of $2p^2$. Since we proved before that $f(n) \ge n$ for all positive integers $n$, it follows that $f(p)+p \ge 2p$ and thus, $f(p)+p \in \{2p,p^2,2p^2\}$. If $f(p)=p^2-2p$ from $P(1,p)$ we have $p+1 \mid f(p)+1$. But then, \[p+1 \mid f(p)+1 = p^2 -p+1 = (p+1)(p-1) -p+2 \implies p+1 \mid p-2\]which is a clear contradiction for all $p>2$. If $p=2$, $f(2)=2^2-2=2$ anyways. Similarly if $f(p)=2p^2-p$ then \[p+1 \mid 2p^2 -p+1 = 2(p+1)(p-1) -p +3 \implies p+1 \mid p-3\]which is a clear contradiction for all $p\ne 3$. But if $f(3)=2\cdot 3^2-3=15$ then $P(3,1)$ implies, $16 \mid 24$ which is a clear contradiction. Thus, for all primes $p$ we must have $f(p)=p$ which finishes the proof of the claim. Now, for each positive integer $n$, consider any prime $q>n$ (thus $\gcd(q,n)=1$). Then from $P(q,n)$ we have \begin{align*} q+n = f(q) + n &\mid q^2 + f(q)f(n)=q^2+qf(n)\\ q+n &\mid q^2 + qn\\ q+n &\mid q(f(n)-n)\\ q+n &\mid f(n)-n \end{align*}Now, since there exists infinitely many primes $q>n$, this implies $f(n)+n$ has infinitely many distinct divisors. Thus, it must be 0 and indeed $f(n)=n$ for all positive integers $n$.

The only answer is $f(x) = x$, which obviously works. Claim: We have $f(1) = 1$. Proof: Taking $P(1,1)$ gives us $f(1) + 1 \mid f(1)^2 + 1$, so $f(1) + 1 \mid f(1) - 1$. It is clear that $f(1) = 1$, as desired. Claim: We have $f(x) \geq x$. Proof: Taking $P(1,x)$ gives us $1+x \mid 1+f(x)$, so the claim follows. Claim: We have $f(x) = x$. Proof: We prove this with induction on $x$. The base case of $1$ has already been proven. For our inductive step, taking $P(x,x-1)$ gives us \begin{align*} f(x) + x-1 & \mid x^2 + (x-1) f(x) \\ \implies f(x) + x-1 & \mid 2x-1. \end{align*}Since we already showed that $f(x) \geq x$, it follows that $f(x) = x$, as desired.