All congruences below are taken $ \bmod p$. Let $ a$ be the smallest integer such that $ f(a) = 0$. Then $ f(ka) = 0 \forall k \in \mathbb{N}$. If $ b$ exists not of this form such that $ f(b) = 0$, then $ f(a) \equiv 0 \Leftrightarrow f(b) + f(a - b) \equiv 0 \Leftrightarrow f(a - b) \equiv 0$ (in other words, we can apply the Euclidean algorithm (or in other other words, $ \mathbb{Z}$ is a PID); contradiction. Hence $ f(n) \equiv 0 \Leftrightarrow \exists k \in \mathbb{N} : n = ka$. On the other hand, clearly $ f(kp) = 0 \forall k \in \mathbb{N}$. It follows that $ a | p$. If $ a = 1$ then $ f$ can't be surjective, so $ a = p$. It now follows that if $ m \equiv - n$ then $ f(m) \equiv - f(pk + n) \forall k \in \mathbb{N} \implies f(m) \equiv f(pk + m) \forall k \in \mathbb{N}$. The residues $ f(m), m = 1, 2, 3, ... \frac {p - 1}{2}$ (for odd $ p$) determine all the others. In order for $ f$ to be surjective, the residues $ f(n), n = 1, 2, 3, ... p - 1$ must be precisely the nonzero residues $ \bmod p$, so the residues $ f(m), m = 1, 2, 3, ... \frac {p - 1}{2}$ are any subset of those residues with no additive inverses (in other words, we pair up each residue with its additive inverse and take only one element of each pair), so there are $ 2^{\frac {p - 1}{2} }$ ways of assigning these pairs (for odd $ p$). When $ p = 2$, $ f(m) \equiv m$. This and the surjective condition are the only conditions on $ f$. In other words, the values of $ f$ in a particular residue class are an arbitrary permutation of the natural numbers in that residues class. For example, when $ p = 2$ the odd values of $ f$ are a permutation of the odd naturals and the even values of $ f$ are a permutation of the even naturals. Edit: My apologies. I thought $ p$ was fixed.

Thank you for notification of my name, but My exact name is : Mohsen Jamaali!

orl wrote: Find all surjective functions $ f: \mathbb{N} \mapsto \mathbb{N}$ such that for every $ m,n \in \mathbb{N}$ and every prime $ p,$ the number $ f(m + n)$ is divisible by $ p$ if and only if $ f(m) + f(n)$ is divisible by $ p.$ Author: Mohsen Jamaali and Nima Ahmadi Pour Anari, Iran we suppose that $ \boxed{n>m,f(n)=f(m)}$ $ \forall x\in\mathbb{N}: \ p|f(x+n)\iff p|f(x)+f(n)\iff p|f(x)+f(m)\iff p|f(x+m)$ then $ f(x+m)$ and $ f(x+n)$ have same pimes divisor then $ \forall X\ge max(n,m): \ X\equiv r(mod\ n-m),r\in\{1,...,n-m\}$: $ f(X),f(r)$ have same primes divisors. $ f$ surjective ===> $ \exists M\ge max(n,m): \ f(M)$ is a prime $ >max(f(1),f(2),....,f(n-m))$ but $ f(M)$ have same primes divisor of an element of $ \{f(1),f(2),...,f(n-m)\}$ (impossible) then we must have $ \boxed{n=m}$ $ f$ is bijective.so we can take $ g=f^{-1}$ NOW we have $ p|n+m\iff p|f(g(n)+g(m))$ i continue after

Hopefully, the following works:

First let's prove that $ f(1) = 1$. Assume there exists such prime $ p$ that $ p|f(1)$. Using induction and condition it follows that $ p|f(n)$, for any $ n$, contradicting the fact that that $ f$ is surjective. So, $ f(1) = 1$. Take any prime $ p$. If $ a$ is minimal such that $ p|f(a)$, than if $ p|f(b)$, we have $ a|b$, because otherwise $ p|f(b - a),f(b - 2a),...,f(b - ka)$, where $ ka < b < (k + 1)a$ and $ b - ka < a$, contradicting the assumption. If the numbers $ f(a + 1)$ and $ f(a)$ have same prime divisor $ p$, than taking the smallest $ m$ for which $ p|f(m)$ we get $ m|a,(a + 1)$, implying $ m = 1$, but $ p$ can't divide number $ f(1) = 1$. Hence, for any positive integer $ a$, $ g.c.d.(f(a),f(a + 1)) = 1$. $ (1)$ Let's prove that $ |f(a + 1) - f(a)| = 1$, for all positive integers $ a$. Assume contrary that there exist $ a$ and prime $ p$ with $ p|(f(a + 1) - f(a))$. Take $ b$ such that $ f(a) + f(b)$ is divisible by $ p$ (Such a number$ b$ exists because of the surjectivity of $ f$.). Than, $ f(a + 1) + f(b)$ is also divisible by $ p$ and using the condition of the problem, we deduce: $ p|f(a + b + 1),f(a + b)$, which is obviously contradiction. (Because of $ (1)$.) So, $ |f(a + 1) - f(a)| = 1$ (2) As $ f(1) = 1$, we have $ f(2) = 2$. So, $ 3|((f(1) + f(2))$, which means that $ 3|f(3)$, but $ f(3) = 1$ or $ f(3) = 3$. So, $ f(3) = 3$. $ f(1) + f(4) = 5$ is divisible by $ 5$, so $ 5|f(5)$, but $ f(5)\leq f(4) + 1 \leq f(3) + 2 = 5$. So, $ f(5) = 5$ and $ f(4) = 4$. Now use induction to prove that $ f(n) = n$ holds for any $ n$. Assume it's true for all $ k \leq n$ (Where $ n \geq 5$). Assume contrary that $ f(n + 1) = n - 1 = f(n - 1)$. Than, if $ p|n - 1$, there exists $ a > 1$ with $ a|(n - 1),(n + 1)$. So, $ a = 2$. It means $ p|f(2) = 2$, implying $ n - 1 = 2^{k}$, for some positive integer $ k$. Than, $ f(n + 2) = n - 2 = f(n - 2)$ or $ f(n + 2) = n = f(n)$. if $ f(n + 2) = n - 2 = f(n - 2)$, than for any prime divisor $ p$ of $ n - 2$, there exist $ a > 1$ with $ a|(n - 2),(n + 2)$, implying $ a = 1,2 or 4$. It means again $ p = 2$ and $ 2^{k} - 1 = n - 2 = 2^{m}$, which is clearly impossible. For the second case, we analogously deduce $ n = 2^{m}$, but $ n = 2^{k} - 1$. This contradiction shows that $ f(n + 1) = n + 1$, which means $ f(n) = n$, for all $ n$, which is clearly solution. Lasha Lakirbaia

If this solution is correct, then the condition that $ f$ is surjective can in fact be replaced with $ f(1) = 1$.

i think for any prime p and numbers a and b , p|f(a)-f(b) if and only if p|a-b... In fact , consider natural number c so that p|a+c , then p| f(a+c) .Indeed p|f(a)+f(c) , so p|f(b)+f(c) . thus p|f(b+c) so p|b+c. indeed p|a-b. now if p|a-b then coose c such that p|a+c . So p|f(a+c) . Then p|f(a)+f(c) . and p|b+c then p|f(b)+f(c) . Indeed p|f(a)-f(b) . Thus |f(a)-f(a-1)|=1 since a-(a-1)=1 . |f(a)-f(a-2)|=2^k since a-(a-2)=2. so we can see f(a) and f(a-2) are different . thus we can see f(n)=n easily . here is , i proved f(1)=1 at first...

(Due to me & mahi)

Easy to prove that $f(1)=1$. Let $k$ be the smalles t integer s.t $p$ divides $f(k)$ It's easy to prove by induction tha if $p$ divides $f(a)$,then $p$ divides $f(ma)$ So $p$ divides $f(kx)$ for all $x$ Let $p$ divides $f(y)$ and $y=kq+r$ where $r<p$ Then $p$ divides $f(kq)+f(r)$ so $p$divides $f(r)$.But $r<p$.So $r=0$ and $pk$ divides $y$ So $p$ divides $f(y)$ iff $k$ divides $y$ Let $x\equiv s (mod k)$ and $x=kq+s$ Then $p$ divides $f(s)+f(k-s)$.As $k$ divides $x+k-s$,$p$ divides $f(x+k-s)$. So $p$ divides $f(x)+f(k-s)$.this implies $p$ divides $f(x)-f(s)$ Let $p$ divides $f(x)-f(y)$ for some $x,y$ and $y\equiv s $(mod $k$).Then $f(y)\equiv -f(k-s)$ (mod $p$) So $p$ divides $f(x)+f(k-s)$.this implies $p$ divides $f(x+k-s)$ So $k$ divides $x+k-s$ $p$ divides $x-y$ So $p$ divides $f(x)-f(y)$ Simillarly we can prove if $p$ divides $f(x-y)$ then $p$ divides $f(x)-f(y)$ So $f(x-y)$ and $f(x)-f(y)$ have the same prime divisors . Let $x=y+1$.Then $f(1)$ and $f(y+1)-f(y)$ have the same prime divisors But $f(1)=1$.So we must have $f(y+1)-f(y)=1$ This implies $f(x)=x$ for all $x$.

AnonymousBunny wrote:

Claim 2: $f(x) = f(y) \iff x=y$ Proof: The if direction is trivial. We shall show the only if direction. Suppose $f(x)=f(y)$ for some $x \neq y.$ WLOG $y>x.$ Note that $p \mid f(y) \iff p \mid f(x) + f(y-x),$ so $p \mid f(y-x).$ Then, $p \mid f(y-x),$ so $p \mid f(k(y-x))$ for all $k \in \mathbb{N}.$ Now, for all $n,$ there exists a $q$ and $r$ such that $n= q(y-x)+r,$ where $r \leq y-x.$ It follows that $p \mid f(n) \iff p \mid f(r).$ Thus, the set of all prime divisors of $f(n)$ is equal to the set of all prime divisors of $\{f(1), f(2), \cdots , f(y-x)\},$ which contradicts the surjectivity of $x.$ $\blacksquare$

Your proof of Claim 2 is wrong.You have proved that $f(x)=f(y) \Rightarrow x=y$ for only those $x$ and $y$ for which we know that $f(x)$ is divisible by $p$,which is a strong assumption. Otherwise I think the proof is fine.

Yes I see. That's not how I was thinking though, I completely messed up while writing the solution. I hope it's correct now. Thanks for pointing it out!

My solution may be similar to others: Exactly as the above argument show that $f(1)=1$.Now suppose $f(x)=f(y)$ for some $x>y$.Fix a prime $p$.By surjectivity there exists $m$ such that $p|f(x+m)$.Then $p|f(x)+f(m)=f(y)+f(m) \implies p|f(y+m)$.We also have $p|f(x+m) \implies p|f(x-y)+f(y+m) \implies p|f(x-y)$.This happens for infinitely many primes $p$,forcing $f(x-y)=0$ which is an impossibility.Thus the function $f$ is one-one,and consequently with the problem statement,bijective on $\mathbb{N}$. Lemma:If $d$ is the minimal positive integer such that $p|f(d)$,then $p|f(m) \Leftrightarrow d|m$.Further $f(x) \equiv f(y) \pmod{p} \Leftrightarrow x \equiv y\pmod{d}$. Proof:Let $m=dk+r$ where $0 \le r <d$.Then $p|f(d) \implies p|f(dk)$ by easy induction.Thus $p|f(m) \implies p|f(dk+r) \implies p|f(kd)+f(r) \implies p|f(r)$,This is a contradiction unless $r=0$ by the choice of $d$.Proving the other side is trivial. For the second claim let $x>y$.Then $p|f(x)-f(y) \implies p|f(x-y) \implies d|x-y$ as desired,Once again the other side is trivial to see. Thus $f(1),f(2),\cdots,f(d)$ are incongruent modulo $d$,which means $d \le p$.If $d<p$ then some integer modulo $d$ will not occur in the range of $f$,contradicting bijectivity.Thus $d=p$.This together with the lemma yeilds that $f(x) \equiv f(y)\pmod{p} \Leftrightarrow x \equiv y\pmod{p}$. Now lets induct to show that $f(n)=n \forall n \in \mathbb{N}$.The base case is already settled.Let this be true for all integers upto $n$.If any prime $p$ divides $f(n+1)-n$ then we would have $p|f(n+1)-f(n) \implies p|1$ by the lemma,which is absurd.We also see that $f(n+1) \ge n+1$ due to bijectivity.Thus $f(n+1)-n=1$ or $f(n+1)=n+1$,completing the induction step and the proof.

Suppose $p | f(1)$ with $p$ prime, then by induction $ p | f(n)$ for all $n$, contradiction to surjectivity. Then $f(1)=1$. Let $p$ be a prime and assume $f(a)=p$. Then $p | f(n) \Leftrightarrow p | f(n-a)$, so the condition $p | f(n)$ depends only on the congruence of $n$ mod $a$. Let $S$ be a set in $\mathbb{Z}_a$ such that $p | f(m) \Leftrightarrow m \in S$ for $1 \le m \le a$. If $a,b \in S$ then $p | f(a)+f(b)$ and so $p | f(a+b)$ and so $a+b \in S$, and therefore $S$ is additive.

But 1 is not in $S$, and therefore $M_p := gcd(a_1,...,a_k,a) > 1$. From this, $S$ is the set of multiples of $M_p$. We get $p | f(n) \Leftrightarrow M_p | n$. Assume $a = b$ (mod $M_p$), then if $c=-a$ (mod $M_p$), we get that $p | f(a)+f(c), f(b)+f(c)$ and so $f(a)=f(b)$ (mod $p$). Also, if $f(a)=f(b)$ (mod $p$), then by surjectivity we can take $f(c)=-f(a)$ (mod $p$) and then $M_p | a+c, b+c$ and so $a=b$ (mod $M_p$). Therefore, $a=b$ (mod $M_p$) $\Leftrightarrow f(a)=f(b)$ (mod $p$). Notice that every congruence mod $p$ is achieved by $f$ (by surjectivity). Therefore, we have an equivalence relation between $\mathbb{Z}_p$ and $\mathbb{Z}_{M_p}$, and therefore, $p=M_p$. We get that $\boxed{p | n \Leftrightarrow p | f(n)}$ and $\boxed{p | a-b \Leftrightarrow p | f(a)-f(b)}$ for all primes $p$. Let the second statement be $\pi$. Assume $f$ is not the identity, and let $n$ be the smallest number such that $f(n) \neq n$. Clearly $n>1$. Now, $f(n-1)=n-1$ by our assumption. Therefore, using $\pi$, we get $p | 1 = n-(n-1) \Leftrightarrow p | f(n)-f(n-1) = f(n)-(n-1)$ and therefore no prime divides $f(n)-(n-1)$. Hence, $f(n)-(n-1)=1$ and so $f(n)=n$. Contradiction! So our assumption was wrong and $f$ is indeed the identity function.

My solution : Suppose that a function $ f $ satisfies the condition. For the moment, if we ignore the condition of surgectivity, then $ g(x) = f(x) - x $ is a function satisfying the condition too. Similarly, we can form a sequence of (decreasing) functions $ f(x), g(x), ..... $ satisfying the given condition. It is easy to see that $ j(x) = 0 $ must appear in this sequence, implying that $ f(x) = ax $ for some constant a. Now, suppose that a prime p divides $ f(1) $, i.e $ p $ divides a. Then $ p $ divides $ f(y) $ for every natural number $ y $. Contradiction ! Hence $ a = 1 $. And so $ f(x) = x $ and $ f(x) = 0 $ (Yes! This is a solution! ) are all the solutions.

nice

My solution: The only such functions are $f(n)=n, \forall n \in \mathbb{N}$ Indeed, it is obvious that these work. We prove that these are the only valid functions. Claim 1. $f(1)=1$ Proof:- By surjectivity, let us assume that $f(k)=1$ for some $k>1$. Now, note that $f(k-1)+f(1) \ge 2$ so there exists a prime $p$ such that $p \mid f(k-1)+f(1)$. This means that $p \mid f(k)=1$ which is a cntradiction. Thus, $f(1)=1$. Claim 2. $\gcd(f(n+1),f(n))=1$ for all $n$. Proof:- Notice that if $p$ is a prime and $p \mid f(n+1)$ and $p \mid f(n)$ implies that $p \mid f(1)=1$ which is a contradiction. Claim 3. $f$ is an injective function. Combined with our assumption, $f$ is a bijection. Proof:- Let $a<b$ and $f(a)=f(b)=c$. Then, clearly, by surjectivity, for any prime number $p$, there exists $m$ such that $p \mid f(m)+c$. Now, our hypothesis means that $p \mid f(m+a)$ and $p \mid f(m+b)$ and thus, $p \mid f(b-a)$ and since this holds for all primes $p$, we have $f(b-a)=0$. But, $0$ is not an element of the range of function $f$. Contradiction. Thus, $f$ is injective. Claim 4. $f(n+1)=f(n)+1$ or $f(n+1)=f(n)-1$ for all $n \in \mathbb{N}$ Proof:- Indeed, let us suppose that the absolute value of the difference between $f(n+1)$ and $f(n)$ is larger than $1$. So, let $p \mid (f(n+1)-f(n))$ be a prime number. Choose an integer $m>0$ such that $p \mid f(m)+f(n)$ (such numbers exist because of surjectivity) Then, we get that $p \mid f(m)+f(n)$ and so $p \mid f(m+n)$. Also, by our definition, since $f(n+1) \equiv f(n) \bmod p$ we have $p \mid f(m)+f(n+1)$ and so $p \mid f(m+n+1)$. Therefore, $p \mid f(m+n)+f(1)$ and clearly, $p \mid f(1)=1$ which is quite impossible. This proves our claim. End game:- We now claim that $f(n)=n$ for all $n>0$. Proof:- Indeed, we see that $f(n+1) \in \{f(n)-1,f(n)+1\}$ and since $f$ is injective, this MUST hold for all $n$ in the same fashion. This gives that $f(n)=n+c$ or $f(n)=-n+c$ for some constant $c$. The latter cannot be a solution and putting $n=1$ in the former, we get that the only solution is $f(n)=n, \forall n \in \mathbb{N}$ This is indeed, trivial to check as stated earlier, and so, the problem is dead! Any question? No... Thus, we conclude, with a 7/7 yay! Remark:- A very elegant problem! But perhaps too easy for an N5. Certainly took some time and tricks... Iran be to pro at making nice NT.

Wow my solution sucks. We claim $f\equiv\mathrm{id}$. It is clear that this works, so we'll now show that it's the only function that works. So suppose $f$ is a function satisfying the FE. Let $P(n)$ be the set of prime factors of $n$. The FE is equivalent to $P(f(m+n))=P(f(m)+f(n))$. Claim 1: $f(x)=1\iff x=1$. Proof of Claim 1: Suppose $f(x)=1$. If $x\ge 2$, then there are $m,n\in\mathbb{N}$ such that $x=m+n$, so \[P(f(x))=P(f(m)+f(n)).\]Since $f(m),f(n)\in\mathbb{N}$, we have $f(m)+f(n)\ge 2$, so the right side is nonempty, while the left side is evidently empty. This is a contradiction so $x=1$. Thus, $f(x)=1\implies x=1$, and now since $f$ is suejective, we have $f(1)=1$ as well. $\blacksquare$ There's one more claim we'll be using repeatedly. Claim 2: For all $k\in\mathbb{N}$, there is some $\ell\in\mathbb{N}$ such that $f(2^k)=2^\ell$. Proof of Claim 2: We see that \[P(f(2^k))=P(2f(2^{k-1})=\{2\}\cup P(f^(2^{k-1})),\]so by induction, $P(f(2^k))=\{2\}\cup P(1)=\{2\}$, as desired. $\blacksquare$ Claim 3: $f(3)=3$ and $f(2)=2$. Proof of Claim 3: We have \[\{2\}=P(f(4))=P(f(1)+f(3)),\]so $f(3)=2^\ell-1$ for some $\ell\ge 2$ (the inequality is so that $f(3)>1$ in accordance with claim 1). Now, \[P(f(3))=P(f(1)+f(2)),\]so letting $f(2)=2^k$ with $k\ge 1$, we have \[P(2^\ell-1)=P(2^k+1).\]The bulk of the proof of Claim 3 will be solving the above equation in $k,\ell$. Note that $3\in P(2^\ell-1)$ if and only if $\ell$ is even, and $3\in P(2^k+1)$ if and only if $k$ is odd. Thus, we need $k$ and $\ell$ to have opposite parities. Now, we see that $\gcd(2^k-1,2^k+1)=1$, so \[\gcd(2^\ell-1,2^k+1)=\frac{\gcd(2^\ell-1,2^{2k}-1)}{\gcd(2^\ell-1,2^k-1)}=\frac{2^{\gcd(2k,\ell)}-1}{2^{\gcd(k,\ell)}-1}.\]If $\ell$ is odd, then this quantity is $1$, which can't be as $2^\ell-1$ and $2^k+1$ have the same set of prime factors, and are both bigger than $1$. Thus, $\ell=2r$ is even, so \[\gcd(2^\ell-1,2^k+1)=2^{\gcd(k,r)}+1.\]Therefore, we have \[P(2^{\gcd(k,r)}+1)=P(2^\ell-1)=P((2^r-1)(2^r+1)).\]We have a couple of cases now. Case 1: $r\mid k$ We get that $P(2^r+1)=P((2^r-1)(2^r+1))$, but since $\gcd(2^r-1,2^r+1)$, we must have $r=1$, so $\ell=2$, so $f(3)=3$. Thus, \[P(2^k+1)=P(3)=\{3\},\]so $2^k+1=3^a$ for some $a$, so $3^a-2^k=1$. By Mihailescu, we see that the only solutions are $a=1$ and $k=1$, or $a=2$ and $k=3$. The former solution leads to $f(2)=2$, so WLOG suppose $f(2)=8$. So $f(2)\in\{2,8\}$. Case 2: $r\nmid k$ We have that $\gcd(k,r)$ is an odd divisor of $r$ not equal to $r$. If $r$ is even, then $2\gcd(k,r)\mid r$, so \[2^{2\gcd(k,r)}-1\mid 2^r-1.\]But $2^r-1$ shares no common factors with $2^r+1$, so $2^{\gcd(k,r)}+1$ shares no common factors with $2^r+1$. Thus, \[P(2^{\gcd(k,r)}+1)\ne P((2^r-1)(2^r+1)).\]So we must have that $r$ is odd. Let $q=\gcd(k,r)$ for ease of notation. We have $q\mid r$ with both $q,r$ odd. It's well known that this implies $X^q+1\mid X^r+1$ (just plug in the roots of $X^q+1$ into $X^r+1$), so \[2^q+1\mid 2^r+1.\]Thus, $\gcd(2^q-1,2^r-1)=1$, so again \[P(2^{\gcd(k,r)}+1)\ne P((2^r-1)(2^r+1)).\]Note that we are ignoring the case $r=1$ as it is under the previous case. Thus, this case is not possible. So far, we've shown that $f(2)\in\{2,8\}$ and $f(3)=3$. Let's finally get rid of the case $f(2)=8$, so suppose it was the case. We have \[P(f(5))=P(f(2)+f(3))=P(11)\]and \[P(f(5))=P(f(1)+f(4)),\]so $f(4)+1=11^a$, so $11^a-2^b=1$. By Mihailescu, this has no solutions, so we must have $f(2)=2$, as desired. $\blacksquare$ So we have $f(x)=x$ for $x\in\{1,2,3\}$. This is the base case for our main induction, but to that induction, we need a key lemma. Lemma: If $a,b\in\mathbb{N}$, then \[P(2^a-1)=P(2^b-1)\implies a=b.\] Proof of Lemma: We see that $\gcd(2^a-1,2^b-1)=2^{\gcd(a,b)}-1$, so \[P(2^{\gcd(a,b)-1})=P(2^b-1).\]Let $x=2^{\gcd(a,b)}$ and $r=b/\gcd(a,b)$. Suppose we had $r\ge 2$. Then, \[P(x-1)=P(x^r-1).\]If $p$ is a prime factor of $r$, then \[x-1\mid x^p-1\mid x^r-1,\]so \[P(x-1)\subseteq P(x^p-1)\subseteq P(x^r-1),\]but since the outer two are equal, we in fact have $P(x-1)=P(x^p-1)$. Thus, \[P(1+x+\cdots+x^{p-1})\subseteq P(x-1).\]It's well known that $d=\gcd(1+x+\cdots+x^{p-1},x-1)=\gcd(p,x-1)$ (ignore that $p$ is prime and induct on $p$), so we have that \[\gcd\left(\frac{1+x+\cdots+x^{p-1}}{d},x-1\right)=1.\]But all the prime factors of the quanitity on the left are prime factors of the one on the right, so in fact \[1+x+\cdots+x^{p-1}=d.\]But $1+x+\cdots+x^{p-1}>x^{p-1}\ge 2^{p-1}\ge p\ge d$, so we have a contradiction. Thus, $r=1$, so $b=\gcd(a,b)$, so $b\mid a$. Similarly, $a\mid b$, so $a=b$. $\blacksquare$ We're now ready to induct. Claim 4: If $f(x)=x$ for all $1\le x\le 2^n-1$ where $n\ge 2$, then $f(x)=x$ for all $1\le x\le 2^{n+1}$. Proof of Claim 4: Note that \[P(f(2^{n+1}-2)+2)=P(f(2^{n+1}))=\{2\},\]so $f(2^{n+1}-2)=2^a-2$. But \[P(f(2^{n+1}-2))=P(2f(2^n-1))=P(2^{n+1}-2),\]so $P(2(2^{a-1}-1))=P(2(2^n-1))$. Thus, $n=a-1$ (by claim 4), so $f(2^{n+1}-2)=2^{n+1}-2$. Also, \[P(f(2^{n+1}-1)+f(1))=P(f(2^{n+1}))=\{2\},\]so $f(2^{n+1}-1)=2^a-1$ for some other $a$. Also, \[P(f(2^{n+1}-1))=P(f(2^{n+1}-2)+f(2))=P(2^{n+1}-1),\]so $P(2^{n+1}-1)=P(2^a-1)$, so $a=n+1$ (claim 3), so $f(2^{n+1}-1)=2^{n+1}-1$. Now suppose $3\le\alpha\le 2^n-1$. Then, \[P(f(2^{n+1}-\alpha)+f(\alpha))=P(f(2^{n+1}))=\{2\},\]so $f(2^{n+1}-\alpha)=2^a-\alpha$. We also have \[P(f(2^{n+1}-\alpha)+f(\alpha-1))=P(f(2^{n+1}-1))=P(2^{n+1}-1).\]Thus, $P(2^a-1)=P(2^{n+1}-1)$, so $a=n+1$ by claim 3, so $f(2^{n+1}-\alpha=2^{n+1}-\alpha$. It remains to show that $f(2^n)=2^n$. By claim 2, we have $f(2^n)=2^a$ for some other $a$. Also, \[P(f(2^n)+f(2^{n-1}))=P(f(3\cdot 2^{n-1}))=P(3\cdot 2^{n-1})=\{2,3\}.\]Thus, $P(2^{a-n+1}-1)=\{3\}$, so $3^b-2^{a-n+1}=1$ for some $b$. By Mihailescu, either $b=1$ and $a=n$ (which means $f(2^n)=2^n$), or $b=2$ and $a-n=2$, so WLOG we're in the latter case, so $f(2^n)=2^{n+2}$. Then, \[P(f(2^n)+f(2^{n-2})=P(f(2^n+2^{n-2}))=P(2^n+2^{n-2})=\{2,5\}\text{ or }\{5\}\]and \[P(f(2^n)+f(2^{n-2})=P(2^{n+2}+2^{n-2})=\{2,17\}\text{ or }\{17\}.\]This is a contradiction, so we have $f(2^n)=2^n$, so the claim is shown. $\blacksquare$ Thus, $f(x)=x$ for all $x$ by induction, so we're done. $\blacksquare$

For any prime $p$ exists $k: p\mid f(k).$ By induction $p\mid f(ak).$ Consequently $f(1)=1$ by surjectivity. All are modulo p. Claim 1: $p\mid f(x)\iff k\mid x.$ Proof. If $p\mid f(x)$ but $k\nmid x$ then let $x=ab+c.$ So $f(ab)+f(c)\equiv f(c),$ absurd. The other direction is trivial. $\blacksquare$ Claim 2: $k=p.$ Proof. Note that $f(x)\equiv f(x+k).$ It is not hard to follow that $k\geq p.$ If $f(x)\equiv f(y),$ then $f(ak-x)\equiv f(ak-y).$ So $f(ak+x-y)\equiv 0.$ Thus $k\mid x-y.$ So the claim. $\blacksquare$ Claim 3: $f(x)\equiv f(y)\iff x\equiv y.$ Proof. The first direction gives ($a$ is constant) $f(x)+f(akx-x)\equiv f(y)+f(akx-x)\equiv f(y+akx-x).$ So $x\equiv y.$ The second direction gives $y-x+akx\equiv 0.$ So $f(y-x+akx)\equiv f(y)+f(akx-x)\equiv 0.$ Clearly $f(x)+f(akx-x)\equiv 0,$ so the claim. $\blacksquare$ Claim 4: $f(x)=x.$ Proof. If $f(x)>x,$ then $p\mid f(x)-x+1\geq 2.$ It gives $x\equiv x-1,$ absurd. If $f(x)<x,$ then $p\mid x-f(x)+1\geq 2.$ It gives $f(x)\equiv f(x)-1,$ absurd. $\blacksquare$

Physicsknight wrote: Answer $f (n)=n\forall n\in\mathbb N$ Solution Claim 1- $f (n)=n $ Proof- $\frac {p}{f (n)+f (m)}\implies \frac {p}{f (m+n)} $. There exists an integer such that $a(f (n))+f (m))=f (n)+f (m)$ . If we show that $f (0)=0, a=1$, and $f (1)=1$. Then $f (n+1)=f (n)+1$ so $f (n)=n\forall n\in\mathbb N$. Claim 2- $f (0)=0$ Proof- $f (0)=2af (0) $ for $n=m=0$. If $f\ne 0$ then $a=\tfrac 12$. Since $a$ is an integer, $f (0)=0$. Claim 3- $f (n+m)=a(f (n)+f (m)) $. Proof- Decompose $f (m+n)$ into a prime number, and $f (n)+f (m) $. Since $p $ divides $f (n)+f (m)\implies \frac {p}{f (n+m)}$ . There are common prime factors this $\implies a $ exists. This is wrong, there's nothing f(0).

The only solution is $\boxed{f(n) = n}$, which works. We now prove it's the only solution. Let $x\sim y$ denote that for all primes $p$, $p\mid x \iff p\mid y$. So we have the assertion $P(m,n)$ that \[f(m+n) \sim f(m) + f(n)\]Claim: $f(1) = 1$. Proof: Note that there exists a positive integer $k$ such that $f(k) = 1$. If $k>1$, then $f(k) =1 \sim f(1) + f(k-1)$, contradiction as $f(1) + f(k-1) > 1$. So $k=1$. $\square$ Claim: For any prime $p$ and positive integers $a>b$, if $p\mid f(a) - f(b)$, then $p\mid f(a-b)$. Proof: By surjectivity, let $k$ be a positive integer for which $p\mid f(a) + f(k)$ and $p\mid f(b) + f(k)$. $P(a,k)$ implies $p\mid f(a+k)$ $P(b,k)$ implies $p\mid f(b+k)$. $P(b+k, a-b): f(a+k) \sim f(b+k) + f(a-b)$. So $p\mid f(b+k) + f(a-b) \implies p\mid f(a-b)$. $\square$ So $f$ is injective and $|f(m+1) - f(m)| = 1$ for all positive integers $m$. We now show $f(n) = n\forall n $ by induction (base case $f(1) = 1$). Suppose $f(m) = m$ for all $m<x$, where $x>1$. We have $|f(x) - f(x-1)| = 1$, so $f(x) = x-2$ or $f(x) = x$. If $f(x) = x-2$, then $f(x) = f(x-2)$, contradicting injectivity. So $f(x) = x$, which completes the induction.

Firstly , we'll show that $f(1)=1$. By surjectivity of $f$ , we know that there exist a number $n \in \mathbb{N}$ , such that $f(n)=1$ , then if $n>1$ , one can see that for each prime number $p$ which $p | f(n-1)+f(1)$ , we have $p|f(n)=1$ , so $f(n-1)+f(1)=1$ which is a contradiction and we get $f(1)=1$. Now notice that since for each natural number $m$ , the set of prime factors of numbers $f(m+1)$ and $f(m)+1$ are equal , as the result we have $gcd(f(m) , f(m+1))=1$. Now define the function $ g: \mathbb{N} \to \mathbb{N}$ in such a way that for each natural number $n$ , $g(n)$ be the least number such that $f(g(n))=n$. ( which always there exist such a $g(n)$ by surjectivity. ) So we'll show that for natural numbers $n,m$ , the numbers $n+f(m)$ and $n+f(m+1)$ are coprime. Suppose not and there exist a prime number $p$ which divides both of these numbers , then one can see that : $$p|n+f(m) \implies p|f(g(n)+m) , p|f(g(n)+m+1) \implies p|gcd(f(g(n)+m) , f(g(n)+m+1))=1$$which is a contradiction. So numbers $f(m+1)-f(m)$ and $n+f(m)$ are coprime which implies $|f(m+1)-f(m)|=1$ (because if there exist a prime number $q$ , such that $q|f(m+1)-f(m)$ , then for a large enough number $k$ and $n=qk-f(m)$ , we have $q|n+f(m)$ which is a contradiction. ) Now since $f(1)=1$ , for each natural $n$ we have $f(n)\le n$ and for proving that $f(n)=n$ , it's enough to show that this equality happens for infinitely many natural numbers $n$. ( Note that obviously , if for natural numbers $m<t<n$ we have $f(n)=n$ and $f(m)=m$ , one can get $f(t)=t$) Consider that $p_1<p_2<p_3<...$ are all prime numbers. By induction on $i$ we'll show that $f(p_i)=p_i$. So obviously $f(2)=2$ and by Chebyshev's theorem for each $i$ we have $p_{i+1}<2p_{i}$ , so by induction case on $i$ one can see that : $$f(p_{i+1}-p_{i})=p_{i+1}-p_{i} , f(p_i)=p_i \implies p_{i+1}|f(p_{i+1}) , f(p_{i+1}) \le p_{i+1} \implies f(p_{i+1})=p_{i+1}$$So we're done.

$f$ surjective implies $f(1)=1$, so we restate the problem as such. The answer is $f(n) = n$ only. Call a positive integer $n$ $g(a)$ if $n$ contains only prime factors in $a$ and all prime factors in $a$. Notice that $f(2) = 2$ clearly. Now we induct from $f$ on $[1, 2^n]$ to $(2^n, 2^{n+1}]$. Observe that $f(2^{n+1} - 1) = g(2^{n+1} - 1)$ by the constraint. Thus, for $k \in (2^n, 2^{n+1}] = 2^{n+1} - a$, we have $$g(2^{n+1} - 1) = f(k) + f(a) = f(k) + a = f(k)+f(a+1) - 1 = 2^k - 1.$$In particular, by Zsigmondy we must have $n+1 = k$ precisely, so $f(k) = 2^{n+1} - a = k,$ as needed.

Suppose $p\mid f(a)$. If $p\mid f((k-1)a)$ then $p\mid f((k-1)a)+f(a)\implies p\mid f(ka)$. By induction, $p\mid f(ka)$ for all positive integers $k$. Suppose $p\mid f(b)$, then \[p\mid f(b) \implies p\mid f(\text{min}(a,b))+f(|a-b|)\]so $p\mid f(|a-b|)$. By the Euclidean Algorithm, $p\mid f(\text{gcd}(a,b))$. If $f(1)>1$ then let $q\mid f(1)$. We have $q\mid f(k)$ for all $k$, violating surjectivity. Thus, $f(1)=1$. If $p\mid f(a)$ and $p\mid f(a+1)$ then $p\mid f(1)$, impossible, so $f(a)$ and $f(a+1)$ are coprime. Suppose $p\mid f(a+1)-f(a)$ then pick $b$ such that $p\mid f(a)+f(b)$, so $p\mid f(a+1)+f(b)$. This means that $p\mid f(a+b)$ and $p\mid f(a+b+1)$, contradiction. Thus, $f(a+1)-f(a)$ is $1$ or $-1$. Let $f(a+1)=f(a)-1$, then $f(a)=f(a+1)+f(1)$, so $p\mid f(a)\iff p\mid f(a+2)$. If $f(a)\neq f(a+2)$ their positive difference is two, so for every prime $q>2$, if it is divisible by one of those it cannot be divisible by the other. Thus, either $f(a)=f(a+2)$ or $f(a)=4$, $f(a+2)=2$. However, in the second case we can apply the same reasoning to $f(a+1)=f(a+2)+f(1)=3$ which can't happen because $f(a+1)=3$ has no corresponding $f(a+3)$ that works. Therefore, $f(a)=f(a+2)=x$ and $f(a+1)=x-1$. Call $a$ sus if if satisfies this. Furthermore, call $a$ imposter if $f(a+3)=x+1$ and crewmate if $f(a+3)=x-1$. We are under the assumption that at least one sus number exists. If $a$ is a crewmate, then $a+2$ must also be sus. By surjection, there must exist at least one imposter. WLOG just let that imposter be $a$. Then, $f(a+3)=f(a)+1$ so $p\mid f(a+3)\iff p\mid f(a+1)$. Since $f(a+1)\neq f(a+3)$, $f(a+1)=2$ and $f(a+3)=4$. Thus, $x=3$. Therefore $a$ is sus only if $f(a)=3$. If $a$ is not sus and $f(a)\ge 4$ then for all $b>a$, $b$ is not sus. We have deduced that our sus numbers are a set of consecutive odd numbers with the smallest element, if there are elements at all, of $3$. Suppose there is at least one sus number, then $f(3)+f(5)=6$, so $6\mid f(8)$. If there are at least three sus numbers, then $f(8)=2$. IF there are two, $f(8)=4$. If there is one, $f(8)=6$. But then $f(2)+f(3)=5$ and so $5\mid f(5)=3$ which is impossible. Thus, there are no sus numbers, so $f$ is always strictly increasing. Thus, $f(x)=x$ for all $x$.

Throughout this solution "power of $k$" means that it's of the form $k^m$ where $m \geq 1$, i.e. $1$ is not a power of $k$ unless otherwise stated. The answer is $f(n)=n$ only, which clearly works. If $f(a)=1$, then $a=1$, else $f(a-1)+f(1)>1$ has no prime divisors: absurd. Henceforth ignore surjectivity. Clearly $f$ sends powers of two to powers of two. Now given that $f$ is the identity on $1,\ldots,2^k$, for some $k \geq 1$, we prove that it is the identity on $2^k+1,\ldots,2^{k+1}$. Note that the base case of $k=1$ is done already, and that for the inductive step we have $\mathrm{rad}(f(n))=\mathrm{rad}(n)$ for all $n \in (2^k,2^{k+1}]$. Now, let $x \in (2^k,2^{k+1}]$ and suppose that $2^{k+1}-2^{l+1}<x\leq 2^{k+1}-2^l$ for some uniquely determined $0 \leq l \leq k-1$, so $x>2^k+1$ (we will deal with the case of $x=2^{k+1}$ last). Then we have $$\mathrm{rad}(f(x)+f(2^{k+1}-x)=2 \implies f(x)+(2^{k+1}-x)=2^a$$for some $a \geq 1$. Also, let the odd prime divisors of $2^{k+1}-2^l$ are $p_1,\ldots,p_r$. Then if $x \neq 2^{k+1}-2^l$, so $l \geq 1$ and thus $2 \mid 2^{k+1}-2^l$, we have $$\mathrm{rad}(f(x)+f(2^{k+1}-2^l-x))=2p_1\ldots p_r \implies f(x)+(2^{k+1}-2^l-x)=2^bp_1^{e_1}\ldots p_r^{e_r}$$for some $b,e_1,\ldots,e_r \geq 1$. If $x=2^{k+1}-2^l$, then this holds as well since $\mathrm{rad}(f(x))=\mathrm{rad}(x)$, except in the case of $l=0$ we must allow $b=0$. Subtracting these two equations yields $$2^l=2^a-2^bp_1^{e_1}\ldots p_r^{e_r}.$$Obviously we need $a>b$, hence $b=l$, so rearranging the equation yields $p_1^{e_1}\ldots p_r^{e_r}=2^{a-l}-1$. On the other hand, for Zsigmondy reasons $\mathrm{rad}(2^x-1)$ uniquely determines $x \geq 0$, hence it follows that $a-l=k+1-l \implies a=k+1$, hence $f(x)=x$ as desired. It remains to deal with $f(2^{k+1})$, which is a power of $2$. First suppose that $k \geq 1$. Since we know $f(2^k)=2^k$ and $f(2^k+1)=2^k+1$, it follows that $\mathrm{rad}(f(2^{k+1})+1)=\mathrm{rad}(f(2^{k+1}+1))=\mathrm{rad}(2^{k+1}+1)$. Then for Zsigmondy reasons, we should be able to guarantee $f(2^{k+1})=2^{k+1}$ most of the time; the exception is when $\{f(2^{k+1}),2^{k+1}\}=\{2,8\}$, which would imply $k=2$ and $f(8)=2$. But then we should have $\mathrm{rad}(f(10))=\mathrm{rad}(f(8)+f(2))=\mathrm{rad}(4)$, but also $\mathrm{rad}(f(10))=\mathrm{rad}(2f(5))=\mathrm{rad}(10)$: contradiction. It remains to deal with $k=0$, i.e. finding the value of $f(2)$, where literally everything goes wrong. So we will need to do a bit of bashing. Suppose that $f(2)=2^a$ where $a \neq 1$, and $f(4)=2^b$. Then $\mathrm{rad}(f(3))=\mathrm{rad}(2^a+1)$, and thus $\mathrm{rad}(f(6))=\mathrm{rad}(2(2^a+1))$. But we should also have $\mathrm{rad}(f(6))=\mathrm{rad}(2^a+2^b)$, implying $\mathrm{rad}(2^{|a-b|}+1)=\mathrm{rad}(2^a+1)$. Thus either $b=2a$ or $a=3$ and $b=2,4$. If the latter case applies, then $f(3)$ is a power of a $3$, say $3^c$. Then $\mathrm{rad}(f(5))=\mathrm{rad}(2^b+1) \in \{5,17\}$, but it should also equal $\mathrm{rad}(3^c+8)$. If $d=2$, it follows that we should have $3^c+8=5^d$ for some $d$, by taking mod $4$ it follows that $c$ is even, and then by taking mod $8$ it follows that $d$ is even, so we can write $c=2c'$ and $d=2d'$ and rewrite the equation as $(5^{d'}+3^{c'})(5^{d'}-3^{c'})=8$, which is clearly impossible (since $c',d' \geq 1$, so we get a size contradiction). In the latter case, because $f(5)+1$ should have the same prime divisors as $2f(3)$, which is twice a power of $3$, it follows by Zsigmondy that $f(5)=17$. Then $\mathrm{rad}(f(5)+f(3))=\mathrm{rad}(f(8))=2$, hence $3^c+17$ is a power of $2$, but also $\mathrm{rad}(f(5)+f(2))=\mathrm{rad}(f(3)+f(4))$, so $3^c+16$ is a power of $5$. By checking small cases and then applying Mihailescu it follows that $c=1$, but this contradicts the fact that $3^c+8$ should be a power of $17$. Otherwise, if $b=2a$, then $f(3)+1$ should be a power of $2$, say $2^c$. Then we should have $\mathrm{rad}(2^c-1)=\mathrm{rad}(f(3))=\mathrm{rad}(2^a+1)$. Thus for any $p \mid 2^c-1$, we should have $p \mid 2^{2a}-1$, hence $p \mid 2^{\gcd(c,2a)}-1$, but also if $p \mid 2^{\gcd(c,2a)}-1$ then it should divide $2^c-1$ as well. For Zsigmondy reasons, this means that $\gcd(c,2a)=c \implies c \mid 2a$. If $c$ is even, then write $2^c-1=(2^{c/2}-1)(2^{c/2}+1)$, which should have the same prime factors as $2^a+1$. However, since $c/2 \mid a$, if $p$ is an (odd) prime dividing $2^{c/2}-1$, then we should have $p \mid 2^a-1$ as well, so it can't divide $2^a+1$ as well, hence $c/2=1$, so $2^c-1=3$ and thus $a=3$, so $f(2)=8$ and $f(4)=16$, hence $\mathrm{rad}(f(5))$ equals both $11$ and $17$: contradiction. Otherwise, if $c$ is odd, we have $c \mid a$, so again any (odd) prime dividing $2^c-1$ divides $2^a-1$ and therefore can't divide $2^a+1$, hence $c=1$ and $f(3)=1$, which is forbidden. It therefore follows that $f(2)=2$, so we can actually finish the induction. Remark: original proof was a bit off, fixed now

Here's a short and cool solution took me 3.5 hours wtf im on vacation tho so its okay It's obvious that f(1)=1, else p|f(1) by building means p|f(n), which contradicts surjectivity. Suppose $\exists m>n:f(m)=f(n)$; take some prime $p$ s.t. (exists by surjectivity) $p \mid f(n)+f(k)=f(m)+f(k)\implies p \mid f(n+k),f(m+k)=f(m-n)+f(n+k)\implies p\mid f(m-n)$, contradiction for sufficiently large $p$, whence f is injective. Now, $p\mid f(n+1)-f(n)\implies p\mid f(n+1-n)=1$, contradiction unless |f(n+1)-f(n)|=1. Since f is bijective f is either strictly increasing or decreasing, the latter is impossible, whence f(n)=n. $\blacksquare$

My first N5

Basically a bit of casework solves this problem

The answer is $\boxed{f(x)=x}$, which evidently works. Notice that $f$ is surjective if and only if $f(1)=1$, so we will use these two properties interchangeably. Denote $\operatorname{rad}(x)$ as the product of the distinct prime factors of $x$. Finally, let the given assertion be $P(m,n)$. Claim 1: $\operatorname{rad}(f(2^e)) = 2$ for all integers $e \ge 1$. Proof: Take $P(2^{e-1}, 2^{e-1})$. This means that if $\operatorname{rad} (f(2^{e-1}))=2$, we also have $\operatorname{rad} (f(2^e)) = 2$, so induction finishes. $\square$ Claim 2: We have $f(x)=x$ for $x \le 4$. Proof: $f(1)=1$ is given, so we just need to show the claim for $2 \le x \le 4$. First, $P(3,1)$ gives $f(3)=2^y-1$ for some $y$, and we already established that $f(2)=2^x$ for some $x$. Then, $P(2,1)$ gives \[\operatorname{rad}(2^x+1) = \operatorname{rad}(2^y-1).\] We will use casework now: If $x=3$, we must have $\operatorname{rad}(2^x+1) = \operatorname{rad}(2^y-1)=3$, which gives \[2^y-1 = 3^z.\] Setting $y=2$ and applying Zsigmondy makes it the only solution for this equation. Hence, $f(2)=8$ and $f(3)=3$. Then, $P(3,2)$ gives \[\operatorname{rad}(f(2)+f(3)) = \operatorname{rad}(f(5)) = \operatorname{rad}(f(1)+f(4)) = 11\]\[\implies 2^a+1=11^b.\] Plugging in $a=5$ makes the LHS contain a factor of $11$, so by Zsigmondy, we just manually test $a \le 5$ to see that this equation has no solutions. Otherwise, denote $p$ as a primitive prime factor of $2^{2x}-1$, which exists by Zsigmondy. Since it does not divide $2^x-1$, it must divide $2^x+1$ and $2^y-1$. Thus, $2x \mid y$, and $2^{2x}-1 \mid 2^y-1$. This fixes $x=1$ and Zsigmondy fixes $y=2$. Hence, $f(2)=2$ and $f(3)=3$. Then, $P(3,2)$ gives \[\operatorname{rad}(f(2)+f(3)) = \operatorname{rad}(f(5)) = \operatorname{rad}(f(1)+f(4)) = 5\]\[\implies 2^a+1=5^b.\] Zsigmondy shows that $a \le 2$, which gives $f(4)=4$ as the only solution. $\square$ Claim 3: If $\operatorname{rad} (2^x-1) = \operatorname{rad} (2^y-1)$ or $\operatorname{rad} (2^x+1) = \operatorname{rad} (2^y+1)$ Proof: This is a simple consequence of Zsigmondy. $\square$ We will prove that $f(n)=n$ by strong induction up to $2^k$. The base case already holds, so suppose the inductive hypothesis holds up to $2^k$. Notice that \[2 = \operatorname{rad}(f(2^{k+1})) = \operatorname{rad}(f(2^{k+1}-1)+f(1)) = \operatorname{rad}(f(2^{k+1}-1)+1),\] so $f(2^{k+1}-1)=2^t-1$ for some $t$. Then, \begin{align*} \operatorname{rad}(2^t-1) &= \operatorname{rad}(f(2^{k+1}-1)) \\ &= \operatorname{rad}(f(2^k-1)+f(2^k)) \\ &= \operatorname{rad}((2^k-1)+2^k) \\ &= \operatorname{rad}(2^{k+1}-1). \end{align*} This shows that $k+1 = t \implies f(2^{k+1}-1) = 2^{k+1}-1$. Next, recall that $f(2^{k+1})=2^t$ for some $t$: \begin{align*} \operatorname{rad}(2^t+1) &= \operatorname{rad}(f(2^{k+1})+1) \\ &= \operatorname{rad}(f(2^{k+1})+f(1)) \\ &= \operatorname{rad}(f(2^{k+1}-1)+f(2)) \\ &= \operatorname{rad}(2^{k+1}+1), \end{align*} implying that $t=k+1 \implies f(2^{k+1}) = 2^{k+1}$. Finally, suppose that $n \in (2^k, 2^{k+1}-1)$ and let $i=2^{k+1}-n-1$. We have \begin{align*} \operatorname{rad}(f(n)+i) &= \operatorname{rad}(f(n)+f(i)) \\ &= \operatorname{rad}(f(n+i)) \\ &= \operatorname{rad}(f(2^{k+1}-1)) \\ &= \operatorname{rad}(2^{k+1}-1), \end{align*} and \begin{align*} \operatorname{rad}(f(n)+i+1) &= \operatorname{rad}(f(n)+f(i+1)) \\ &= \operatorname{rad}(f(n+i+1)) \\ &= \operatorname{rad}(f(2^{k+1})) \\ &= \operatorname{rad}(2^{k+1}). \end{align*} So, we have an integer $j$ such that \[f(n)+i+1 = 2^j \implies \operatorname{rad}(2^j-1) = \operatorname{rad}(f(n)+i) = \operatorname{rad}(2^{k+1}-1),\] so $j=k+1$, which means $f(n)=n$. The induction is complete, and the problem is solved.

We forgot the condition of $f$ being surjective and only use $f(1)=1$ The problem can be rewrited as \[\operatorname{rad}\big(f(x)+f(y)\big) = \operatorname{rad}\big(f(x+y)\big) \hspace{0.2cm}\forall\hspace{0.1cm} x,y\in \mathbb{N}\]Where $\operatorname{rad}(a)$ is the product of distinct primes of $a$ $\textcolor{blue}{\text{Claim. } f(2^\theta) \hspace{0.1cm}\text{is a power of 2}}$ Plugging $(1,1)$ \[\operatorname{rad}\big(f(1)+f(1)\big)=\operatorname{rad}\big(f(2)\big)\]so \[\operatorname{rad}\big(f(2)\big)=\operatorname{rad}(2)\]then $f(2)=2^\theta$ And as \[\operatorname{rad}\big(f(2^\alpha)+f(2^\alpha)\big)=\operatorname{rad}\big(f(2^{\alpha+1})\big) \]We conclude by induction $\textcolor{blue}{\text{We start by finding the frist values of the function}}$ Plugging $(2,1)$ \[\operatorname{rad}\big(f(2)+f(1)\big)=\operatorname{rad}\big(f(3)\big) \]But \[\operatorname{rad}\big(f(2)+f(2)\big)=\operatorname{rad}\big(f(3)+1\big) \]so \[f(3)+1=2^\gamma\]then \[\operatorname{rad}\big(2^\gamma-1\big)=\operatorname{rad}\big(2^\theta+1\big) \]Let $p$ be a primite prime of $2^{2\theta}-1$ which by Zsigmondy exists $\left(\operatorname{Ord}_p(2)=2\theta\right)$, then so \[p\mid 2^{2\theta}-1 \Rightarrow p\mid 2^{\theta}+1 \hspace{0.1cm} \text{as}\hspace{0.1cm} p\mid 2^{\gamma}-1 \Rightarrow 2\theta\mid \gamma\]\[\Rightarrow 2^{2\theta}-1\mid 2^{\gamma}-1 \Rightarrow (2^\theta-1)(2^\theta+1)\mid 2^{\gamma}-1\]And as $\gcd(2^\theta-1,2^\theta+1)=1\Rightarrow 2^\theta-1=1\Rightarrow f(2)=2$ so \[\operatorname{rad}\big(f(3)\big)=\operatorname{rad}(3)\Rightarrow f(3)=3^\alpha \Rightarrow 3^\alpha+1=2^\gamma \]by Zsigmondy(or Catalan) $\alpha=1$ and $\gamma=2$ Then we got that \[f(1)=1 \hspace{1cm} f(2)=2 \hspace{1cm} f(3)=3\]Now, \[\operatorname{rad}\big(1+f(4)\big)=\operatorname{rad}\big(f(2)+f(3)\big)=5 \]so $1+2^u=5^v$ and again by Zsigmondy $f(4)=4$ and $f(5)=5$ $\textcolor{red}{\text{So we got}\hspace{0.1cm} f(a)=a \hspace{0.1cm} \forall \hspace{0.1cm} 1\leq a \leq 5}$ $\textcolor{blue}{\text{Lemma. if}\hspace{0.1cm} \operatorname{rad}(2^x-1)=\operatorname{rad}(2^y-1) \hspace{0.1cm} \text{then} \hspace{0.1cm} x=y }$ Trivial by Zsigmondy $\textcolor{blue}{\text{We are going to prove that}\hspace{0.1cm} f(x)=x \hspace{0.1cm} \forall \hspace{0.1cm} x \hspace{0.1cm} \text{by induction}}$ Suppose we have the statement for $x\leq 2^e$ we want to prove the statement for $2^e\leq x \leq 2^{e+1}$ note that \[ f(x)+f(2^{e+1}-x+1)=\underbrace{f(x)+f(2^{e+1}-x)}_{2^\theta}-1 \hspace{0.5cm} (1) \]\[\operatorname{rad}\big(f(2^{e+1}-1)\big)=\operatorname{rad}\big(2^\theta-1\big) \]as $\operatorname{rad}\big(f(2^{e+1}-1)\big)=\operatorname{rad}\big(f(2^e)+f(2^e-1)\big)=\operatorname{rad}(2^{e+1}-1)$ then \[\operatorname{rad}\big(2^{e+1}-1\big)=\operatorname{rad}\big(2^\theta-1\big) \]so by the lemma $f(2^{e+1})=2^{e+1}$ So in $(1)$ we get \[ f(x)+2^{e+1}-x+1=2^{e+1}-1\]then $\boxed{f(x)=x}$

Denote the assertion as $A(m,n)$ and the notation $\operatorname{rad}(m)$ as the product of the distinct prime divisors of $m$. We first compute special values: $f(1)=1$ follows from surjectivity. (This will be the only use of surjectivity in this solution.) $f(2^n)$ is a power of 2 for all $n \in \mathbb{N}$ by inducting on powers of 2. Determine the values of $f(2)$ and $f(3)$ to be of the form $2^a$ and $2^b-1$, respectively, using the previous and $A(1,3)$. Then $A(1,2)$ gives us \[\operatorname{rad}(2^a+1) = \operatorname{rad}(2^b-1).\]Zsigmondy in most cases tells us there exists a primitive prime divisor $p$ with \[p \mid 2^a+1 \mid 2^{2a}-1 \implies 2^{2a}-1 \mid 2^b-1 \implies \operatorname{rad}(2^{2a}-1) = \operatorname{rad}(2^b-1) \implies 2a=b,\]contradiction. Thus $(a,b)=(3,2),(1,2)$ from examining the exceptions, from which we can conclude $f(2)=2$ and $f(3)=3$ is the only possible choice, also inducing $f(4)=4$. We finish with folding induction - assuming $f(x)=x$ holds for $1 \leq x \leq 2^k$, we show it also holds for $2^k+1 \leq x \leq 2^{k+1}$: Note that $A(1,2^{k+1}-1)$ tells us $f(2^{k+1}-1)$ is one less than a power of 2 (say $2^{\ell}$), and $A(2^k, 2^k-1)$ tells us \[\operatorname{rad}(2^{\ell}-1) = \operatorname{rad}(f(2^{k+1}-1) = \operatorname{rad}(2^{k+1}-1) \implies f(2^{k+1}-1) = 2^{k+1}-1\]by Zsigmondy. (This line of argument is a recurring theme in the remainder of our proof.) $A(2^{k+1},1)$ and $A(2^{k+1}-1,2)$, knowing $f(2^{k+1})$ is a power of 2, concludes $f(2^{k+1})=2^{k+1}$. $A(x,2^{k+1}-x)$ tells us $f(x)+2^{k+1}-x$ is one less than a power of 2, and hence $A(x,2^{k+1}-x-1)$ concludes $f(x)=x$. $\blacksquare$

Beautiful problem! Posting for storage. Denote $\mathbb{N}$ and $\mathbb{P}$ by the sets of positive integers and prime numbers, respectively. Note that problem condition is $f(m+n) \equiv 0 \pmod{p} \iff f(m)+f(n) \equiv 0 \pmod{p}$ for all $m,n \in \mathbb{N}, p \in \mathbb{P}$ The answer is $\boxed{f(n)=n~~\forall n \in \mathbb{N}}$ which is clearly satisfy the problem condition. We’ll show that this is the only solution. Claim 1: $f(1)=1$ Proof FTSOC, suppose $f(1)>1 \implies~~$There exist $p\in \mathbb{P}$ s.t. $f(1)\equiv 0 \pmod{p}$ It is easy to see that $f(n)\equiv 0 \pmod{p}~~\forall n \in \mathbb{N}$ which contradicts to the facts that $f$ is surjective$~~\square$ Claim 2: If positive integers $a>b$ and prime $p\in \mathbb{P}$ satisfy $f(a) \equiv f(b) \pmod{p}$, then$ f(a-b) \equiv 0 \pmod{p}$ Proof Supoose positive integers $a>b$ and prime $p\in \mathbb{P}$ satisfy $f(a) \equiv f(b) \pmod{p}$ Since $f$ is surjective, we can select $l \in \mathbb{N}$ such that $f(a)+f(l)\equiv 0\pmod{p}\implies f(b)+f(l)\equiv 0 \pmod{p}$ By the problem condition; $f(a+l)\equiv f(b+l)\equiv 0 \pmod{p}$ Using the problem condition again; $f(a+l)\equiv 0 \pmod{p}\implies f(b+l)+f(a-b)\equiv 0 \pmod{p}$ Since $f(b+l)\equiv 0 \pmod{p}$, it implies that $f(a-b)\equiv 0 \pmod{p}$, as desired$~~\square$ Claim 3: $f$ is injective Proof Suppose there exists positive integers $x>y$ such that $f(x)=f(y)$. Note that $f(x)\equiv f(y) \pmod{p}~~ \forall p \in \mathbb{P}$. By Claim 2, we can conclude that $f(x-y) \equiv 0 \pmod{p}$ for all prime $p\in \mathbb{P}$ which leads to contradiction if we pick $p>f(x-y)$ Claim 4: $|f(m+1)-f(m)|=1 ~~\forall m \in \mathbb{N}$ Proof FTSOC, suppose $|f(m+1)-f(m)|>1~~ \exists m \in \mathbb{N}$ Pick a prime $p$ which divides $f(m+1)-f(m)$. By Claim 1, we can conclude that $f(1)\equiv 0 \pmod{p}\implies p \mid 1$, a contradiction! Finally, combine Claim 1,Claim 3 and Claim 4, we can conclude that $f(n)=n \forall n \in \mathbb{N}$, as desired. $~~\blacksquare$

OG! My first N5! We claim that only function that satisfies is Claim: $f(1)=1$ Proof: FTSOC, assume $f(1)>1$, let $p$ be a prime dividing $f(1)$. Now, we prove by induction on $n$, that $f(n)$ is divisible by p for all naturals $n$. Now, $n=1$ satisfies the condition(Base Case) If the condition holds for $n=k$, then $p|f(1)+f(k)$ which implies $p|f(k+1)$, completing our induction. Thus, $p|f(n)$ for any natural $n$, however this is in contrary to the fact that $f$ is surjective. Hence, our claim is proved. Claim: let $a$ be the the minimal number such that $f(a)=p$. then $p|f(x) \iff a|x$ Proof: let $ka \leq x < (k+1)(a)$. We induct on $k$. For $k=0$, since $a$ is the minimal number such that $f(a)=p$. So it is clear. Now if the statement is true for $k$ for $k+1$ we have that for $(k+1)a \leq x < (k+2)(a)$ $p|f(x) \iff p|f(x-a)+f(a) \iff p|f(x-a).$ Since, $ka \leq x-a < (k+1)(a)$, $p|f(x-a) \iff a|x-a \iff a|x$ and thus our induction is complete.