# Functional equation of divisibility

I am struggling with the following issue: Find all functions $f:\mathbb{N}_{+}\rightarrow\mathbb{N}_{+}$, such that for all positive integers $m$ and $n$, there is divisibility $$m^2+f(n)\mid mf(m)+n$$

$\mathbb{N}_{+}$ stands for the set of positive integers

I've tried various substitutions but I dont know how to solve functional equations of this form therefore I couldn't manage to find any $f$. I think this is a interesting problem so I'd like to know the answer.

• $f(n)=n$ is a solution. – Donald Splutterwit Nov 30 '17 at 23:41
• Can you prove there are No others? – TheRlee Nov 30 '17 at 23:44
• Well, as a start, I can show that $f(1)=1$. Proof: setting $n=1$ we see that $m^2+f(1)$ divides $mf(m)+1$ for all $m$. But if there were a prime $p\,|\,f(1)$ then taking $m=p$ gives a contradiction, hence there is no such $p$ which implies that $f(1)=1$. – lulu Dec 1 '17 at 0:15
• Thanks @lulu, that's just what I needed to solve the problem! :) – David Dec 1 '17 at 0:35
• How do we see that $m^2+f(1)$ divides $mf(m)+1$? – TheRlee Dec 1 '17 at 0:48

## 1 Answer

Thanks @lulu for showing that $f(1)=1$. Now I can finish the problem by proving that the identity is the only possibility for $f$.

Suppose that there exists $m$ such that $f(m)<m$. Then taking $n=1$ we have $$m^2+1=m^2+f(1)\le mf(m)+1<m^2+1\ ,$$ a contradiction. Now suppose there exists $n$ such that $f(n)>n$. Taking $m=1$, we have $$1+n<1+f(n)\le f(1)+n=1+n\ ,$$ another contradiction. Thus $f(n)=n$ for all $n$.
Addendum. Proof that $f(1)=1$. This proof was provided in a comment by Lulu, I'm copying it verbatim here in case the comment disappears in the future.

Setting $n=1$ we see that $m^2+f(1)$ divides $mf(m)+1$ for all $m$. But if there were a prime $p\mid f(1)$ then taking $m=p$ gives a contradiction, hence there is no such $p$ which implies that $f(1)=1$.

• Oh, good argument (+1). I was still trying to proceed by divisibility. – lulu Dec 1 '17 at 0:42