# A Problem about the G.C.D.

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.

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.