Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
1  
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
1  
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

3 Answers 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.

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

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

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

 
discard

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