Let $\mathbb{N}_{\geqslant 1}$ be the set of positive integers. Find all functions $f \colon \mathbb{N}_{\geqslant 1} \to \mathbb{N}_{\geqslant 1}$ such that, for all positive integers $m$ and $n$: \[\mathrm{GCD}\left(f(m),n\right) + \mathrm{LCM}\left(m,f(n)\right) = \mathrm{GCD}\left(m,f(n)\right) + \mathrm{LCM}\left(f(m),n\right).\] Note: if $a$ and $b$ are positive integers, $\mathrm{GCD}(a,b)$ is the largest positive integer that divides both $a$ and $b$, and $\mathrm{LCM}(a,b)$ is the smallest positive integer that is a multiple of both $a$ and $b$.
Problem
Source: 2021 Francophone MO Juniors p4
Tags: number theory, greatest common divisor, least common multiple, functional equation, functional, Francophone
Ainulindale
04.04.2021 06:12
Huh. As usual, let $P(m,n)$ denote the given assertion.
Only the identity function works; this is easy to verify.
$P(kf(1),1)$ implies that $1+kf(1) = f(1) + f(kf(1))$, so for each positive integer $k$, $$f(kf(1))=(k-1)f(1)+1.\qquad (\dagger)$$In particular, $f(f(1))=1$, so $P(f(1),n)$ gives $$1+\text{lcm}(f(1),f(n)) = \gcd(f(1),f(n)) + n. \qquad(\ddagger)$$
Now suppose $f(1)>1$. Then by Dirichlet's theorem, there exists a prime $p$ congruent to $1\pmod{f(1)}$, so from $(\dagger)$, we know $f(a)=p$ for some positive integer $a$. Note that $\gcd(p,f(1))=1$ and $\text{lcm}(p,f(1))=pf(1)$, so by putting $n=a$ in $(\ddagger)$ we obtain $1+pf(1) = 1+a$, implying $f(pf(1))=p$. It now follows from $(\dagger)$ that $(p-1)f(1)+1=p$, giving $f(1)=1$, contradicting our assumption. Thus we must have $f(1)=1$.
$(\dagger)$ then becomes $f(k)=k$ for each positive integer $k$, so the identity function is indeed the only one.
P1kachu
04.04.2021 07:53
Let $f(1)=c$.
$P(1,n): \gcd(c,n)+\mathrm{lcm}(1,f(n))=\gcd(1,f(n))+\mathrm{lcm}(c,n)$
$\implies f(n)=1+\mathrm{lcm}(c,n)-\gcd(c,n)$
Suppose that $c>1$, then $f(c-1)=c(c-1)$ and $f(c(c-1))=(c-1)^2$
$P(c-1,c(c-1)): \gcd(c(c-1),c(c-1))+\mathrm{lcm}(c-1,(c-1)^2)=\gcd(c-1,(c-1)^2)+\mathrm{lcm}(c(c-1),c(c-1))$
$\implies c(c-1)+(c-1)^2=c-1+c(c-1)$
$\implies c=2$
This means $f(n)=2n$ for all odd $n$ and $f(n)=n-1$ for all even $n$. However this does not work, for say $P(4,6)$.
Therefore only $c=1$ is allowed which give $\boxed{f(n)=n}$.
bora_olmez
08.04.2021 15:33
My solution at the competition has not been posted yet, though it is similar to the previous post; but I guess I'll post it anyways.
First of all, the identity, $f(x) = x$ trivially satisfies the condition.
Let $P(m,n)$ denote the given assertion as usual.
$P(m,f(m))$ gives us that $f(f(m)) = m$ meaning that $f$ is involutive.
Now, the main idea in my solution is a "clever substitution", namely $P(1,f(2))$.
This gives us that $lcm(f(1),f(2)) - gcd(f(1),f(2)) = 1$ meaning that either $f(1) = 1, f(2) = 2$ or $f(1) =2, f(2) =1$ because $lcm(x,y)-gcd(x,y) = 1$ iff $x,y$ is a permutation of $1$ and $2$.
Case 1) $f(1) = 2$
Looking at $P(1,n)$, we get that $f(n) = 2n$ for all odd $n$ and $f(n) = n -1$ for all even $n$ which contradicts the fact that $f$ is involutive.
Case 2) $f(1)=1$
Looking at $P(1,n)$ we get that $f(n)=n$ for all $n \in \mathbb{N}$ which is indeed a solution.
hakN
08.04.2021 15:54
Let $P(m,n)$ be the assertion.
$P(m,1)\implies 1 + \text{lcm}(m,f(1)) = \text{gcd}(m,f(1)) + f(m)$. $(1)$
So we have $f(m)=mf(1)$ for all integers $m$ that are coprime to $f(1)$.
Also plugging $m=f(1)$ into $(1)$, we see that $f(f(1))=1$.
$P(f(1),n)\implies 1 + \text{lcm}(f(n),f(1)) = \text{gcd}(f(n),f(1)) + n$. $(2)$
Again choosing $n$ that is coprime to $f(1)$, we have $f(n)=nf(1)$ and $(2)$ gives us
$1 + nf(1) = f(1) + n \implies n(f(1) - 1) = f(1) - 1$ but this can hold for infinitely many $n$ if and only if $f(1)=1$.
So we get $\boxed{f(n)=n \forall n \in \mathbb{N}}$ which clearly satisfies the condition.
L567
04.05.2021 13:15
My solution looks different from all of the above (Although somewhat similar to #3), so I'll post it. Let $P(m,n)$ denote the given assertion and let $f(1) = c$ With $P(1,n)$, we get that $f(n) = \text{lcm}(c,n) - \text{gcd}(c,n) + 1$ So, for sufficiently large $p$, we have that $f(p) = cp$ Now, for each $n$, we can pick a prime $p$ such that $p$ is coprime with $n$ as well as $f(n)$. So, $P(p,n)$ gives that $\text{lcm}(c,n) - f(n) = \frac{\text{gcd}(c,n) - 1}{p}$ and since this holds for infinitely many $p$, we have that $\text{gcd}(c,n) = 1$ for all $n$ So, this implies that $c = 1$ and so we have that $f(n) = n$ for all $n$
MatBoy-123
27.09.2021 07:55
parmenides51 wrote: Let $\mathbb{N}_{\geqslant 1}$ be the set of positive integers. Find all functions $f \colon \mathbb{N}_{\geqslant 1} \to \mathbb{N}_{\geqslant 1}$ such that, for all positive integers $m$ and $n$: \[\mathrm{GCD}\left(f(m),n\right) + \mathrm{LCM}\left(m,f(n)\right) = \mathrm{GCD}\left(m,f(n)\right) + \mathrm{LCM}\left(f(m),n\right).\] Note: if $a$ and $b$ are positive integers, $\mathrm{GCD}(a,b)$ is the largest positive integer that divides both $a$ and $b$, and $\mathrm{LCM}(a,b)$ is the smallest positive integer that is a multiple of both $a$ and $b$. My solution - We claim that the answer is $f(m) = m$ for all natural $m$. If a prime $p$ doesn't divide $f(1)$ , then from $P(p,1)$ we get $f(p) = pf(1)$ , and if a prime $q \mid f(1)$ , then from $P(q,1)$ we get $f(q) = f(1)-q+1$ , So $f(p) = pq+pf(q) -p$ , now as there exist infinite primes not dividing $f(1)$ , choose a $r > max (f(1) - q +1 )_{q \mid f(1)}$ , and let $s$ be a prime dividing $f(1)$ , so from $P(r,s)$ , we got $r+s = rs+1$ , a contradiction , so no prime divide $f(1)$ so $f(1)=1$ , now from $P(m,1)$ , we got desired conclusion. $\blacksquare$