I got a solution from this link. http://www.mathlinks.ro/weblog.php?w=858

But is the solution right? From $ f(p)+f(1)|(p+1)^k$, I don't think we get $ f(p)+f(1)=(p+1)^{r(p)}$...

Official Solution: First we will show that $ f$ is injective. If $ a\neq b$ but $ f(a)=f(b)$, then for each $ n$ we have $ f(a)+f(n)\mid (a+n)^k$ and $ f(a)+f(n)=f(b)+f(n)\mid (b+n)^k$. So $ f(a)+f(n)$ is a common divisor of $ (a+n)^k$ and $ (b+n)^k$. If $ n$ satisfies the condition that $ \gcd(a+n,b+n)=1$ then this can not happen. But $ \gcd(a+n,b+n)=\gcd(a+n,b-a)$ and if $ b-a\neq 0$ there is number $ a+n$ that is relatively prime to it. (for example a very big prime) Now let $ b$ be a natural number. For every $ n$ we have $ f(n)+f(b)\mid (n+b)^k$ and $ f(n)+f(b+1)\mid (n+b+1)^k$. But $ (n+b)$ and $ (n+b+1)$ are relatively prime to each other. So $ 1=\gcd(f(n)+f(b),f(n)+f(b+1))=\gcd(f(n)+f(b),f(b+1)-f(b))$. We want to show that $ f(b+1)-f(b)=\pm1$. If it is not equal to $ \pm1$, then there is a prime $ p$ which divides it. Let $ a$ be such that $ p^a>b$. Now put $ n=p^a-b$. We have $ f(n)+f(b)\mid (n+b)^k=p^{ak}$, so $ p\mid f(n)+f(b)$. We had $ p\mid f(b+1)-f(b)$, so $ p\mid \gcd(f(n)+f(b),f(b+1)-f(b))$ which contradicts the previous arguments. So $ f(b+1)-f(b)=\pm1$ for every number $ b$. But since $ f$ is injective, it is either always equal to $ 1$ or always equal to $ -1$. (Because for two consecutive $ b$'s it cannot change sign) But it cannot always be equal to $ -1$, because $ f$ takes only natural values. So $ f(b+1)-f(b)=1$ for every number $ b$. Hence there is a number $ c$ such that $ f(n)=n+c$. $ c$ is non-negative because $ f(1)=1+c$ is positive. If $ c$ is positive, then take a prime $ p$ greater than $ 2c$. Now $ f(1)+f(p-1)\mid p^k$ which shows that $ p\mid f(1)+f(p-1)=p+2c$. But it's a contradiction because $ 2c<p$. So $ c=0$ and the function is $ f(n)=n$ which obviously satisfies the conditions of the problem statement.

Quote: So $ f(b-1)-f(b)=1$ for every number $ b$ . Hence there is a number $ c$ such that $ f(n)=n+c$ i don't understand how $ f(b-1)-f(b)=1$ can give this function $ f(n)=n+c$.can you please show how?

I think that he used linear recurrence equation

this is amir's solution could anyone contradict Let $m=1, n=p-1$ for a prime $p$ and so, $f(1)+f(p-1)|p\Longrightarrow f(1)+f(p-1)=1, p$ But the range of $f$ is naturals and so, $f(1)+f(p-1) \ge 2 \Longrightarrow f(1)+f(p-1)=p$ $p=2\Longrightarrow f(1)=1\Longrightarrow f(p-1)=p-f(1)=p-1$ So, $f(1)=1, f(2)=f(3-1)=2$ This forms the base case for induction. Now assume for some natural $n, f(n)=n$ Consider $f(n+1)+f(n)|2n+1\Longrightarrow n+f(n+1)|2n+1$ But $(2n+1)\vdots (n+f(n+1)) \ge n+1\Longrightarrow n+f(n+1)=2n+1\Longrightarrow f(n+1)=n+1$ We argue that $n+f(n+1)$ is $2n+1$ because the factor of $2n+1$ greater than $n$ has to be $2n+1$ So, our proof by induction is complete$\Longrightarrow \boxed{f(n)=n\forall n\in \mathbb{N}}$

siddharthanand wrote: this is amir's solution You think so? http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1875340#p1875340 siddharthanand wrote: this is amir's solution could anyone contradict Let $m=1, n=p-1$ for a prime $p$ and so, $f(1)+f(p-1)|p\Longrightarrow f(1)+f(p-1)=1, p$ But the range of $f$ is naturals and so, $f(1)+f(p-1) \ge 2 \Longrightarrow f(1)+f(p-1)=p$ $p=2\Longrightarrow f(1)=1\Longrightarrow f(p-1)=p-f(1)=p-1$ So, $f(1)=1, f(2)=f(3-1)=2$ This forms the base case for induction. Now assume for some natural $n, f(n)=n$ Consider $f(n+1)+f(n)|2n+1\Longrightarrow n+f(n+1)|2n+1$ But $(2n+1)\vdots (n+f(n+1)) \ge n+1\Longrightarrow n+f(n+1)=2n+1\Longrightarrow f(n+1)=n+1$ We argue that $n+f(n+1)$ is $2n+1$ because the factor of $2n+1$ greater than $n$ has to be $2n+1$ So, our proof by induction is complete$\Longrightarrow \boxed{f(n)=n\forall n\in \mathbb{N}}$ And this proof is for a completely different problem. Please read the problems correctly before copying that problem's proof. Or if you are confused, just give that link.

This is a different approach and the solution is really lengthy. The idea is as follows: First establish a strictly increasing sequence $\{a_n\}_{n=1}^{\infty}$ such that $f(a_n) = a_n \;\;\forall n\in\mathbb{N}$. If we have such a sequence in place, then for every $m \in \mathbb{N}\setminus \{a_1, a_2, ... \}$, $f(m) + f(a_n) | (m + a_n)^k \Rightarrow f(m) + a_n | (m + a_n)^k$ $\Rightarrow f(m) + a_n | (m - f(m))^k (\because a|b^k \Rightarrow a|(b-a)^k)$. The quantity $(m - f(m))^k$ is bounded while $f(m) + a_n$ is increasing with $n$ and there exists an $n_0$ such that $f(m) + a_{n_0} > (m - f(m))^k$. Hence, the only way this possible is if $f(m) = m$. Then we would have proved $f(n) = n \; \forall n \in \mathbb{N}$. Now it remains for us to establish a sequence $\{a_n\}_{n=1}^{\infty}$ such that $f(a_n) = a_n \;\;\forall n\in\mathbb{N}$. We choose the following sequence: For $1 \leq n \leq 5, \; a_n = n$ and for $n \geq 6, \; a_n = 2^{n-3}$. We will now establish $f(a_n) = a_n$ by induction. The base cases will run all the way up to $n = 11$. We will establish the base cases in the end. Suppose $f(a_n) = a_n$ for $ 1 \leq n \leq l$ where $l \geq 11$. We want to establish $f(a_{l+1}) = a_{l+1}$. Claim: Suppose $p$ is an odd prime greater than 3 such that $p = 2^a + 1$. Then the only solution to $p^m = 2^n + 1$ is $m = 1, n = a$. Proof of Claim: It is trivial to see that $n \geq a$ and $n = a$ gives us $m = 1$. Suppose $n \geq a+1$. $p \equiv (2^a +1) (\mod 2^{a+1}) \Rightarrow p^2 \equiv (2^a +1)^2 (\mod 2^{a+1})$ $\Rightarrow p^2 \equiv 1 (\mod 2^{a+1})$ Since $n \geq a+1$, $p^m \equiv 1 (\mod 2^{a+1}) \Rightarrow m$ is even (i.e.) $m = 2t$. $\Rightarrow (p^t - 1)(p^t + 1) = 2^n \Rightarrow p^t - 1, p^t + 1$ are both powers of 2 which is not possible since $p > 3$. Hence, the only solution is $m = 1$ and $n = a$. $f(a_{l+1}) + f(a_{l+1}) | (a_{l+1} + a_{l+1} )^k \Rightarrow f(a_{l+1}) | 2^{(l-1)k-1} \Rightarrow f(a_{l+1}) = 2^s $ where $s \geq 0$. $f(a_{l+1}) +f(a_{l-3})|(a_{l+1} + a_{l-3})^k \Rightarrow 2^s + 2^{l-6} | (2^{l-2} + 2^{l-6})^k$ $\Rightarrow 2^s + 2^{l-6} | 2^{(l-6)k}17^k$. $s = l-6$ is a possible value. Suppose $s \neq l-6$. This would imply an odd number of the form $2^n + 1$ divides $2^{(l-6)k}17^k$. Since 17 is a prime number, $2^n + 1 = 17^m$. By the above claim, it follows $n = 4$. Hence, the other possible values of $s$ are $l-2$ and $l-10$. Therefore, $s \in \{l-2, l-6, l-10\}$. (1) $f(a_{l+1}) +f(a_{l-1})|(a_{l+1} + a_{l-1})^k \Rightarrow 2^s + 2^{l-4} | (2^{l-2} + 2^{l-4})^k$ $\Rightarrow 2^s + 2^{l-4} | 2^{(l-4)k}5^k$. $s = l-4$ is a possible value. Suppose $s \neq l-4$. This would imply an odd number of the form $2^n + 1$ divides $2^{(l-4)k}5^k$. Since 5 is a prime number, $2^n + 1 = 5^m$. By the above claim, it follows $n = 2$. Hence, the other possible values of $s$ are $l-2$ and $l-6$. Therefore, $s \in \{l-2, l-4, l-6\}$. (2) $f(a_{l+1}) +f(2^{l-10})|(a_{l+1} + 2^{l-10})^k \Rightarrow 2^s + 2^{l-10} | (2^{l-2} + 2^{l-10})^k$ $\Rightarrow 2^s + 2^{l-10} | 2^{(l-10)k}257^k$. $s = l-10$ is a possible value. Suppose $s \neq l-10$. This would imply an odd number of the form $2^n + 1$ divides $2^{(l-10)k}257^k$. Since 257 is a prime number, $2^n + 1 = 257^m$. By the above claim, it follows $n = 8$. Hence, the other possible values of $s$ are $l-2$ and $l-18$. Therefore, $s \in \{l-2, l-10, l-18\}$. (3) From (1), (2) and (3), it follows that the only value of $s$ that belongs to all three sets is $s = l-2$. Hence, $f(a_{l+1}) = 2^{l-2} = a_{l+1}$. Then, by induction, it would follow that $f(a_n) = a_n \;\;\forall n \in \mathbb{N}$. Now it remains for us to prove that $f(a_n) = a_n$ for $n \leq 11$. (i)First we will establish $f(1) = 1, f(4) = 4, f(16) = 16$ and $f(256) = 256)$. (ii)Then we will show $f(3) = 3, f(2) = 2, f(8) = 8, f(5) = 5$. (iii)Finally, we will show $f(64) = 64, f(128) = 128, f(32) = 32$. (i) $f(1) + f(1) | 2^k \Rightarrow f(1)|2^{k-1} \Rightarrow f(1) = 2^s_0$ where $s_0 \geq 0$. Suppose $s_0 > 0$. This implies $f(1)$ is even. $f(2^a) + f(2^a) | 2^{(a+1)k} \Rightarrow f(2^a) | 2^{(a+1)k-1} \Rightarrow f(2^a) = 2^{s_a}$ where $s_a \geq 0$. $f(1) + f(2^a) | (2^a+1)^k \Rightarrow f(2^a)$ is odd as $f(1)$ is even. This implies $f(2^a) = 1$. Setting $a=1$, we get $f(1) + 1|3^k \Rightarrow f(1) + 1 = 3^{b_1}$ where $b_1 > 0$. Setting $a=2$, we get $f(1) + 1|5^k \Rightarrow f(1) + 1 = 5^{b_2}$ where $b_2 > 0$. This implies $3^{b_1} = 5^{b_2}$ and that is not possible. Hence, $f(1) = 1$. We know that $f(2^a) = 2^{s_a}$ where $s_a \geq 0$. Suppose $p$ is a prime greater than 3 such that $p = 2^a +1$. Then $f(1) + f(2^a) | (1+2^a)^k \Rightarrow 1+2^{s_a}|p^k \Rightarrow 1 + 2^{s_a} = p^m$ where $m > 0$. It follows from the claim of the previous post that, $s_a = a$ (i.e.) $f(2^a) = 2^a$. The number $2^a+1$ is a prime greater than 3 when $a \in \{2,4,8\}$. Hence, $f(2^2) = 2^2, f(2^4) = 2^4, f(2^8) = 2^8$. Therefore, $f(4) = 4, f(16) = 16, f(256) = 256$. (ii) $f(2n-1) + f(4) | (2n+3)^k \Rightarrow f(2n-1) + 4| (2n+3)^k \Rightarrow f(2n-1)$ is odd. $f(3) + f(3) | 6^k \Rightarrow f(3) | 2^{k-1}3^k \Rightarrow f(3) | 3^k$ $\Rightarrow f(3) = 3^s$ where $s \geq 0$. $f(1) + f(3) | 4^k \Rightarrow 1 + 3^s | 4^k \Rightarrow 1 + 3^s = 2^m$ Suppose $s = 0$. Then $m = 1$. Let $s \geq 1$. This would imply that $2^m \equiv 1 (\mod 3)$. This, in turn, implies that $m$ is even (i.e.) $m = 2t$. $\Rightarrow (2^t-1)(2^t+1) = 3^s \Rightarrow 2^t-1, 2^t+1$ are powers of 3. This is is possible only if $t = 1$. Hence, $s = 1, m = 2$. Therefore, $f(3) \in \{1,3\}$. Suppose $f(3) = 1$. $f(3) + f(4)|7^k \Rightarrow 1+4|7^k \Rightarrow 5|7^k$. This is not possible. Hence, $f(3) = 3$. We know that $f(2^a) = 2^{s_a}$ where $s_a \geq 0$. $f(2) + f(1)|3^k \Rightarrow 2^{s_1} + 1|3^k \Rightarrow 2^{s_1} + 1 = 3^m_1$ where $m_1 > 0$. $f(8) + f(1)|9^k \Rightarrow 2^{s_3} + 1|9^k \Rightarrow 2^{s_3} + 1 = 3^m_3$ where $m_3 > 0$. Consider $2^n + 1 = 3^m$ When $n = 1$, $m = 1$. When $n \geq 2$, $3^m \equiv 1(\mod 4) \Rightarrow m$ is even(i.e.) $m = 2t$. $\Rightarrow (3^t-1)(3^t+1) = 2^n \Rightarrow 3^t-1, 3^t+1$ are powers of 2. The only way this is possible is if $t = 1$. Hence, $n = 3, m =2$. This implies $f(2),f(8) \in \{2,8\}$. $f(2) + f(3) |5^k \Rightarrow f(2) + 3|5^k \Rightarrow f(2) = 2 \;(\because f(2) = 8 \Rightarrow 11 | 5^k$ which is a contradiction $)$ $f(8) + f(3) |11^k \Rightarrow f(8) + 3|11^k \Rightarrow f(8) = 8 \;(\because f(8) = 2 \Rightarrow 5 | 11^k$ which is a contradiction $)$ Therefore, $f(2) = 2, f(8) = 8$. $f(5) + f(3) |8^k \Rightarrow f(5) + 3|8^k \Rightarrow f(5) +3 = 2^a$. $f(5) + f(4) |9^k \Rightarrow f(5) + 4|9^k \Rightarrow f(5) +4 = 3^b \Rightarrow 2^a+1 =3^b$. The only solutions to $2^a+1 =3^b$ as observed above are $(a,b) \in\{(1,1),(3,2)\}$. Since $2^a > 3$, $a = 3, b = 2$. This implies $f(5) + 3 = 2^3$. $\Rightarrow f(5) = 5$. (iii) We know that $f(2^a) = 2^{s_a}$ where $s_a \geq 0$. $f(32) + f(5)|37^k \Rightarrow f(32) + 5|37^k \Rightarrow f(32) + 5 = 37^a$ where $a > 0$. This implies $f(32) = 2^{s_5} \geq 32$. $f(32) +f(2) | 34^k \Rightarrow 2^{s_5} + 2|2^k17^k$. Since $f(32) \geq 32$, $s_5 \geq 5$. This would imply an odd number of the form $2^n + 1$ divides $2^{k}17^k$. Since 17 is a prime number, $2^n + 1 = 17^m$. By the above claim, it follows that $n = 4$. Hence, the only possible value of $s_5$ is 5. Therefore, $f(32) = 32$. $f(64) + f(3)|67^k \Rightarrow f(64) + 3|67^k \Rightarrow f(64) + 3 = 67^a$ where $a > 0$. This implies $f(64) = 2^{s_6} \geq 64$. $f(64) +f(4) | 68^k \Rightarrow 2^{s_6} + 4|4^k17^k$. Since $f(64) \geq 64$, $s_6 \geq 6$. This would imply an odd number of the form $2^n + 1$ divides $4^{k}17^k$. Since 17 is a prime number, $2^n + 1 = 17^m$. By the above claim, it follows that $n = 4$. Hence, the only possible value of $s_6$ is 6. Therefore, $f(64) = 64$. $f(128) + f(3)|131^k \Rightarrow f(128) + 3|131^k \Rightarrow f(128) + 3 = 131^a$ where $a > 0$. This implies $f(128) = 2^{s_7} \geq 128$. $f(128) +f(8) | 136^k \Rightarrow 2^{s_7} + 8|8^k17^k$. Since $f(128) \geq 128$, $s_7 \geq 7$. This would imply an odd number of the form $2^n + 1$ divides $8^{k}17^k$. Since 17 is a prime number, $2^n + 1 = 17^m$. By the above claim, it follows $n = 4$. Hence, the only other possible value of $s_7$ is 7. Therefore, $f(128) = 128$. Hence, we have covered all the base cases. Therefore, $f(n) = n \;\;\forall n \in \mathbb{N}$ is the only solution to the problem.

