$\mathbb{N}$ is the set of positive integers. Determine all functions $f:\mathbb{N}\to\mathbb{N}$ such that for every pair $(m,n)\in\mathbb{N}^2$ we have that: \[f(m)+f(n) \ | \ m+n .\]
Problem
Source:
Tags: function, induction, number theory, prime numbers, number theory proposed
24.09.2010 20:38
See this for a generalisation.
24.09.2010 21:19
Let $P(m,n)$ be the assertion that $f(m)+f(n)|m+n$. $P(1,1)\implies 2f(1)|2 \implies f(1)=1$ $P(m,1)\implies f(m)+1|m+1 \implies f(m)\le m\ \forall \ m$ Let $p$ be a prime number. $P(p-1,1)\implies f(p-1)+1|p \implies f(p-1)+1=p$ since $f(p-1)+1>1$. Thus $f(p-1)=p-1$. Now $P(p-1,p)\implies p-1+f(p)|p-1+p$ $\ \implies p-1+f(p)|p-1+p-(p-1+f(p))=p-f(p)$ Now since $p\ge f(p)$ we have $p-f(p)\ge 0$. Suppose $p-f(p)\not= 0$. Then since $p-1+f(p)|p-f(p)$ we have $p-1+f(p)\le p-f(p)$. This means that $2f(p)\le 1$, a contradiction. Thus $f(p)=p$ for all primes $p$. Let $n$ be an arbitrary positive integer. If $n$ is prime then $f(n)=n$. Otherwise let an arbitray prime greater than $n$ be $p_n$. Then $P(n,p_n-n)\implies f(n)+f(p_n-n)|p_n$ But since $p_n$ is prime we have $f(n)+f(p_n-n)=p_n\implies f(n)=p_n-f(p_n-n)$. Now $P(n,p_n)\implies f(n)+p_n|n+p_n\implies$ $ p_n-f(p_n-n)+p_n|p_n+n\implies p_n-f(p_n-n)+p_n\le p_n+n$. From the last inequality it follows $p_n\le f(p_n-n)+n \le p_n-n+n=p_n$. Hence $f(p_n-n)=p_n-n$ i.e. $f(n)=n$ for all $n$ since $p_n-n$ with $n$ arbitrary covers $\mathbb{N}$. Hence the only solution is $f(n)=n$.
26.09.2010 08:22
Or we could do it simply by this... (almost in the same method as in IMO SL 2004 N3) From above post, if p is a prime, then f(p-1) = p-1 f(m) + f(n) | m+n => f(m)+f(n) | m + f(n) +n - f(n) Put m = p-1 Then f(p-1)+f(n) | p-1 + f(n) + (n - f(n)) => p-1 + f(n) | p-1 + f(n) + (n - f(n)) => p-1 + f(n) | (n - f(n)) (*) Now fix n and vary p (p prime) Since there are infinitely many prime numbers, (*) holds for infinitely many p. Thus n - f(n) = 0 and hence f(n) = n for all n
26.09.2010 10:32
Obviously $f(x)\le x$ for $x\in \mathbb N$ Now let $f(m)=m-k,f(n)=n-l$ with $0<k<m,l<n$ then $f(m)+f(n)|m+n$ and $m+n-(k+l)$.so it divides $k+l$ too.Now repeating this we find it can simultaneously hold for positive $k,l$.So $f(m)=m$
04.04.2012 15:30
i used induction.for m=1 its obvious that f(1)=1.now suppose for all positive integers m=1,2,...,n-1 ,f(m)=m.we want to prove f(n)=n.according to Chebyshev's theorem there is a prime number p such that n<p<2n.so 0<p-n<n . using induction assumption we have: f(p-n)=p-n f(n)+f(p-n)|n+(p-n)=p since p is prime: f(n)+f(p-n)=p so f(n)+p-n=p and finally we have f(n)=n.
02.01.2020 13:31
17.04.2020 12:22
This reminds me of APMO 2019 P1
17.04.2020 13:16
easy to prove with induction if f(n)=n then f(n)+f(n+1) | 2n+1 so n+f(n+1) | 2n+1 but the only divisor of an odd number 2n+1 greater than n is 2n+1 so we get n+f(n+1)=2n+1 subtracting n and we are done