pieater314159 wrote: Let $f:\mathbb N\to \mathbb N$. Show that $f(m)+n\mid f(n)+m$ for all positive integers $m\le n$ if and only if $f(m)+n\mid f(n)+m$ for all positive integers $m\ge n$. Proposed by Carl Schildkraut Solution. Firstly we deal the case when, $f(m) + n\mid f(n) + m$ for all $m\leq n$. This gives us $f(m) - m \leq f(n) - n$ for all $m\leq n$. We have a positive integer $m$. We choose $n \equiv - f(m) \pmod {f(m)-f(1)}$ and $n\geq m$, so $f(m) - f(1) \mid n+f(m)$. Further, $f(1) + n\mid f(n) + 1$, so $f(n) = k(f(1)+n)-1$ for some positive integer $k$. Also, $f(m) + n \mid f(n) + m$, so \[f(m) + n\mid k(f(1)+n)-1+m\implies f(m) + n\mid k(f(1) - f(m)) + m- 1.\]Now as $f(1) - f(m) \mid f(m) + n$, $f(m)-f(1)\mid m-1$ which gives $f(m) - m \leq f(1) - 1$. We also have that $f(m) - m\leq f(n) - n$ for all $m\leq n$, which gives us $f(m) - m = f(1) - 1$ for all $m$ which eventually gives us that $f(m) + n = f(n) + m$ for all $m,n$ and we are done in this case. Now we need to deal the case when $f(m) + n \mid f(n) + m$ for all $m\geq n$. This gives us $f(m) - m\leq f(n) - n$ for all $m\ge n$. We have $f(m) + 1\mid f(1) + m$ and also $f(m) + 1>1$. We pick $m$ such that $f(1) + m$ is a prime which gives us $f(m) + 1 = f(1) + m$ or $f(m) - m = f(1) - 1$ for infinitely many $m$. As $f(m) - m\leq f(n) - n$ for all $m\geq n$, we have $f(m) - m$ is a constant or $f(m) + n = f(n) + m$ for all $m,n$ and we are done. $~\square$

We show that both are equivalent to $f \equiv x + c$ for a non-negative integer $c$, which clearly works. First suppose that $f(m) + n \mid f(n) + m$ holds for all $m \le n$. This implies $f(m) + n \le f(n) + m \implies f(m)-m \le f(n)-n$ for all $m \le n$. Define $g(n) = f(n)-n$ so that $g$ is non-decreasing and the condition becomes \[g(m)+m+n \mid g(n) + m+n \implies g(m) + m +n \mid g(n)-g(m).\]Fix $m\in \mathbb{N}$ and consider $g(m) + m +n \mid g(n)-g(m)$ $g(m+1) + m+1 + n \mid g(n) - g(m+1)$ Let $d = g(m+1) - g(m) + 1$ be the difference between the left sides; note that $d>0$. Pick large $n$ so that $d$ divides both left sides. We get \[g(n) \equiv g(m) \equiv g(m+1) \pmod{d}\]which forces $d=1$ and thus $g(m)=g(m+1)$, which applied to all $m$ gives $g$ constant as needed. Now suppose $f(m) + n \mid f(n) + m$ for all $m \ge n$. Fix $n=1$ and let $m=p-f(1)$ for arbitrarily large primes $p$. Then we force $f(p-f(1)) + 1 = p$, so in particular we have infinitely many $X$ such that $f(X) = X + c$ for a constant $c \ge 0$. Fixing $n$ and setting $m=X$ gives \[X+c+n \mid f(n)+X \implies X+c+n \mid f(n) - n - c\]so as $X$ grows big we force $f(n) = n+c$, as desired.

Pretty cool problem - especially the statement We shall deal with both directions seperately. $\textbf{Case 1)}$ $f(m)+n \mid f(n) +m$ for all positive integers $m \geq n$ Let $P(m,n)$ denote the above assertion. We will prove that $f(m+1) = f(m)+1$ for all $m \in \mathbb{N}$ which implies that $f$ is linear giving the desired conclusion. Notice that $f$ is clearly increasing by taking $P(1,n)$. Assume that $f(m+1) - f(m) > 1$ and let $p$ be a prime divisor of $f(m+1) - f(m)$. Now, fix a sufficiently large $n$ such that $$n \equiv - f(m) \equiv -f(m+1) \pmod{p} $$Taking $P(m,n)$ and $P(m+1,n)$ gives us that $$p \mid f(m)+n \mid f(n) + m$$and $$p \mid f(m+1)+n \mid f(n)+m+1$$which is clearly a contradiction as $gcd(f(n)+m,f(n)+m+1) = 1$. $\square$ $\textbf{Case 2)}$ $f(m)+n \mid f(n)+m$ for all positive integers $m \geq n$ We shall once again prove that $f$ is linear. Fix some $n \in \mathbb{N}$ and notice that we can set $f(n)+m$ to be a prime for infinitely many $m \in \mathbb{N}$, for all of which $f(m)-m = f(n)-n = c$ Taking $m$ to be sufficiently large $m \in \mathbb{N}$ such that $f(m) = m+c$ gives us that $$m+c+n \mid f(n)+m$$Furthermore, $$m+c+n \mid m+c+n$$meaning that $$m+c+n \mid f(n)-c-n$$for infinitely many $m \in \mathbb{N}$ with $n$ fixed and therefore $f(n)=n+c$ for all $n \in \mathbb{N}$ as desired. $\blacksquare$

I really hope my solution works. Really cool problem though ! First, I will show $f(m)+n |f(n)+m \forall n \geq m \implies f$ is linear. In fact I will show that $f(k+1)=f(k)+1 $for all k. Choose any $m > k+1.$ We know that $f(k)+m | f(m)+k$ and that $f(k+1)+m | f(m)+k+1$. Since the numerators are coprime, the denominators have to be too. So $f(k)+m$ and $f(k+1)+m$ are coprime for infinitely many values of $m$. Let $|(f(k+1)-f(k))| = s$. Note that $f(k+1) \equiv {b} \pmod{s \times a}$ and $f(k) \equiv{b} \pmod{s \times a}$ for some big enough value of a. Then we can see that $f(k+1) +s \times a \times c - b \equiv{0} \pmod{s \times a}$ and similarly with $f(k) $ where $c$ is again some number big enough, so these two share a common factor $s$ which is a contradiction unless $s=1$. Also note that $f(s)+s+1 | f(s+1)+s$. So if $f(s)=f(s+1)+1$ there’s a problem. So we are done $\blacksquare$. Now I will show the opposite direction. Fix $n=1$ and $m=p-f(1)$ for some large enough prime $p$. Then note that $f(p-f(1))=p-1$. Now set $m=p-f(1)$ to get $p-1+n | f(n)+p-f(1) \implies p-1+n \mid f(n)+p-f(1)-p+1-n \implies p-1+n \mid f(n)+1-f(1)-n$ for large enough $p$. This forced $f(n)=n+f(1)-1$ basically, so we showed $f$ is linear.