Determine all integers $k$ for which there exists a function $f: \mathbb{Z}_{>0} \to \mathbb{Z}$ such that $f(2023) = 2024$ and $f(ab) = f(a) + f(b) + kf(\gcd(a,b))$ for all positive integers $a$ and $b$.
Problem
Source: Bulgaria EGMO 2023 TST, Day 1, Problem 2
Tags: number theory, greatest common divisor, function
08.02.2023 04:19
Suppose $k$ is a number satisfying the condition. Consider any prime number $p$. We have $f(p^{n+1}) = f(p^n) + f(p) + kf(p),\forall n\in\mathbb Z^+$ $\Rightarrow f(p^n) = \left [(k+1)(n-1) + 1\right] f(p),\forall n\in\mathbb Z^+$. We also have: $f(p^{2m}) = (k+2)f(p^m),\forall m\in\mathbb Z^+$ $\Rightarrow [(k+1)(2m-1) + 1]f(p) = (k+2)[(k+1)(m-1) + 1]f(p),\forall m\in\mathbb Z^+$ Since there exists $p\in\mathcal{P}$ such that $f(p)\neq 0$, then $(k+1)(2m-1) = (k+2)(k+1)(m-1) + k + 1,\forall m\in\mathbb Z^+$ $\Rightarrow k\in \{-1; 0\}$. $\bullet$ $k=0\Rightarrow f(ab) = f(a) +f(b),\forall a,b\in\mathbb Z^+$ $\Rightarrow f(n) = \sum_{p\in \mathcal{P}, p\mid n} v_p(n) f(p)$. Easy to see for all value of $\{f(x) | x\in\mathcal{P}\}$, the function above is satisfied. So we only need to have $2024 = f(2023) = f(7) + 2f(17)$, it is possible. $\bullet$ $k=-1\Rightarrow f(ab) = f(a) + f(b) - f(\gcd(a,b)),\forall a,b\in\mathbb Z^+$ $\Rightarrow f(p^n) = f(p),\forall p\in\mathcal{P}, n\in\mathbb N^*$ $\Rightarrow f(n) = \sum_{p\in\mathcal{P}, p\mid n} \left [f(p) - 1\right] + 1$. Similarly, we see that this function satisfied. Thus, $k\in \{0; -1\}$.
08.02.2023 09:15
1997 Taiwanese MO (It had $f(1997) = 1998$) https://artofproblemsolving.com/community/c6h128912p731007
09.02.2023 03:38
Bug in solution above: how do you know it is not the case that $f(p)=0$ for all prime $p$? As I show below, this case is possible. Nevertheless, the proof still works with a minor fix, I provide mine for completeness. Take $a=2023^{n-1}$ and $b=2023$ to find \[ f\bigl(2023^n\bigr) - f\bigl(2023^{n-1}\bigr) = f(2023)(1+k) \implies f\bigl(2023^n\bigr) = f(2023)\bigl(1+(k+1)(n-1)\bigr). \]Take $n=2\ell$ and compare this with what we get via $a=b=2023^\ell$ to find \[ f(2023)\bigl((k+1)(2\ell-1) +1\bigr) = f(2023)\bigl((k+2)(k+1)(\ell-1)+(k+2)\bigr) \implies k\in\{-1,0\}. \]Case 1. $k=0$. In this case, we have $f(ab)=f(a)+f(b)$. So, we immediately obtain \[ f(n) = \sum_{\substack{p:p\text{ is prime}\\p\mid n}} v_p(n)f(p). \]Finally, it is straightforward to assign $f$ to primes for which $f(2023)=f(7)+2f(17)=2024$. Case 2. $k=-1$. We have $f(ab)= f(a)+f(b)-f({\rm gcd}(a,b))$. Let $f(n) = 2024\bigl(\omega(n)-1\bigr)$, where $\omega(n)$ is the number of (distinct) primes dividing $n$. This $f$ clearly works, concluding the problem. Remark. As you can see, $f(p)=0$ for all prime $p$ is clearly possible for the case $k=-1$.
29.10.2024 19:13
$$P(a, b): f(ab) = f(a) + f(b) + kf(\gcd(a,b))$$Plugging $P(a, a)$: $$f(a^2) = (k+2) f(a).$$Notice that: $$f(a^4) = f(a^2)(k+2) = (k+2)^2 f(a)$$Also: $$f(a^4) = f(a^3)+f(a)+kf(a) = f(a^2)+2f(a)+k f(a) = (3k+4)f(a).$$Equating both of the above equations: $k=0, -1$. Now, we will provide functions $f$ which satisfy the given conditions for the values of $k$: For $k=0$: $f(p_1^{e_1} p_2^{e_2} \cdots ) = e_1 f(p_1) + e_2 f(p_2)+\cdots $ Thus, letting $f(7)=0$ and $f(17)=1012$ works. For $k=-1$: let $g$ be a function mapping from $\mathbb N$ to $\mathbb Z$ for which: $$f(p_1^{e_1} p_2^{e_2} \cdots ) = g(p_1)+g(p_2)+\cdots.$$Here we can let $g(17)=2024$ and for all primes $p \neq 17$: $g(p) = 0$ (we can do this thing in many other ways too ).
07.11.2024 09:40
Lol, how has no one noticed so far (and in the Taiwan thread) that for $k=-1$ the constant function (here $2024$) works??
07.11.2024 16:24
Assassino9931 wrote: Lol, how has no one noticed so far (and in the Taiwan thread) that for $k=-1$ the constant function (here $2024$) works?? To be honest, I realised it few minutes after I completed the solution typing and didn't wanted to mention it further (I should have been more specific with the sentence "we can do this thing in many other ways too" I think ).
07.11.2024 16:26
Everyone on AoPS: spamming reload on the contests and program thread to get their score These 6 guys: Da-Da-Da, a GCD Fe...