<ignore>

Kamran011 wrote: Find all functions $f : \mathbb{N}\rightarrow{\mathbb{N}}$ such that for all positive integers $m$ and $n$ the number $f(m)+n-m$ is divisible by $f(n)$.

already posted

Math-wiz wrote: Kamran011 wrote: Find all functions $f : \mathbb{N}\rightarrow{\mathbb{N}}$ such that for all positive integers $m$ and $n$ the number $f(m)+n-m$ is divisible by $f(n)$.

no your solution is wrong, you can have $g(p-c)=1+c$ here is my solution set $m=1$ so we have $f(n) |n-1+f(1)$ let $p$ be a prime number such that $p>f(1)-1$ set $n=p-f(1)+1$ we get $f(p+1-f(1)) | p \iff f(p+1-f(1))=1 \text{or} p$ if $f(p+1-f(1))=p$ for infinitely many primes numbers $p$ we set $n=p+1-f(1)$ so $p | p+1-f(1)+f(m)-m \iff p | 1-f(1)+f(m)-m$ choosing $p$ big enough we get $f(m)=m+c$ with $c\ge 0$ this function fulfills the condition of the problem If $f(p+1-f(1))=p$ for finitely many numbers $p$ so $f(p+1-f(1))=1$ for all prime numbers $p>C$ set $n=1$ and $m=p+1-f(1)$ with $p>C$ we get $f(1)|p-1$ for all prime numbers $p>C$ If $f(1)=1$ we have $f(p)=1$ for all $p>C$ setting $m=p$ we get $f(n)|n+1-p$ by dirichlet there is inifinitely many prime numbers $q$ congruent to $1$ mod $f(n)$ and infinitely many prime numbers $r$ congruent to $-1$ modulo $f(n)$ $(1)$ setting $p=q$ and $p=r$ we get $f(n)|2$ forall $n \in \mathbb{N}$ if there is an integer $n$ such that $f(n)=2$ if $f(n)=2$ then $f(n)|n$ (set $m=1$) so $n$ is even and setting $m=2k$ so $2|f(2k)+n-2k$ and $n$ is even so $f(2k)=2$ forall positive integers $k$ and $f(2k+1)=1$ else $f(n)=1$ for all postive integers $n$ If $f(1) \neq 1$ using the same argument in $(1)$ we get $f(1)=2$ so $f(p-1)=1$ setting $m=p-1$ and using the same argument as in $(1)$ we get $f(n)|2$ so if there is an integer $n$ such that $f(n)=2$ then setting $m=1$ we get $n$ is odd and for an odd integer $m$ we have $2|f(m)+n-m$ so $f(m)$ is even hence $f(m)=2$ and so $f(2k+1)=2$ for all positive integers $k$ and $f(2k)=1$ so the solutions are $f(n)=n+c$ $f(n)=2$ for odd $n$ and $f(n)=1$ for even $n$ $f(n)=1$ for even $n$ and $f(n)=2$ for odd $n$ $f(n)=1$

Is something wrong? We have $f(m)-m+n\geq f(n)$. So for every integers $m,n$ we have $f(n)-n=f(m)-m$.

mashina wrote: Is something wrong? We have $f(m)-m+n\geq f(n)$. So for every integers $m,n$ we have $f(n)-n=f(m)-m$. $f(m)-m$ might be negative and huge, so you would have $m-f(m)-n\ge f(n)$ for some certain $n$

anyone__42 wrote: mashina wrote: Is something wrong? We have $f(m)-m+n\geq f(n)$. So for every integers $m,n$ we have $f(n)-n=f(m)-m$. $f(m)-m$ might be negative and huge, so you would have $m-f(m)-n\ge f(n)$ for some certain $n$ we know $f(n)+m-n\geq f(m)$ if $f(n)-n\geq f(m)-m$ then change n and m and you get $f(m)-m=f(n)-n$

