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

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))$$

-
$\mathbb{N}=\{1,2,3,...\}$ – user59671 Feb 8 '13 at 21:15
Why did you rollback my edit? – George V. Williams Feb 8 '13 at 21:42
@GeorgeV.Williams: by $\iff$ I'm mean metalanguage equivalence. and $p:prime$ is more clear. but I edited | to \mid . thanks. – user59671 Feb 8 '13 at 21:45
No problem, I was just wondering (although you could change the $p : prime$ to $p : \mathrm{prime}$ (\mathrm{prime}) so it doesn't get italicized. – George V. Williams Feb 8 '13 at 21:46
As far as I can tell, it all comes down to the presence of duplicate primes in the factorization of the left not present in the right, or vice-versa. If we can prove there are no duplicates not present in the other side, then $f$ is linear (because both sides would have the exact same prime factors and therefore must be equal). If we could come up with an $f$ that introduces a duplicate prime without introducing a new prime, that would be a counter-example. I can't seem to do either right now. – Todd Wilcox Feb 8 '13 at 22:32

There are many counterexamples which are not constant.

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

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

Let me know if you want more elaborate counterexamples.

-
you're right. your example can be generalized. If it can be generalized to an infinite valued function, it would be great. However it has been proved there's no surjective counterexample. – user59671 Feb 9 '13 at 17:03

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?

-

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

-
This doesn't satisfy the stated property. $f(1) + f(2) = 2 + 4 = 6$, so $3$ divides it. But $3$ does not divide $f(1 + 2) = 8$. – Zach L. Feb 8 '13 at 21:41