here my solution: First, we will prove that $f(p)=p$ for all prime number $p$. We can find easily $f$ -injective, $f(2)=2^{\alpha} $, $f(4)=2^{\beta} $ and \[ f(p)+f(2)|(p+2)^k, \quad \quad \quad f(p)+f(4)|(p+4)^k \] and $f(p)+f(2)$, $f(p)+f(4)$ are odd for all odd prime $p$. So $f(p)$ is odd for all odd prime $p$, clearly $f(1)=1$. We have $f(q-1)+1=q^k$ and $q|f(q-1)+1$ for all prime $q$. Let $f(p)=p^b$ for a prime number $p$. Suppose that $b>1$. Then there exists prime number $q$ such that q can't divide $p-1$ but $q|f(p)-1$. Hence $q|f(q-1)+f(p)|(q-1+p)^k $ $ \Rightarrow $ $q|p-1$ and a contradiction. $f(p)=p$ for all prime $p$, $f(1)=1$. Second, we will prove that $f(n)=n$ for all $n\in N$. Suppose that there exists prime number $q$ such that $q$ can't divide $f(n)(f(n)-n)$ for $n\in N$. Let $f(n)\equiv -r \pmod{q} $, $(r\not= 0)$, $gcd(r,q)=1$. By Dirichlet's theorem there exists prime number $p$ such that $p\equiv r\pmod{q} $. Then $q|f(n)+p|(n+p)^k $ and $q|f(n)+p$, $q|n+p$ $ \Rightarrow $ it gives us $q|f(n)-n$, a contradiction. Thus $ f(n)(f(n)-n) $ has infinitely many prime divisors. Obviously, $ f(n)=n $ . Answer : $f(n)=n$ for all $n\in N$.

