Does $p\mid f(m)+f(n)\leftrightarrow p\mid f(m+n)$ imply $f(m+n)=f(m)+f(n)$?

Question

Let $f:\mathbb{N}\to\mathbb{N}$ be a function such that: $$(\forall p: \mathrm{~prime~})(\forall m,n\in\mathbb{N})(p\mid f(m)+f(n)\leftrightarrow p\mid f(m+n))$$

is $f$ linear?

---

by linear I mean:

$$(\forall m,n\in\mathbb{N})(f(m+n)=f(m)+f(n))$$

Answer 1

Nope. For example, consider $f(n) = 2^n$.

Answer 2

I found one trivial nonlinear $f$. Let $f\equiv2$. then for arbitrary $m$ and $n$ we have: $$p\mid f(m+n)\leftrightarrow p\mid 2 \leftrightarrow p=2 \leftrightarrow p\mid 4 \leftrightarrow p\mid f(m)+f(n)$$

but $$f(1+1)=2\ne4=f(1)+f(1)$$

Other exmples are constant functions $f\equiv2n_0$ where $n_0$is any positive integer. It seems these are all possible constant functions.

But I guess nonconstant functions are linear.

At least if $f$ is onto then $(\forall n\in \mathbb{N})(f(n)=n)$! But non-surjective functions are interesting for me. Is there any non constant non surjective example?

Answer 3

There are many counterexamples which are not constant.

Take any partition of $\mathbb{N}$ into 2 nonempty sets $A, B$, and take

\begin{equation} f(n)= \begin{cases} 6& \text{if} \, n \in A \\ 18& \text{if} \, n \in B \end{cases} \end{equation}

Let me know if you want more elaborate counterexamples.