Find all functions $f : N \to N$ such that $f(m)+f(n)$ divides $m+n$ for all positive integers $m$ and $n$.
Problem
Source: 2006 MOP Homework Blue Algebra 1
Tags: function, algebra, functional equation, Divisibility
15.04.2020 16:24
Just use strong induction and PNT/slightly strengthened Bertrand's Postulate.
15.04.2020 17:39
parmenides51 wrote: Find all functions $f : N \to N$ such that $f(m)+f(n)$ divides $m+n$ for all positive integers $m$ and $n$. Plugging $n=p-m$, $p > m$ prime, we get that $f(p-m)+f(m)=p$ (since it is a $p$ divisor greater than $1$). In particular, $f$ is not bounded. Now I prove that $f$ is injective. If $f(a)=f(b)=c$, we have for any $m$: $$f(m)+f(a)|m+a, f(m)+f(b)|m+b \Rightarrow f(m)+c|a-b$$ However, since $f$ is unbounded, $a=b$. Finally: $m=n=1$ gives $f(1)=1$ $m=n=2$ gives $f(2) \le 2$, hence $f(2)=2$ ... by induction, we get that $f(k)=k$ for all $k$.
15.04.2020 18:23
So the problem statement is expressed as $f(m)+f(n)\mid m+n$. Setting $m=n$, we get that $f(m)\mid m$, thus we get that $f(m) \leqslant m$. If we set $m=1$ we get that $f(1)=1$, setting $m=1$ and $n=p-1$, for some prime number $p$, we get that $f(p-1)+1 \mid p$, thus $f(p-1)+1 \in \{1,p\}$, since the codomain is the set of the natural numbers $\mathbb{N}$, we get that $f(p-1)=p-1$, for any prime number we choose. Now set $n=p-1$ we get that $f(m)+p-1 \mid m + p-1$, now we can also get that $f(m)+p-1\mid m-f(m)$. Since $m-f(m) > 0$, we have that $f(m)+p-1 \leqslant m - f(m) \iff 2f(m)+p-1 \leqslant m$, But notice we can always set a prime number $p$ such that this inequality doesn't hold, so we have that $m-f(m)=0 \iff m=f(m)$ Thus the only solution is $\boxed{m=f(m)}$.....
15.04.2020 18:24
Iran MO 2004
16.04.2020 07:32
Let $P (x,y) $ be the assertion $\frac {x+y}{f (x)+f (y)}$. $P (n,n)\implies 2f (n)\mid 2n\implies f (n)\mid n\implies f (n)\le n $. $P (p-n,n):\text{p is a very large prime} \implies f (p-n)+f (n)=p$ but notice that $f (p-n)\le p-n$ and $f (n)\le n $ so this forces $f (p-n)=p-n $ and $f (n)=n$. But since $n $ is arbitrary we get $f(x)=x~\forall x\in\mathbb {N} $.