I have a different approach for proving $f(n)=n$ after $f(p)=p$ has been proved, $f(p)=p$ can be proved in mathuz's way, for example. We have, for arbitrary prime $p$, \[f(n)+f(p)|(n+p)^k\]\[\Rightarrow f(n)+p|(n+p)^k\] and thus \[(n-f(n))^k \equiv (n+p)^k \equiv \ 0 \pmod {f(n)+p} \] (as $p\equiv -f(n) \pmod{f(n)+p}$) And thus,\[f(n)+p | (n-f(n))^k\] As $f(n)+p$ is not bounded but $(n-f(n))^k$ is, it directly implies $n-f(n)=0$, and thus $\boxed{f(n)=n \; \forall n \in \mathbb N}$

Comment: This problem is very similar to IMO Shortlist 2004 N3. The main idea is same, finding $f(p-1)$ or $f(p)$ first and then resulting in an unbound divisor dividing $m-f(m)$.

mathuz wrote: here my solution: First, we will prove that $f(p)=p$ for all prime number $p$. We can find easily $f$ -injective, $f(2)=2^{\alpha} $, $f(4)=2^{\beta} $ and \[ f(p)+f(2)|(p+2)^k, \quad \quad \quad f(p)+f(4)|(p+4)^k \] and $f(p)+f(2)$, $f(p)+f(4)$ are odd for all odd prime $p$. So $f(p)$ is odd for all odd prime $p$, clearly $f(1)=1$. We have $f(q-1)+1=q^k$ and $q|f(q-1)+1$ for all prime $q$. Let $\color{red}{f(p)=p^b}$ for a prime number $p$. Suppose that $b>1$. This is wrong. You can't assume this only after proving $f(p)$ odd. You must prove before- 1. $p|f(p)$ 2. No other prime except $p$ divides $f(p)$.

