Denote by $\mathbb{Z}^{*}$ the set of all nonzero integers and denote by $\mathbb{N}_{0}$ the set of all nonnegative integers. Find all functions $f:\mathbb{Z}^{*} \rightarrow \mathbb{N}_{0}$ such that: $(1)$ For all $a,b \in \mathbb{Z}^{*}$ such that $a+b \in \mathbb{Z}^{*}$ we have $f(a+b) \geq $ min $\left \{ f(a),f(b) \right \}$. $(2)$ For all $a, b \in \mathbb{Z}^{*}$ we have $f(ab) = f(a)+f(b)$.
Problem
Source: Macedonian TST for IMO 2013 - P3 day 1
Tags: algebra, functional equation, function, number theory
29.03.2021 05:11
We claim any $f$ admits the following form: for some prime $p$ and integer $k\ge 0$, it holds that for any $n$, $f(n)=k\cdot v_p(n)$ where $v_p(n)$ is the largest $\alpha\in\mathbb{N}_0$ such that $p^\alpha \mid n$. Any such $f$ clearly verifies the conditions. We now show any $f$ satisfying the conditions must be of the aforementioned form. Taking $a=b=1$, we find $f(1) = 2f(1)$, yielding $f(1)=0$. Now, taking $a=b=-1$, we find $f(1)=2f(-1)$ which is zero, hence $f(-a) = f(a)$ for all $a$. For this reason we simply restrict our attention to $\mathbb{N}$. Iterating the second identity, we find for every prime $p$ and positive integer $k$, $f(p^k) = kf(p)$. Iterating this even further, we obtain if $n=\prod_{1\le j\le n}p_j^{\alpha_j}$, then $f(n) = \sum_{1\le j\le n} \alpha_j \varphi(p_j)$; which $\varphi$ being the restriction of $f$ onto the primes. Now, if $\varphi=0$ everywhere we are done, hence assume there is a prime $p$ such that $\varphi(p)\ne 0$. Let us now assume $\varphi(\cdot)$ is positive on two distinct primes $p$ and $q$. Consider $a=pq-pq^{p}$ and $b=pq^{p}$. Then $a+b = pq$, forcing $f(ab) = f(p)+f(q)$. Notice, on the other hand, $f(b) = f(p)+pf(q)$ and \[ f(a) = f\left(pq\cdot \left(1-q^{p-1}\right)\right) = f(p)+f(q)+f\left(q^{p-1}-1\right)\ge 2f(p)+f(q). \]Above, we used the fact that $q^{p-1}-1\equiv 0\pmod{p}$ (by Fermat's theorem), hence using the second identity, $f\left(q^{p-1}-1\right)\ge f(p)$. With this \[ f(p)+f(q) = f(a+b) \quad\quad \text{whereas}\quad\quad \min\{f(a),f(b)\} \ge \min\{f(p)+pf(q),2f(p)+f(q)\}. \]This is a contradiction. Hence, $\varphi(\cdot)$ is non-zero on at most one prime, concluding the proof.