Let $f$ be a non-zero function from the set of positive integers to the set of non-negative integers such that for all positive integers $a$ and $b$ we have $$2f(ab)=(b+1)f(a)+(a+1)f(b).$$Prove that for every prime number $p$ there exists a prime $q$ and positive integers $x_{1}$, ..., $x_{n}$ and $m \geq 0$ so that $$\frac{f(q^{p})}{f(q)} = (px_{1}+1) \cdot ... \cdot (px_{n}+1) \cdot p^{m},$$where the integers $px_{1}+1$,..., $px_{n}+1$ are all prime. Proposed by Nikola Velov
Problem
Source: 2023 Macedonian Balkan Math Olympiad TST Problem 4
Tags: algebra, functional equation
23.04.2023 21:43
First, I think one must assume $f$ is not identically zero: $f\equiv 0$ enjoys the given condition, while $f(q^p)/f(q)$ is not defined for this function. Note that if $f$ is not identically zero, then it is clear there is a prime $q$ so that $f(q)>0$. Next, we show for any $q\in\mathbb{N}$ and $n\ge 1$, $f(q^n)=(q^{n-1}+\cdots+1)f(q)$. For $n\in\{1,2\}$ this is clear, so assume $f(q^{n-1}) = (q^{n-2}+\cdots+1)f(q)$. Taking $a=q^{n-1}$ and $b=q$, we get \[ 2f(q^n) = (q^{n-1}+1)f(q) + (q+1)(q^{n-2}+\cdots+1)f(q) = f(q)\left(q^{n-1}+1 + \frac{q^{n-1}-1}{q-1}(q+1)\right), \]which upon rearranging yields my claim. So, we get in particular \[ \frac{f(q^p)}{f(q)} = \frac{q^p-1}{q-1}, \]assuming $f(q)\ne 0$. Take now $q$ to be any prime for which $f(q)>0$. We inspect prime divisors of $(q^p-1)/(q-1)$. Take any such $r$ and let $d$ be the smallest positive integer for which $r\mid q^d-1$. We get $d\mid p$ and $d\mid r-1$. From the first, $d\in\{1,p\}$. From the second, we get $r\equiv 1\pmod{d}$. So, either $d=1$, in which case we get $r=p$, or $r\equiv 1\pmod{p}$. Namely, any prime divisor of $f(q^p)/f(q)$ is either equal to $p$ or congruent to one modulo $p$, which yields the conclusion. Remarks. (1) $f$ must be non-zero. (2) I assume $x_i$'s need not be distinct. (3) Isn't it the case that the result holds for pretty much all $q$ with $f(q)>0$? Let me know if I am missing something.
23.04.2023 23:23
@above Awesome solution! Yes, it is specified in the problem that the function is non-zero. Also, the $x_i$'s do not have to be distinct, and yes, this can be generalized to all $q$ such that $f(q)>0$. A related question: is it possible to find all functions which satisfy the equation?
24.04.2023 17:27
steppewolf wrote: A related question: is it possible to find all functions which satisfy the equation? Yes, it is. Let $\mathcal{A}$ be set of primes for which $f(p)\ne 0$ and $\mathcal{B}=\text{set of remaining primes}$. As @grupyorum wrote, for all $q\in \mathcal{A}$ $f(q^{n}) = (q^{n-1}+\cdots+1)f(q)$ holds. Also $f(q^n)=0$ for all $q\in \mathcal{B}$. Now take $p\in \mathcal{A}$ and $q\in \mathcal{B}$. We have $\frac{(q+1)^2 f(p)}{2}=(q+1)f(pq)+(pq+1)f(q)=2f(pq^2)=(q^2+1)f(p) \implies q^2+1=2q \implies q=1$ which is contradiction. So, one of $\mathcal{A}$ and $\mathcal{B}$ is empty. If $\mathcal{A}$ is empty, then obviously, $f\equiv 0$ which is solution. Now assume $\mathcal{B}$ is empty. Take $2$ distinct primes $p$ and $q$. Let $f(p)=c(p-1)$ where $c$ is some rational number. Double-counting $f(p^2q)$ gives that $f(q)=c(q-1)$ for all prime $q$. So, $f(2)=c$ which means $c$ is non-negative integer. If $c=0$ we again get $f\equiv 0$. If $f\ne 0$, then we can easily prove that $f(n)=c(n-1)$ for all $n$ using induction on number of distinct prime diviors of $n$. Edit: Also we can verify that $f(1)=0$ by just plugging $b=1$ in equation. So, the only solution is $f(n)=c(n-1)$ for some non-negative integer $c$.
02.05.2023 15:56
$4f(abc)=2((a+1)f(bc)+(bc+1)f(a))=(a+1)(b+1)f(c)+(a+1)(b+1)f(b)+2(bc+1)f(a)$. Swapping $a,c$ we get $(a+1)(b+1)f(c)+2(bc+1)f(a)=(c+1)(b+1)f(a)+2(ba+1)f(c)$. Simplifying, $(a-1)f(c)=(c-1)f(a)$. (by taking $b=2$, or just taking out the factor of $b-1$) Hence $f(a)=k(a-1)$ for constant $k$. This proof works over $\mathbb{Q},\mathbb{R}^+$, and any other multiplicative group you can think of. Also easily generalisable to $f(ab)=g(a)f(b)+g(b)f(a)$ (with some constraints).