Particle wrote: This is wrong. You can't assume this only after proving $f(p)$ odd. You must prove before- 1. $p|f(p)$ 2. No other prime except $p$ divides $f(p)$. Both of which are more than trivial if you notice that $(f(p)+f(p)) | (p+p)^k$

ghostchungho wrote: Quote: So $ f(b-1)-f(b)=1$ for every number $ b$ . Hence there is a number $ c$ such that $ f(n)=n+c$ i don't understand how $ f(b-1)-f(b)=1$ can give this function $ f(n)=n+c$.can you please show how? Let $f(1) = c+1$ for some $c$. Then, $f(2) = c+2$, etc., trivially. It is easy to now see that $f(n) = n + c$.

I'll nail this FE by applying both Mihăilescu's theorem and Zsigmondy's theorem, and using a needlessly convoluted chain of reasoning. And no, I'm not ashamed of it. Let's agree that $P(m,n)$ means " $P$lug in $m$ and $n$ in the equation" . Step 1: At least one of $f(2)$ and $f(4)$ is an even power of $2$. How come? Well, from $P(2,2)$ and $P(4,4)$, obviously they are powers of two. If they are both $1$, then $P(1,2)$ and $P(1,4)$ imply $f(1)+1$ divides both $3^k$ and $5^k$, so they have a non-trivial common factor, but that's nonsense. Hence the conclusion. $\square$ Step 2: $f(\text{odd})=\text{something odd}$, and $f(\text{even})=\text{something even}.$ How come? Let's say $f(2)$ is a even power of two (the argument is identical in case of $f(4)$). Then $P(2,\text{odd})$ means $\text{something odd}+f(\text{odd})$ divides something odd, so it's odd itself, implying $f(\text{odd})$ is odd. In particular, $f(1)$ is odd. So $P(1,\text{even})$ gives $\text{something odd}+f(\text{even})$ is odd, so $f(\text{even})$ is even. $\square$ Step 3: $f(1)=1,f(2)=2.$ How come? $P(1,1)\implies f(1)|2^k$, but $f(1)$ is odd, so $f(1)=1$. Now the statements $P(2,2)$ and $P(3,3)$ together with Step 2 yield that $f(2)$ and $f(3)$ are powers of $2$ and $3$ respectively. Now $P(1,2)$ means $1+2^a$ is a power of $3$, where $f(2)=2^a$. Then Mihăilescu tells us that $f(2)=2$ or $8$. In the second case, $P(2,3)$ gives $8+3^b=5^c$, for some integers $b,c$. But taking this $\bmod{\;3}$ gives $c$ is odd, whereas $\bmod{\;8}$ implies $c$ is even, contradiction. Thus $f(2)=2$. $\square$ Step 4: $f(p-1)=p-1$ for all primes $p$. How come? This is already established for small $p\in\{2,3\}$, so let's think big. $P(1,p-1)$ says that $1+f(p-1)$ is a power of $p$, so $f(p-1)=p^n-1$ for some $n$. Now $P(2,p-1)$ gives $$2+f(p-1)|(p+1)^k\implies p^n+1|(p+1)^k.$$"But," sayeth Zsigmondy, "this is impossible unless $n$ is precisely $1$." (barring some trivial cases, but we're thinking big anyway) So $f(p-1)=p-1$. $\square$ Step 5: The Reveal, where we finally pull off $f'$s mask. How come? Pick an $x$, any $x$. $P(x,p-1)$ gives $$f(x)+p-1|(x+p-1)^k\implies f(x)+p-1|(x-f(x))^k.$$But unless $x=f(x)$, we can take a really big $\huge{\textit{p}}$ so that the above statement fails to hold. Therefore $\boxed{f(x)=x\;\forall x\in\mathbb N}$, which is indeed a solution. $\blacksquare$

