Find all functions $f:\mathbb{N}\rightarrow\mathbb{N}$ such that $\gcd(f(m),n) + \text{lcm}(m,f(n)) = \text{lcm}(f(m),n) + \gcd(m,f(n))$

Question

A little functional equation I've been having problems with. How to deal with the greatest common factor and least common multiple functions here? Help much appreciated

Answer 1

As pointed out by JetfiRex in the comments, setting $n = f(m)$ gives us $f(f(m)) = m$, i.e. $f$ is an involution.

Let $k \in \mathbb{N}$ be such that $\text{gcd}(f(1), k) = 1$. Then, setting $n = 1$ and $m = k$ in the equation, we get $f(k) = kf(1)$.

Now, setting $n = 1$ and $m = kf(1)$, we get $f(kf(1)) = (k - 1)f(1) + 1$. Hence $f(f(k)) = (k - 1)f(1) + 1$. Assuming we chose $k > 1$ (e.g. $k > f(1)$ prime as pointed out by Randall), this last equality becomes $f(1) = 1$, since $f$ is an involution.

From $f(1) = 1$ we get $\text{gcd}(f(1), k) = 1$ for all $k \in \mathbb{N}$. Therefore $f(k) = kf(1) = k$ for all $k \in \mathbb{N}$.

Answer 2

I have another method:

Set $n=f(m)$ we have

$$\gcd(f(m),f(m)) + \text{lcm}(m,f(f(m))) = \text{lcm}(f(m),f(m)) + \gcd(m,f(f(m))).$$

So we have $\text{lcm}(m,f(f(m))) =\gcd(m,f(f(m)))$ and thus $m=f(f(m))$.

Set $m$ to $f(m)$ we have

$$\gcd(m,n) + \text{lcm}(f(m),f(n)) = \text{lcm}(m,n) + \gcd(f(m),f(n)).$$

Let $m,n=p,2p$ for prime $p$, we have $$\text{lcm}(f(p),f(2p))-\gcd(f(p),f(2p)) = p.$$

So we have $\gcd(f(p),f(2p))|p$, it is either $\gcd(f(p),f(2p))=1$ or $\gcd(f(p),f(2p))=p$. Supper former, we have $\gcd(f(p),f(2p))=1$ and thus $\text{lcm}(f(p),f(2p))=p+1$. So $f(p),f(2p)$ both are coporime to $p$. Set $m=2p$ and $n=p$ for prime $p$, we have

$$\gcd(f(p),2p) + \text{lcm}(2p,f(p)) = \text{lcm}(f(2p),p) + \gcd(p,f(2p)).$$

So we know that $\gcd(f(p),2p)$ and $\gcd(p,f(2p))$ are same modulo $p$. Since $\gcd(p,f(2p))=1$, and $\gcd(f(p),p)=1$, so $\gcd(f(p),2p)$ is $1$ or $2$. Since that and $1$ are same modulo $1$, we have $\gcd(f(p),2p)=1$. Thus we have $\text{lcm}(2p,f(p))=\text{lcm}(f(2p),p)$. Since $f(2p)$ and $f(p)$ are coprime, this can happen only if $f(2p)=2$ and $f(p)=1$ which contradict to $\text{lcm}(f(p),f(2p))=p+1$. Therefore we know that $f(p)$ and $f(2p)$ are both multiple of $p$.

Let $n=pk$, $m=p$ for prime $m$ and $k\le 1$, we have

$$\gcd(f(p),pk) + \text{lcm}(p,f(pk)) = \text{lcm}(f(p),pk) + \gcd(p,f(pk)).$$

Since $f(p)$ is a multiple of $p$, and also $\text{lcm}(p,f(pk)), \text{lcm}(f(p),pk)$ are multiples of $p$, so $\gcd(p,f(pk))$ is a multiple of $p$, thus $f(pk)$ is a multiple of $p$. Wherefore we can say, if $p|n$, $p|f(n)$.

Now we consider $f(1)$: if $p|f(1)$, we have $p|f(f(1))$ so $p|1$, contradiction. So $f(1)=1$. Let $m=1$ we have

$$\gcd(1,n) + \text{lcm}(1,f(n)) = \text{lcm}(1,n) + \gcd(1,f(n))$$

And thus $f(n)=n$.