Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
$\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

\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.

share|cite|improve this answer
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?

share|cite|improve this answer

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.