Ankoganit wrote: I'll nail this FE by applying both Mihăilescu's theorem and Zsigmondy's theorem, and using a needlessly convoluted chain of reasoning. And no, I'm not ashamed of it. Let's agree that $P(m,n)$ means " $P$lug in $m$ and $n$ in the equation" . Step 1: At least one of $f(2)$ and $f(4)$ is an even power of $2$. How come? Well, from $P(2,2)$ and $P(4,4)$, obviously they are powers of two. If they are both $1$, then $P(1,2)$ and $P(1,4)$ imply $f(1)+1$ divides both $3^k$ and $5^k$, so they have a non-trivial common factor, but that's nonsense. Hence the conclusion. $\square$ Step 2: $f(\text{odd})=\text{something odd}$, and $f(\text{even})=\text{something even}.$ How come? Let's say $f(2)$ is a even power of two (the argument is identical in case of $f(4)$). Then $P(2,\text{odd})$ means $\text{something odd}+f(\text{odd})$ divides something odd, so it's odd itself, implying $f(\text{odd})$ is odd. In particular, $f(1)$ is odd. So $P(1,\text{even})$ gives $\text{something odd}+f(\text{even})$ is odd, so $f(\text{even})$ is even. $\square$ Step 3: $f(1)=1,f(2)=2.$ How come? $P(1,1)\implies f(1)|2^k$, but $f(1)$ is odd, so $f(1)=1$. Now the statements $P(2,2)$ and $P(3,3)$ together with Step 2 yield that $f(2)$ and $f(3)$ are powers of $2$ and $3$ respectively. Now $P(1,2)$ means $1+2^a$ is a power of $3$, where $f(2)=2^a$. Then Mihăilescu tells us that $f(2)=2$ or $8$. In the second case, $P(2,3)$ gives $8+3^b=5^c$, for some integers $b,c$. But taking this $\bmod{\;3}$ gives $c$ is odd, whereas $\bmod{\;8}$ implies $c$ is even, contradiction. Thus $f(2)=2$. $\square$ Step 4: $f(p-1)=p-1$ for all primes $p$. How come? This is already established for small $p\in\{2,3\}$, so let's think big. $P(1,p-1)$ says that $1+f(p-1)$ is a power of $p$, so $f(p-1)=p^n-1$ for some $n$. Now $P(2,p-1)$ gives $$2+f(p-1)|(p+1)^k\implies p^n+1|(p+1)^k.$$"But," sayeth Zsigmondy, "this is impossible unless $n$ is precisely $1$." (barring some trivial cases, but we're thinking big anyway) So $f(p-1)=p-1$. $\square$ Step 5: The Reveal, where we finally pull off $f'$s mask. How come? Pick an $x$, any $x$. $P(x,p-1)$ gives $$f(x)+p-1|(x+p-1)^k\implies f(x)+p-1|(x-f(x))^k.$$But unless $x=f(x)$, we can take a really big $\huge{\textit{p}}$ so that the above statement fails to hold. Therefore $\boxed{f(x)=x\;\forall x\in\mathbb N}$, which is indeed a solution. $\blacksquare$ your solution is good but this takes $0$ from 7 in iran .because we cant use Mihăilescu's theorem and Zsigmondy's theorem.