Let $P(n, m)$ be the assertion $f(n)\mid f(m)-m+n.$ First let's fix $m.$ Choose $n=p+m-f(m),$ where $p$ is a large prime. We see that $$f(p+m-f(m)) \in \{1, p\}.$$ Case 1: Suppose that for some $p$ we have $f(p+m-f(m))=1.$ Now $P(n, p+m-f(m))$ yields $f(n)\mid p-1$ for an arbitrary $n.$ It is an immediate consequence that for any prime $q>p$ it must be true that $f(q+m-f(m))=1$ (just consider $P(q+m-f(m), p+m-f(m))$ )$.$ Thus the assertion $P(n, q+m-f(m))$ implies that $f(n)\mid q-1$ for all $q>p.$ Now if there exists some $n\in \mathbb{N},$ such that $f(n)$ is divisible by an odd prime$,$ or $4\mid f(n),$ it will follow that all primes $q>p$ are congruent to the residue class $1\mod$ the odd prime dividing $f(n)$ or $\mod 4.$ This is of course false, since it's easy to prove that for $k\geq 3,$ there are infinitely many primes $r\not \equiv 1 \pmod k.$ Thus $f(n)\in \{1, 2\}$ $\forall n\in \mathbb{N}.$ Note that $f\equiv 1$ is a solution. Assume that there exists $n$ with $f(n)=2.$ Let $M_1=\{n\mid n\in \mathbb{N}, f(n)=1\}, M_2=\{n\mid n\in \mathbb{N}, f(n)=2\}.$ Now consider $P(n_2, m),$ where $n_2\in M_2.$ This gives us $$2\mid f(m)-m+n_2.$$If $m\in M_2,$ it must be the case that $m\equiv n_2\pmod 2.$ If $m\in M_1,$ it follows $m\not \equiv n_2\pmod 2.$ Therefore one easily obtains $\{M_1, M_2\}=\{2\mathbb{Z}, 2\mathbb{Z}+1\}.$ It is not hard to verify that this is a solution. Case 2: $$f(p+m-f(m))=p \text{ }\text{ }\text{ }\forall p\in \mathbb{P}, p>f(m)-m$$Consider the function $g(n)=f(n)-n.$ We have $g(p+m-f(m))=f(p+m-f(m))-p+f(m)-m=g(m)$ and recalling that $m$ was fixed and $p$ was an arbitrary large prime$,$ we get $g(n)=c=\text{const},$ or in other words $f(n)=n+c$ for infinitely many values of $n.$ Now consider $P(n, k)$ with fixed $k$ and arbitrarily large $n,$ such that $f(n)=n+c.$ We obtain $$n+c=f(n)\mid f(k)-k+n-(n+c)=f(k)-k-c.$$The last expression is constant and therefore it must be zero$,$ namely $f(k)=k+c.$ Since we can fix any $k,$ we easily deduce that $f(k)=k+c$ for all $k\in \mathbb{N}$ and some $c\in \mathbb{Z}_{\geq 0}.$ It is not hard to verify that this is also a solution$.$

We see that $f(a)-a \equiv f(b)-b \pmod{f(b)}$, thus comparing two of these relations we get that $f(x)-f(y) \equiv x-y \pmod{Z}$, whenever $Z$ is in the image of $f$. Thus, we have two cases: Case $1$ $f(x)-f(y)=x-y \forall x,y \in \mathbb{N}$. Then, we get the set of solutions $f(x)=x+c, c \geq 0$ Case $2$ If the previous equality does not hold, then any element $Z$ of the image divides a positive value, thus the image is bounded, so it is finite. Let it be $ \{ a_1,a_2,...,a_l \}$, and define $M=\text{lcm}(a_1,...,a_l)$. If $f(x)=f(y)$ and $x \neq y$, $a_t \mid x-y \forall t \Rightarrow M \mid x-y$. From here, we see that the density of numbers $m$ such that $f(m)=k$, for a fixed $k$, is at most $\frac1M \Rightarrow \frac{l}{M} \geq 1$. However, we clearly have $l \geq M \geq \text{max} \{ a_1,...,a_l \} \geq l$, and equality must hold everywhere, so $\text{lcm}(1,...,l)=l \Rightarrow l \leq 2$. From here, it's pretty easy to get the solutions mentioned above.

Consider set $S=\{f(m)-m | m\in\mathbb{N}\}$. If $|S|=1$ we get $f(n)=n+c$ for all $n\in\mathbb{N}$ for some constant $c$, which indeed works. Now assume $|S|\geq 2$. Pick $2$ distinct number $a,b$ from $S$. So we get $f(n)\mid n+a$ and $f(n)\mid n+b$, for all $n\in\mathbb{N}$. So $f(n)\mid \gcd({n+a,n+b}) \implies f(n)\mid \gcd({n+a,b-a})$. Obviously $\gcd({n+a,b-a})=1$ for infinitely many $n$. So we get $f(n)=1$ for infinitely many $n$. Now let $f(m_0)=1$ for some $m_0$, and let $n=m_0-2$, and plug this ones in originial equation. We get $f(m_0-2)\mid f(m_0)-m_0+(m_0-2) \implies f(m_0-2)\mid 1 \implies f(m_0-2)=1$. So if $f(k)=1$ for some $k>2$, then $f(k-2)=1$. Since $f(n)=1$ for infinitley many $n$, we get at least $1$ of give conditions should hold $(i) f(2t)=1$ for all $t\in\mathbb{N}$, $(ii) f(2t+1)=1$ for all $t\in\mathbb{N}$. $(i)$ From this case we get $f(2r+1)$ divides both $2r+2$ and $2r+4$. So $f(2r+1)\mid 2$ for all $r$. It's easy to see that there can't be $2$ odd numbers $c,d$ such that $f(c)=1$ and $f(d)=2$. So we get $f(n)\equiv 1$ or $f(even)=1$ and $f(odd)=2$. $(ii)$ It's completely same with $(i)$. So all solutions are $\boxed{f(n)=n+c}$, $\boxed{f(n)\equiv 1}$, $\boxed{f(even)=1, f(odd)=2}$, $\boxed{f(odd)=1,f(even)=2}$.