In my Google+ inbox I find a lot of interesting stuff about mathematics (besides some boring misunderstandings, but that is another story). Here is a problem. What mappings f from the natural numbers to the natural numbers have the property that

\(\text{gcd}(n,m) = \text{gcd}\left(f(n),f(m)\right) \qquad\text{ for all } n \ne m,\)

where gcd is the greatest common divisor. Clearly, f(n)=n has this property. But since we are not allowed to enter n=m into the equation, the problem gets surprisingly difficult.

So here is a proof that f(n)=n for all n. First we have

\(n = \text{gcd}(n,n^2) = \text{gcd}\left(f(n),f(n^2)\right)\)

from which we conclude that n is a divisor of f(n) for all n. We write that as

\(n \,|\, f(n) \qquad\text{ for all } n.\)

Next, we take n and a such that f(n)=an, and we take b such that f(pa)=pab. p can be any prime that does not divide n or a. It is just there so that pa is different from n. Note that a and b exist by our result that n|f(n) for all n. Then

\(\text{gcd}(n,a) = \text{gcd}(n,pa) = \text{gcd}(f(n),f(pa)) = \text{gcd}(na,pab).\)

Since a divides the right hand side, it must also divide the left hand side. Thus

\(a = \dfrac{f(n)}{n} \,|\, n\)

or

\(f(n) \,|\, n^2 \qquad\text{ for all }n.\)

Now we take a fresh look at the equation

\(n = \text{gcd}(n,n^2) = \text{gcd}(f(n),f(n^2)). \)

Since

\(n \,|\, f(n) \,|\, n^2 \,|\, f(n^2)\)

the right hand side can only be equal to n, if f(n)=n. This is our claim.