That's not OK; $0\not\in \mathbb N$

Iran TST 2008 wrote: $ k$ is a given natural number. Find all functions $ f: \mathbb{N}\rightarrow\mathbb{N}$ such that for each $ m,n\in\mathbb{N}$ the following holds: \[ f(m)+f(n)\mid (m+n)^k\] Answer: only the identity function works. It is clear that it does, so we show that no other function satisfies the given condition, henceforth dubbed as $P(m, n)$. For any prime $p$, $P(p, p) \implies f(p) =2^ap^b$ for some $0 \le a \le k-1$ and $0 \le b \le k$ depending on $p$. Hence to each prime $p$ we associate such a pair $(a, b)$. Note that some pair $(c, d)$ occurs infinitely often by pigeonhole principle. Claim 1. $f(2)$ is even. (Proof) For $p$ prime, notice that $$P(2, p-2) \implies f(p-2)+f(2) \mid p^k.$$Also, $f(2) \mid 2^{2k-1}$ so if $f(2)$ is odd then there exists $\ell>0$ such that $f(p-2)=p^l-1$ with $\ell$ depending on $p$; hence, $$p-1 \mid f(p-2) \mid 2^{k-1}(p-2)^k,$$which is false for $p>2^{2k-1}+1$. $\blacksquare$ By $P(p, 2)$ we conclude $f(p)+f(2) \mid (p+2)^k$ so for $p>2$, we see that $f(p)$ is odd; hence $a=0$ in all cases. For large primes $p, q$; $$p^d+q^d \mid (p+q)^k,$$which is not possible if $d>1$ by Zsigmondy's theorem; so $d \le 1$. Claim 2. $d=1$. (Proof) Otherwise, $d=0$ so $f(p)=1$ for infinitely many primes $p$, so for any prime $q>2^k(p-1)+1$ we obtain $$P(q-p, p) \implies f(q-p)+1 \mid q^k.$$Hence, there exists an integer $r>0$ for which $f(q-p)=q^r-1$ so $$q-1 \mid f(q-p) \mid 2^k(q-p)^k \implies q-1 \mid 2^k(p-1),$$contradicting the size of $q$; establishing the validity of this claim. $\blacksquare$ Finally, fix $m \ge 1$ and a prime $p$ sufficiently large with $f(p)=p$; then we conclude that $$P(m, p) \implies p+f(m) \mid (m+p)^k \implies p+f(m) \mid (m-f(m))^k,$$which yields $f(m)=m$ for all $m \in \mathbb{N}$ just as we desired. $\blacksquare$

