Find all functions $f : \mathbb{N} \rightarrow \mathbb{N}$ for which these two conditions hold simultaneously (i) For all $m,n \in \mathbb{N}$ we have: $$ \frac{f(mn)}{\gcd(m,n)} = \frac{f(m)f(n)}{f(\gcd(m,n))};$$ (ii) For all prime numbers $p$, there exists a prime number $q$ such that $f(p^{2025})=q^{2025}$.
Problem
Source: Kosovo Math Olympiad 2025, Grade 12, Problem 4
Tags: number theory, primes, GCD, functional equation, solve in natural, beautiful
17.11.2024 20:44
Let's nail this. I claim $f(x)=x$ for all $x$ is the only solution. First, taking $(m,n)=1$ we find that $f(mn) = f(m)f(n)/f(1)$. So, it suffices to recover $f$ on prime powers and show $f(1)=1$. To that end, take $m=n=p$ a prime. Then, $f(p^2) = pf(p)$. Now taking $(m,n)=(p^2,p)$ we find $f(p^3) = pf(p^2)=p^2f(p)$. Iterating this, we find $f(p^N) = p^{N-1}f(p)$ for all $p$ prime. This together with item (ii) gives $q=p$ and that $f(p)=p$ for all prime $p$. Lastly, suppose $f(1)>1$ and let $p,q$ be two primes not dividing $f(1)$. Then, taking $m=p$ and $n=q$ gives $f(pq) = f(p)f(q)/f(1) = pq/f(1)$, yielding $f(pq)\notin\mathbb{N}$, a contradiction. So, $f(1)=1$ and $f(n)=n$ for all $n$.
17.11.2024 20:58
Sniped but anyways, really nice. Let $P(x, y)$ denote the given assertion. $P(p^{2024}, p)$ gives: $$q^{2025} = f(p^{2024})\cdot p \implies p \mid q^{2025} \implies p = q \implies f(p^{2025}) = p^{2025}, f(p^{2024}) = p^{2024}$$$P(p^{2023}, p)$ gives $f(p^{2023}) = p^{2023}$, $P(p^{2022}, p)$ gives $f(p^{2022}) = p^{2022}$, and continouing like this, we get $f(p^2) = p^2$. $P(p, p)$ gives $f(p) = p$. Also, $P(p^{2025}, p)$ gives $f(p^{2026}) = p^{2026}$, $P(p^{2026}, p)$ gives $f(p^{2027}) = p^{2027}$, and continuing we get: $$f(p^{\alpha}) = p^{\alpha} \forall \\ \alpha \in \mathbb{N}$$ Assume FTSOC, $f(1) \neq 1$. Consider two distinct primes $r$ and $s$ such that $r, s \nmid f(1)$. $P(r, s)$ gives: $$f(rs)f(1) = rs \implies f(1) \mid rs$$which is a contradiction since $\gcd(f(1), rs) = 1$, so $f(1) = 1$. We now prove $f(x) = x$ for all $x$. Let $x = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdots p_k^{\alpha_k}$. $P(p_1^{\alpha_1}, p_2^{\alpha_2})$ gives $f(p_1^{\alpha_1}\cdot p_2^{\alpha_2}) = p_1^{\alpha_1}\cdot p_2^{\alpha_2}$, $P(p_1^{\alpha_1}\cdot p_2^{\alpha_2}, p_3^{\alpha_3})$ gives $f(p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot p_3^{\alpha_3}) = (p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot p_3^{\alpha_3}$, and continuing like this, we get $f(x) = x$, so we are done.
17.11.2024 22:21
Here is my solution written in Albanian. Warning: IT'S LONG
Attachments:
2025 Kosovo MO 12th grade P4.pdf (363kb)
17.11.2024 23:32
We claim that \[ f(n) = n \quad \forall n \in \mathbb{N} \]is the only solution. Let \( P(x, y) \) denote the assertion. Claim 1: \( f(m^2) = m f(m) \quad \forall m \in \mathbb{N} \) Proof: \( P(m, m) \) gives \[ \frac{f(m^2)}{m} = \frac{f(m)^2}{f(m)} \implies f(m^2) = m f(m) \] Claim 2: \( f(m^\alpha) = m^{\alpha-1} f(m) \quad \forall m, \alpha \in \mathbb{N} \) Proof: We use induction. Base Case: \( f(m^2) = m^{2-1} f(m) \), from Claim 1. Induction Step: Assume \( f(m^\beta) = m^{\beta-1} f(m) \) for some \( m, \beta \in \mathbb{N} \). Then, \[ P(m^\beta, m) \quad \text{gives} \quad \frac{f(m^{\beta+1})}{m} = \frac{f(m^\beta) f(m)}{f(m)} \implies f(m^{\beta+1}) = m f(m^\beta) \] Claim 3: \( f(p^k) = p^k \quad \forall \text{ prime } p \text{ and } k \in \mathbb{N} \) Proof: Note that \[ f(p^{2025}) = p f(p^{2024}) \]\[ = p^2 f(p^{2023}) \]\[ \vdots \]\[ = p^{2024} f(p) \]\[ = q^{2025} \quad \text{where } q \text{ is also a prime.} \]This implies \( p = q \), so \[ f(p^{2025}) = p^{2025} \]\[ f(p) = p \quad \text{and} \quad f(p^{k+1}) = p^{k+1} \] Claim 4: \[ f(n) = \frac{n}{f(1)^{g(n)-1}} \quad \text{where } g(n) \text{ is the number of distinct prime factors of } n. \] Proof: We use induction. First, let \( n = p_1^{a_1} p_2^{a_2} \ldots p_k^{a_k} \) be the unique prime factorization of \( n \). Let us use induction on \( k \). Base case: For \( k = 2 \), we have \[ f\left(p_1^{\alpha}\right) = \frac{p_1^{\alpha}}{f(1)^{1-1}} \quad \text{(by claim 3).} \] Induction: Assume \[ f\left(p_1^{\alpha_1}p_2^{\alpha_2} \dots p_k^{\alpha_k}\right) = \frac{p_1^{\alpha_1} p_2^{\alpha_2} \dots p_k^{\alpha_k}}{f(1)^{k-1}}. \] For \( P\left(p_1^{\alpha_1} p_2^{\alpha_2}\dots p_k^{\alpha_k}, p_{k+1}^{\alpha_{k+1}}\right) \), we have: \[ f\left(p_1^{\alpha_1} p_2^{\alpha_2} \dots p_k^{\alpha_k}, p_{k+1}^{\alpha_{k+1}}\right) = \frac{f\left(p_1^{\alpha_1} p_2^{\alpha_2} \dots p_k^{\alpha_k}\right) f\left(p_{k+1}^{\alpha_{k+1}}\right)}{f(1)}. \] Substituting the induction hypothesis: \[ f\left(p_1^{\alpha_1}, p_2^{\alpha_2}, \dots, p_k^{\alpha_k}, p_{k+1}^{\alpha_{k+1}}\right) = \frac{p_1^{\alpha_1} p_2^{\alpha_2} \dots p_k^{\alpha_k} \cdot p_{k+1}^{\alpha_{k+1}}}{f(1)^{k}}. \] (Here, \( p_{k+1} \) is prime and \( \alpha_{k+1} \in \mathbb{N} \).) Now all we need to do is note that $f(1)$ divides all naturals and hence is equal to $1$. Indeed, \( f(n) = n \) satisfies the two conditions. $\blacksquare$