Find all functions $f: \mathbb{N} \to \mathbb{N}$ such that for all $m,n \in \mathbb{N}$ holds $f(mn)=f(m)f(n)$ and $m+n \mid f(m)+f(n)$ .
Problem
Source: Turkey IMO TST 2016 P5
Tags: function, number theory, functional equation, Divisibility
10.04.2016 19:49
The answer is $f(x)=x^k$ for all $x\in \mathbb N$, where $k$ is an odd positive integer. Throughout the solution, we'll denote $f(mn)=f(m)f(n)$ as $(*,m,n)$ and $m+n \mid f(m)+f(n)$ as $(**,m,n)$. $(*,1,1)$ gives $f(1)=1$. Claim 1: $f(2)=2^k$, and $k$ is an odd positive integer. Proof of Claim 1: Assume the contrary that for an odd prime $p$, $p\mid f(2)$. Then by $*$, we get $p\mid f(x)$ for all $x$ even. Then since $p-1$ is even, we get $p\mid f(p-1)$. Now $(**,p-1,1)$ gives $p-1+1\mid f(p-1)+f(1)\Longrightarrow p\mid f(1)$. Contradictory to $f(1)=1$. This proves $f(2)=2^k$. Now $(**,2,1)$ gives $2+1\mid f(2)+1\Longrightarrow 3\mid 2^k+1\Longrightarrow k$ is odd. This proves Claim 1. $\blacksquare$ Claim 2: $f(p)=p^m$ for any odd prime $p$. Proof of Claim 2: Assume the contrary that for another prime $q\neq p$, $q\mid f(p)$. Then by $*$, we get $q\mid f(x)$ for all $x$ which are multiples of $p$. We know there is a multiple of $p$ which gives $-1$ as a residue when divided by $q$. Let that multiple of $p$ be $px$, i.e, $px\equiv-1\pmod q$. Now $(**,px,1)$ gives $px+1\mid f(px)+f(1)$ and since we know $q\mid px+1$ and $q\mid f(px)$, this gives $q\mid f(1)$. Contradictory to $f(1)=1$. This proves Claim 2. $\blacksquare$ Claim 3: If $f(2)=2^k$ and $f(p)=p^m$ for an odd prime $p$, then $k=m$. Proof of Claim 3: Assume the contrary that $k\neq m$. Then $c=|k-m|>0$. Take any positive integer $a$. By $*$, we know $f(2^a)=2^{ak}$. $(**,2^a,p)$ gives $2^a+p\mid f(2^a)+f(p)\Longrightarrow 2^a+p\mid 2^{ak}+p^m\Longrightarrow 2^a+p\mid 2^{ak}+p^k-p^k+p^m$. Since $k$ is odd, we have $2^a+p\mid 2^{ak}+p^k$, which means $2^a+p\mid p^m-p^k\Longrightarrow 2^a+p\mid p^c-1$ since $gcd(2,p)=1$. Now notice that we got $2^a+p\mid p^c-1$ for all positive integers $a$. But if we take $a$ large enough, clearly this will be false. Contradiction. Then $c=|k-m|=0$. This proves Claim 3. $\blacksquare$ So, we have proved $f(p)=p^k$ for all primes $p$, where $k$ is an odd integer. By $*$, this means $f(x)=x^k$ for all positive integers $x$, as desired. This completes the proof. $\blacksquare$
11.04.2016 01:47
I did it slightly differently.
14.04.2016 11:44
Note that $f(x)=x^{2k+1}$ with fixed $k\in \mathbb{N}\cup \{0\}$ respects the hypothesis; we'll prove that this is the only type of function. As $f(1)=f(1)^2$, we get $f(1)=1$. Note that $p|f(2)f \left ( \dfrac{p-1}{2} \right )+1$ for any odd prime $p$, so there is no odd prime $p$ dividing $f(2)$. Obviously, $f(2)\ne 1$ as $2+2$ does not divide $1+1$, thereby $f(2)=2^{\alpha}$. Inductively, $f(2^k)=2^{k\alpha}$. As $2+4|2^{\alpha}+4^{\alpha}$, we get that $\alpha$ is odd. Fix $n\in \mathbb{N}$. Then $n+2^k|f(n)+2^{k\alpha}$ for any $k\ge 1$. But $n+2^k|n^{\alpha}+2^{k\alpha}$, hence $n+2^k|f(n)-n^{\alpha}$. This happens for any $k\ge 1$, hence $f(n)=n^{\alpha}$.
11.08.2018 19:05
Nice problem. The answer is $\boxed{f(x)=x^a}$, where $a$ is an odd positive integer. Clearly, for $f(x)=x^{a}$ where $a$ is odd suffices, as $f(x^{mn})=f(x^m)f(x^n)$ and by the lemma $a+b|a^k+b^k$ for odd $k$, we see that clearly the described function works. I now prove that these are all the solutions. Observe $f(1)=f(1)^2$ so, $f(1)=1$. I now present the following lemma: Lemma: $f(2^{a})=f(2)^{a}$ Proof We proceed by induction. Observe for $a=1$, this is true. Assume for $a=n$ the statement is true. Then $f(2^{n+1})=f(2)f(2^{n})=f(2)^{n+1}$ as desired.\ Now let $f(2)=2^{a}(2r+1)$ where $a=v_{2}(f(2))$ and $r$ is a nonegative integer. Then, we have $$1+2r \mid 1+f(2)f(r)=1+2^{a}(2r+1)f(r)$$which gives us $1+2r \mid 1$ implying $r=0$. This gives us $f(2)=2^{a}$. I now claim that $a$ is odd. $2+1 \mid 2^a+1$ thus, $a$ is odd. Now we have $x+2^{k} \mid f(x)+2^{ak}$ and $x+2^k \mid x^a+2^{ak}$ where $a$ is odd. Subtracting gives us $x+2^{k} \mid f(x) -x^a$ where $a$ is odd. Fixing $x$ and letting $k$ vary, we get $f(x)=x^a$ for an odd $a$. $\blacksquare$
04.01.2019 21:30
realquarterb wrote: Nice problem. The answer is $\boxed{f(x)=x^a}$, where $a$ is an odd positive integer. Clearly, for $f(x)=x^{a}$ where $a$ is odd suffices, as $f(x^{mn})=f(x^m)f(x^n)$ and by the lemma $a+b|a^k+b^k$ for odd $k$, we see that clearly the described function works. I now prove that these are all the solutions. Observe $f(1)=f(1)^2$ so, $f(1)=1$. I now present the following lemma: Lemma: $f(2^{a})=f(2)^{a}$ Proof We proceed by induction. Observe for $a=1$, this is true. Assume for $a=n$ the statement is true. Then $f(2^{n+1})=f(2)f(2^{n})=f(2)^{n+1}$ as desired.\ Now let $f(2)=2^{a}(2r+1)$ where $a=v_{2}(f(2))$ and $r$ is a nonegative integer. Then, we have $$1+2r \mid 1+f(2)f(r)=1+2^{a}(2r+1)f(r)$$which gives us $1+2r \mid 1$ implying $r=0$. This gives us $f(2)=2^{a}$. I now claim that $a$ is odd. $2+1 \mid 2^a+1$ thus, $a$ is odd. Now we have $x+2^{k} \mid f(x)+2^{ak}$ and $x+2^k \mid x^a+2^{ak}$ where $a$ is odd. Subtracting gives us $x+2^{k} \mid f(x) -x^a$ where $a$ is odd. Fixing $x$ and letting $k$ vary, we get $f(x)=x^a$ for an odd $a$. $\blacksquare$ You have simply copy pasted the solution from Number Theory Concepts and problems
02.10.2021 14:45
We will prove that $f(p)=p^c$ ($c$ is odd positive integer) for all primes $p$ which implies $f(n)=n^c$ for odd positive integer $c$ from the first condition. From the first condition $m=1 \implies f(1)=1$. From the second condition $m=n=p \implies p|f(p)$. Assume that $q|f(p)$ for $p\neq q$ primes numbers. Then from Bezout's Lemma there exists infinitely many integers $(x,y)$ such that $qx+py=1$. Take a $(x,y)$ such that $x>0$ and $y<0$. $$q|qx=qx-p(-y)+p(-y)|f(qx-p(-y))+f(p(-y))=1+f(p)f(-y)$$So $q|1$, contradiction. Thus $f(p)=p^{g(p)}$ for all primes $p$. Assume that there exists primes $(p,q)$ such that $g(p)\neq g(q)$. From the first condition $f(r^l)=f(r)^l$ for a prime $r$. From the second condition, $p^m+q^n|f(p^m)+f(q^n)=f(p)^m+f(q)^n=p^{g(p)m}+q^{g(q)n} \implies p^m+q^n|p^{g(p)m}\pm p^{g(q)m}$. For large enough n, we have contradiction. Thus $f(p)=p^c$ for all $p$. From the second condition, $p+1|p^c+1 \implies c$ is odd. Thus $f(n)=n^c$ where $c$ is an odd positive integer and it satisfies both conditions.
06.02.2022 12:38
Claim:$f(p)=p^k$ $k$ is odd number.($p$ -is prime number.) Proof:If exist $q$ prime number such that $q|f(p)$ and $(p,q)=1$ $f(pk) =f(p)f(k)\implies q|f(pk)$ Exist $k \implies q|pk+1 \implies q|pk+1|f(pk)+ 1 \implies q|1$ Contradiction. $f(p)=p^k \implies f(p^m)=p^{km}$ any positive integer $m$ Remaining easy.$\blacksquare$.
06.02.2022 12:39
Indian national math olympiad 2018p6
10.02.2022 09:12
Solved with quirtt and OlyMan pretty much an year ago. We will show that $f(x)=x^k$ for any odd $k$ is the only solution. It's validity can be checked easily. Denote the assertion of $f(mn)=f(m)f(n)$ by $\spadesuit(m,n)$ and assertion of $m+n \mid f(m)+f(n)$ by $\clubsuit(m,n)$. One can quickly obtain that $f(1)=1$ from $\spadesuit(1,n)$. The next major claim of ours will be Claim: $f(2)=2^k$ for any odd $k$. Proof: We will show that only odd divisor of $f(2)$ is 1. Assume that there is some odd prime divisor of $f(2)$. Let that prime divisor be $\alpha$. It is easy to observe that $f(2) \mid f(2x)$ for any positive integer $x$ with $\spadesuit(x,2)$. $\clubsuit(\alpha-1,1)$ and our small observation gives \begin{align*} \alpha \mid f(\alpha-1) +1 \\ f(2) \mid f(\alpha-1) \end{align*}This sets up the required. As $\alpha$ divides two consecutive numbers(namely $f(\alpha-1)$ and $f(\alpha-1)+1$) therefore $\alpha$ must be 1. For showing that $k$ is odd, from $\clubsuit(2,1)$ gives $3 \mid 2^k+1$ which forces $k$ to be odd. $\square$ The finishing from here is quite nice. From $\spadesuit$, one can induct to get $f(2^d)=2^{kd}$. $\clubsuit(m,2^d)$ gives \begin{align*} 2^d+m \mid f(m)+2^{kd} \tag{1} \end{align*}By a well known theorem, $m+2^d \mid m^k +2^{dk}$ for any odd $k$. Subtracting this from $(1)$, we get \begin{align*} m + 2^d \mid f(m) -m^k \end{align*}for some odd $k$. Taking $d$ to sufficiently large, we can force $f(m)-m^k=0$ ending the solution. $\blacksquare$
23.07.2022 05:44
The answer is $f(n) = n^k$ for odd positive integers $k$, which obviously work. The key is proving $f(2) = 2^k$. In particular, let $f(2) = 2^k(2m+1)$ for nonnegative integers $k, m$. Then $$2m+1 \mid 1+f(2)f(m) = 1+2^k(2m+1)f(m)$$implies $m=0$, which implies $f(2) = 2^k$. Furthermore, $$6 \mid f(2) + f(4) = 2^k+4^k,$$so $k$ is odd. The first condition yields $f(2^m) = 2^{mk}$ for all positive integers $m$. But then $$n+2^m \mid f(n) + 2^{mk} \text{ and } n+2^m\mid n^k + 2^{km} \implies n+2^m \mid n^k - f(n).$$Letting $m$ vary, $n^k - f(n)$ has infinitely many positive divisors, so $f(n) = n^k$ for all positive integers $n$.
07.04.2023 13:49
10.12.2023 13:39
Turkey TST 2016 wrote: Find all functions $f: \mathbb{N} \to \mathbb{N}$ such that for all $m,n \in \mathbb{N}$ holds $f(mn)=f(m)f(n)$ and $m+n \mid f(m)+f(n)$ . Clearly, $f(n)=n^k$ works for odd $k$.We now show these are the only solutions. Let $f(2)=2^t(2s+1)$ $1+2s|f(1)+f(2s)=1+f(2)f(s)$ therefore $s=0$ and $f(2) = 2^t$ Claim 1:$t$ is odd
Claim 2:$f(m)=m^t$ for odd $t$