Let $k$ be a positive integer. Find all functions $f:\mathbb{N}\to \mathbb{N}$ satisfying the following two conditions: • For infinitely many prime numbers $p$ there exists a positve integer $c$ such that $f(c)=p^k$. • For all positive integers $m$ and $n$, $f(m)+f(n)$ divides $f(m+n)$.
Problem
Source: Iran 3rd round 2017 Number theory first exam-P3
Tags: number theory, function
09.08.2017 16:18
We prove by induction that $f(n) = nf(1)$. Let $c_1,c_2,\ldots,$ be the sequence of naturals such that $f(c_i) = p_i^k$. Then one has $$f(c_i - (d+1)) + f(d+1) \mid f(c_i) = p_i^k$$and hence $f(c_i - (d+1)) = p_i^j - f(d+1)$ for some natural number $j < k$. By pigeonhole, there are infinitely many $i$ that gives us the same $j$ and hence we can assume that $j$ is fixed since we can just consider that sequence instead. Similarly, one has $f(c_i - k) = p_i^{j'} - f(k)$ for some fixed natural number $j'$. Now we have $$f(1) + f(c_i - (d+1)) \mid f(c_i - d) \implies p_i^j - f(d+1) + f(1) \mid p_i^{j'} - f(d).$$Let $j' = aj + b$ where $0 \leq b < j$. Then our divisibility condition becomes $$p_i^j - f(d+1) + f(1) \mid (f(d+1) - f(1))^a p_i^b - f(d)$$but since $b < j$ and $a <k$, the RHS is less than the LHS when $p_i$ is large enough which is a contradiction unless the LHS is zero. In which case one has $$(f(d+1) - f(1))^a p_i^b = f(d)$$and so $b = 0$, giving us $(f(d+1) - f(1))^a = f(d)$. On the other hand, one also has $$f(1) + f(d) \mid f(d+1)$$giving us $$(f(d+1) - f(1))^a + f(1) \mid f(d+1).$$Letting $f(d+1) - f(1) = c$, one has $$c^a + f(1) \mid c + f(1)$$which is impossible unless $c^a = c$, in which case either $c = 1$ or $a = 1$. If $c = 1$, then $f(d) = 1$ and $f(1) + f(d-1) \mid f(d)$ is impossible. Thus it must be that $a = 1$ which gives us $f(d+1) = f(d) + f(1)$. By induction, $f(n) = nf(1)$ as desired. Now clearly any function satisfying $f(n) = nf(1)$ satisfies the second condition. For the first condition, it is clear that one must have $f(1) = 1$. Hence the only solution is $f(n) = n$ for all $n \in \mathbb{N}$.
10.08.2017 18:05
Nice problem, but somehow, I still find this problem is easier than P2 (I wasn’t able to solve it, fattypiggy solution is really nice ). Here is my solution: (Actually, it's almost the same as fattypiggy, but anyways) Let say a pair $(c,p)$ satisfy: $f(c)=p^k$ a good pair, from the condition, there are infinitely many good pair. From the condition $f(m)+f(n)|f(m+n)$, we have: $f(m+n)\geq f(m)+f(n)>f(m)$ forall $m,n$, thus $f$: is strictly function, hence injective. Fixed a positive integer $m$. Taking an arbitrary good pair $c>m$, we have: $f(m)+f(c-m)|f( c)=p^k$, thus: $f(m)+f(c-m)=p^l$ for some positive integer less or equal to $k$. Now, consider $(c_n)$, $(p_n)$ are two strictly sequence satisfy this. Thus, we have: $f(m)+f(c_i-m)=p_i^{l_i}$ forall $i$. Apply the second condition: $f(c)+f(c_j-c)|f(c)=p_j^k$, hence: $f(c)+f(c_j-c)=p_j^u$ for some $u\leq k$, hence: $f(c_j-c)=p_j^u-p^k$ Now, since: $f(c_i-m)+f(c_j-c)|f(c_j-m)$, which gives: $p^l-f(m)+p_j^u-p^k|p_j^{l_i}-f(m)$ Write: $l_i=tu+r$ for $r<u$, Note that: $p_j^u\equiv p^k+f(m)-p^l$ $\text{mod}( p^l-f(m)+p_j^u-p^k)$, Hence:$ p^l-f(m)+p_j^u-p_i^k|( p^k+f(m)-p^l)^t.p_j^r-f(m)$ Taking $j\rightarrow+\infty$, $p_j\rightarrow+\infty$, we must have: $r=0, k=l$, thus $k=l$ Thus, forall good pair $c>m$, we have: $f(m)+f(c-m)=p^k$. Using this, this force, there exist infinitely many $c$: $f(m)+f(c-m)=f(m-1)+f(c-m+1)$, thus: $f(m)-f(m-1)=f(c-m+1)-f(c-m)$. Since: $f(c-m)+f(1)|f(c-m+1)$, hence: $f(c-m+1)=kf(c-m)+kf(1)$, Plugging back to the above and taking limit, implies: $f(m+1)=f(m)+f(1)$, an easy induction show $f(n)=nf(1)$. Hence: $p^k=f( c)=cf(1)$, which gives: $f(1)=1$ and: $f(n)=n$, which indeed a solution.
06.01.2018 19:19
fattypiggy123 wrote: which is impossible unless $c^a = c$, in which case either $c = 1$ or $a = 1$. If $c = 1$, then $f(d) = 1$ and $f(1) + f(d-1) \mid f(d)$ is impossible. Thus it must be that $a = 1$ which gives us $f(d+1) = f(d) + f(1)$. By induction, $f(n) = nf(1)$ as desired. You missed a case which $a=0$, it's trivial though.
18.02.2023 13:44