Let $S = \{2, 3, 4, \dots\}$ be the set of positive integers greater than 1. Find all functions $f : S \to S$ that satisfy \[ \text{gcd}(a, f(b)) \cdot \text{lcm}(f(a), b) = f(ab) \]for all pairs of integers $a, b \in S$. Clarification: $\text{gcd}(a,b)$ is the greatest common divisor of $a$ and $b$, and $\text{lcm}(a,b)$ is the least common multiple of $a$ and $b$.
Problem
Source: Rioplatense Math Olympiad Level 3, P5 2024
Tags: algebra, functional equation, fe, rioplatense
mijail
06.12.2024 20:47
Solved with @Enigma714 Let $P(a,b)$ be the statement. Lemma 1: $abf(a)f(b)=f(ab)^2$, for all $a,b\in S$, and $af(a)=f(a^2)$ for all $a\in S$.
Multiplying $P(a,b)\times P(b,a)$ and using that $\text{gcd}(m,n)\times \text{lcm}(m,n)=mn$ we get the first result. Then applying $a=b$ we get the second (as we are working with positive integers.
We can find then $f(a^3)^2=f(a^2)f(a^4)=af(a)a^2f(a^2)=a^4f(a)^2 \implies f(a^3)=a^2f(a)$ now consider $P(a,a^2)$ then $$a.\text{lcm}(f(a), a^2)=a^2 f(a) \implies \text{lcm}(f(a), a^2)=af(a) \implies \text{gcd}(f(a),a^2)=a$$Write then $f(a)=ag(a)$ with $(g(a),a)=1$ consider $P(a,f(a))$ so $\text{gcd}(a, f(f(a))) = ag(af(a))$ so must have $g(af(a))=1$ Notice by reeplacing this definition in Lemma 1 we get: Lemma 2: $g(a)g(b)=g(ab)^2$, for all $a,b\in S$. Then in lemma 2 put $b=f(a)$ so $g(a)=1$ this concludes with $f(a)=a$ for any $a \in S$
InterLoop
12.12.2024 23:03
Let $P(a, b)$ denote the assertion into the main equation. $P(a, a)$ gives
$$\gcd(a, f(a)) \cdot \text{lcm}(a, f(a)) = f(a^2) \implies af(a) = f(a^2)$$Now we use the two substitutions $P(f(b), b)$ and $P(b, f(b))$. These substitutions give
$$\gcd(f(b), f(b)) \cdot \text{lcm}(f(f(b), b) = f(bf(b))$$$$\gcd(b, f(f(b))) \cdot \text{lcm}(f(b), f(b)) = f(bf(b))$$Indeed, this means $\gcd(b, f(f(b))) = \text{lcm}(b, f(f(b)))$ and so $b = f(f(b))$ and $f$ is injective. Plugging this into the above two equations, we get
$$f(bf(b)) = bf(b)$$But since $bf(b) = f(b^2)$, we get $f(bf(b)) = f(b^2)$, which means $bf(b) = b^2 \implies \boxed{f(b) = b \forall b}$ which works.