# functional equation in the set of positive integers.

Let $$k$$ be a fixed positive integer. Find all functions $$f :\mathbb{N}\to\mathbb{N}$$ such that for any distinct positive integers $$a_1,a_2,\ldots,a_k$$, there exists a permutation $$(b_1,b_2,\ldots,b_k)$$ of $$\{a_1,a_2,\ldots,a_k\}$$ such that $$f(a_1)/b_1+ f(a_2)/b_2+\ldots+ f(a_k)/b_k$$ is a positive integer.

Please help, I'm really stuck here, I guess $$f$$ must be constant or linear, I tried induction on $$k$$, but the permutation mess everything, the case $$k=1$$ is trivial, idk how to deal with $$k>1$$.

• Constants don't work. If $f(n)=c$ for all $n$ then, for large $a$ $\frac {f(a)}a$ is not an integer. $f(n)=cn$ works for $c\in \mathbb N$.
– lulu
Nov 3 '20 at 9:47
• More broadly, if, for every $n$ we have $n\,|\,f(n)$ then $f(n)$ works. thus $f(n)=n^m$ works but so do "piecewise" functions like $f(n)=n^2$ if $n$ is even and $f(n)=n^5$ if $n$ is odd.
– lulu
Nov 3 '20 at 9:51
• @lulu and OP I wrote a solution last night but it was messy. Just cleaned it up. Please let me know if you find anything wrong. Thanks. Nov 4 '20 at 12:55

Lemma: If $$p$$ is a prime number, $$A, B, M \in \mathbb{N}$$, $$p \nmid B$$, $$M$$ and $$p$$ are coprime, then the sum $$\frac{A}{M} + \frac{B}{p}$$ cannot be a positive integer.

Proof of the lemma is straightforward: $$\frac{A}{M} + \frac{B}{p}=N \Rightarrow pA + MB=NMp \Rightarrow p | MB$$, a contradiction.

Now we prove $$\forall n \in \mathbb N$$, we must have $$n|f(n)$$. We construct a sequence $$a_1, a_2, \ldots, a_k$$ in the following fashion: $$a_1=n$$, and $$\forall 2\leqslant j \leqslant k$$,

$$a_j > \max\{a_m, f(a_m) , \forall 1\leqslant m

Then there's a permutation $$\{ b_j, 1\leqslant j \leqslant k \}$$ of $$\{ a_j, 1\leqslant j \leqslant k \}$$ such that $$S \equiv \sum_{j=1}^k f(a_j)/b_j$$ is a positive integer. Assume $$b_i = a_k$$ for some index $$i$$, we have

$$S = \frac{A}{\prod_{j=1}^{k-1} a_j} + \frac{f(a_i)}{a_k}.$$

From the lemma, since $$\gcd(\prod_{j=1}^{k-1} a_j, a_k)=1$$, we know $$a_k | f(a_i)$$. By construction $$a_k > f(a_j), \forall j, therefore $$i=k, a_k | f(a_k)$$.

It follows that $$\sum_{j=1}^{k-1} f(a_j)/b_j$$ is also a positive integer. By the same reasoning we have $$b_{k-1} = a_{k-1}, a_{k-1} | f(a_{k-1})$$. We repeat this process until finally we have $$f(n)/n$$ as a positive integer.

On the other hand if $$n|f(n), \forall n\in \mathbb{N}$$, the identity permutation guarantees that $$\sum f(a_j)/a_j$$ is a positive integer. $$\blacksquare$$

• I don't understand "we pick prime number $p_2, p_2, \cdots, p_k$ in the following manner, $p_2>\max (n,f(n))$. Should the first $p_2$ be a $p_1$?
– lulu
Nov 4 '20 at 13:36
• No it's $p_2$. The first number is $n$. Nov 4 '20 at 13:39
• Why does $p_2$ appear twice on your list?
– lulu
Nov 4 '20 at 13:40
• Ah, I see. Your goal is to define the numbers $a_i$ and $a_1=n$. It's confusing to write $p_2, p_2, \cdots, p_k$ though.
– lulu
Nov 4 '20 at 13:41
• Yes I agree. I want to emphasize all numbers are prime except for $n$. Later I used $a_j$ instead. Nov 4 '20 at 13:43