I understood Mihaylescu but why you can't use Zsigmondy.(Can we use it in Imo?)

We have $f(1)|2^{k-1} \implies f(1)=2^a , 0\leq a\leq k-1$ Now$$f(1)+f(2)|3^k \implies f(2)=3^b-2^a $$Also $2f(2)|4^k \implies 3^b-2^a|2^{2k-1} $.This gives only a few cases , namely $3$ for $a$ and $b$- CASE I) $b=a=0$.But this means that $f(2)=0 \not \in \mathbb{N}$- CASE II) $b=1,a=1 \implies f(1)=2,f(2)=1$ Then since $f(n)|2^{k-1}n^k$ , we have that for all odd primes , $f(p)=2^xp^y$ , for some $x,y$.Then $$2^xp^y+2|(p+1)^k$$So , for a prime $q$ , $$q|2^{x-1}p^y+1 \implies q|p+1 \implies q|2^{2x-2}-1 $$But we can take sufficiently large $p$ such that all prime factors of $p+1$ do not divide any term among $\{2-1,2^2-1,2^3-1 \cdots 2^{2(k-2)}-1\}$.This gives that for infinitely many $p$ , $x=0, f(p)=p^y$.But then $$p^y+2 |(p+1)^k $$which gives a contradiction because $$q|p^y+2 \implies p\equiv -1 \pmod{q} \implies q|3$$which is NOT necessary. CASE III) $b=1,a=0 \implies f(1)=1,f(2)=2$. Then $$2^xp^y +1|(p+1)^k ,,q|2^xp^y+1 \implies p\equiv -1 \pmod{q} \implies q|p^{2x}-1 $$Again take sufficiently large $p$ such that no prime factors of $(p+1)$ divide any of $\{2-1,2^2-1,2^3-1 \cdots 2^{2k}-1\}$.This gives that for infinitely many $p$ , $f(p)=p^y$.Then $$p^y+1|(p+1)^k \implies y=1 $$becuase of Zsig.So , for infinitely many $p$ , $f(p)=p$.Then $$q|f(n)+p \implies q|n+p \implies q|f(n)-n \implies f(n)=n)$$by considering the set $\{f(n)+p\}$ varying $p$.