Finding all functions $f: \mathbb{Z^{+}}\to \mathbb{Z^{+}}$ such that $f(a)| (f(b)+a-b)$ for all $a,b\in \mathbb{Z^{+}}$

Solution 1:

Let $a=c+1, b=c$: $$f(c+1) | f(c) +1 \implies f(c+1)\le f(c)+1 \; \; \mathbf{(1)}\hspace{1 cm}(\because f(c)+1\ge1)$$

Let $a=c,b=c+1$: $$f(c) | f(c+1)-1 $$ Now, either $f(c+1)\ge 2$ in which case $$f(c) \le f(c+1) -1 \implies f(c+1)\ge f(c)+1 \; \; \mathbf{(2)}$$ or $f(c+1)=1$ and then $f(c)$ can be anything, as anything divides $0$. This means, using $(1)$ and $(2)$, that if $f(c+1)\ne 1$, $$f(c+1) =f(c) +1$$ Now partition $\mathbb Z^+$ into the set $C= \{c_1,c_2,\dots,c_n\} $ s.t. $f(c_i)=1$ and $c_i$ are in ascending order, and $\overline C$. For the moment, let’s assume $|C|\ge 2$. Now it remains to apply the main condition to get more information about $C$.

Test $1: a= x\in(c_i,c_{i+1} )$, $b=c_j$

Using $(1)$ and $(2)$, it can be checked that $f(a) = x+1-c_i$. It’s required that $$1+x-c_i | 1+x-c_j $$ Since $j$ is free, this is equivalent to saying that $1+x-c_i | c_j -c_k$. The possible values for $f(a)$ are $2,3,4\dots, c_{i+1}-c_i$. Hence, it is sufficient to ensure that $2,3,4,\dots, M$ divide all $c$-differences (the difference of any two members of $C$), where $M$ is the largest consecutive $c$-difference.

Test $2: a= x\in(c_i,c_{i+1})$, $b= y\in(c_j,c_{j+1} )$

This time, it’s needed that $$1+x-c_i | 1+x-c_j$$

But this is exactly the same as the previous one, so no extra restrictions are brought about.

Of course, there’s nothing much to say about the case when $a\in C$.

Now, our condition says that $2,3,4\dots, M$ are factors of all $c$-differences. This means that all elements in $C$ differ by multiples of $\text{lcm}(2,3,4\dots,M)=L$. But $M$ is itself a $c$-difference, so is a multiple of $L$, but also $L\ge M$. This implies $M=L$. Then the only possibilities are $M=1$ or $M=2$. Importantly, the elements in $C$ are equally-spaced.

Case $1$: $M=1$

$f$ looks like $$f(1), \dots, f(c_1-1), 1,1,1\dots 1, f(c_n+1), \dots$$ Setting $a=c_1-1$, $b=c_1$ and $b=c_1 +1$ in the main condition, it follows that $f(c_1-1)$ divides two consecutive integers $\implies f(c_1 -1)=1$. Similarly, $f(c_n+1) =1$. Repeating this logic gives $f(n)=1$. So atleast two $1$‘s together are ‘infectious’.

Case $2$: $M=2$

You can check that in this case, $f$ must look like $$f(1), \dots, f(c_1-1), 1,2,1,2\dots,1,2 , f(c_n+2),\dots$$ Again, you’ll find by setting $a=c_1-2, c_1 -1$ with $b=c_1, c_1 +2$ you can deduce that $f(c_1-2)=1, f(c_1-1)=2$. Similarly with the right end. So, this corresponds to the solution $f(2n) =2, f(2n-1)=1$. The other way round, i.e. starting with $f(1)=2$ doesn’t work.

Case $3$: $|C|=1$

$f$ looks like $$f(1), \dots, 1,2,3,4\dots $$ By assuming that at least $2$ numbers come before that starting $1$ and setting $a= c-2$ and $b=c$, get $f(c-2) | -1 \implies f(c-2)=1$, a contradiction. So, there is atmost $1$ element before the starting $1$, i.e. $f(1)$. Setting $b=1$ and $a\ge 2$, conclude that every positive integer divides $f(1)$, which is impossible. Hence, this case can only correspond to $f(n)=n$.

Case $4$: $C=\emptyset$ Clearly, $f$ must look like $$f(1), f(1)+1, f(1)+2, \dots $$ and this corresponds to $f(n) = n+k$ where $k\ge 1$.

All done. The only solutions are

$$ \boxed{ \mathsf {f(n)=1 \\ f(n) =n+k, \ k\ge 0 \\ f(n)= \begin{cases} 1, & n \ \text{odd} \\ 2, & n \ \text{even} \end{cases}}}$$