Find all functions satisfying f(mn)=f(m)f(n), and m+n|f(m)+f(n)

[lfdahl]

Find all functions, $f: \mathbb{N}\rightarrow \mathbb{N}$, satisfying

\[f(mn)=f(m)f(n),\: \: \: and \: \: \: m+n \: \: |\: \: f(m)+f(n)\]for all $m,n \in \mathbb{N}$.

 

[kaliprasad]

Find all functions, $f: \mathbb{N}\rightarrow \mathbb{N}$, satisfying

\[f(mn)=f(m)f(n),\: \: \: and \: \: \: m+n \: \: |\: \: f(m)+f(n)\]for all $m,n \in \mathbb{N}$.

Spoiler

by putting m = 1 we get $f(n) = f(1) f(n)$ so $f(1) = 1$

now 1 + n is a factor of 1 + f(n) so by inspection f(n) = n. I do not have a proof of the same

 

[Opalg]

Spoiler

by putting m = 1 we get $f(n) = f(1) f(n)$ so $f(1) = 1$

now 1 + n is a factor of 1 + f(n) so by inspection f(n) = n. I do not have a proof of the same

[sp]Odd powers of $n$ also have this property: $(mn)^k = m^kn^k$, and $(m+n)^k = (m+n)(m^{k-1} - m^{k-2}n + \ldots + n^k)$ if $k$ is an odd integer.

I have not thought about whether these are the only solutions.
[/sp]

 

[kaliprasad]

[sp]Odd powers of $n$ also have this property: $(mn)^k = m^kn^k$, and $(m+n)^k = (m+n)(m^{k-1} - m^{k-2}n + \ldots + n^k)$ if $k$ is an odd integer.

I have not thought about whether these are the only solutions.
[/sp]

Spoiler

Right

 

[kaliprasad]

[sp]Odd powers of $n$ also have this property: $(mn)^k = m^kn^k$, and $(m+n)^k = (m+n)(m^{k-1} - m^{k-2}n + \ldots + n^k)$ if $k$ is an odd integer.

I have not thought about whether these are the only solutions.
[/sp]

there is a typo in above

Spoiler

$(m+n)^k = (m+n)(m^{k-1} - m^{k-2}n + \ldots + n^k)$

should be

$m^k+n^k = (m+n)(m^{k-1} - m^{k-2}n + \ldots + n^{k-1})$

 

[lfdahl]

Suggested solution:

Spoiler

As kaliprasad noted: $f(1) = 1$. So, $2n+1 \;\; | \;\; f(2n) + f(1) = f(2) \cdot f(n) + 1 \Rightarrow gcd(2n+1,f(2)) = 1$ for all $n$. This means, that $f(2)$ has no odd prime divisor, so $f(2) = 2^k$. Furthermore, $3 \;\; | 1 + f(2) = 1 + 2^k \Rightarrow k$ is odd (as Opalg noted). Also note, $f(2^m) = f(2) \cdot f(2) \cdot … \cdot f(2) = 2^{km}$ for all $m$. Now, for all $m$ and $n$, $2^m+n \;\; | \;\; f(2^{m}) + f(n) = 2^{km} + f(n)$. But $k$ is odd, so $2^m+n \;\; | \;\; 2^{km} + n^k$. Thus $2^m+n \;\; | \;\; f(n)-n^k$. But this is valid for all $m$, so $f(n) – n^k = 0 \Rightarrow f(n) = n^k.$
We have now proven, that $f(n) = n^k$ for all $n$ for some fixed odd number $k$. On the other hand, it is easily seen that functions of this form satisfy the given conditions.