How does one find all $f:\mathbb {Z} \rightarrow \mathbb {Z}$ that satisfies the following: $$f(gcd(x,y))=gcd(f(x),f(y))$$ I had suspected that there would be some results concerning this functional equation but was unable to find any.

It appears that the only solution for $f(x)$ would be $f(x)=cx^r$ for fixed integers $c,r$. However, I was unable to prove or disprove the statement.

Any help would be appreciated.

  • 2
    $\begingroup$ note that if $n|m$ then $f(n)|f(m)$ $\endgroup$ – Jane Jan 29 '16 at 2:38
  • $\begingroup$ Will constant functions (e.g. $f(x)=1, \forall x$) be classified as bad examples? $\endgroup$ – rtybase Feb 2 '16 at 22:29
  • $\begingroup$ @rtybase If you were trying to disprove my conjecture (as has been done below), it would be a bad example, I would think, as they are of the form $f(x)=cx^r$ where $r=0$. As just a example of this kind of function, however, it could be all right, in my opinion. $\endgroup$ – user305063 Feb 3 '16 at 1:03
  • $\begingroup$ See also math.stackexchange.com/questions/2388228/… $\endgroup$ – lhf Oct 20 at 22:09
  1. A combination of two solutions is again a solution. This does not help much with your class of functions, but wait.

  2. Consider any multiplicative function that maps primes to a permutation thereof. Say, $2\mapsto3$, $3\mapsto2$, and the rest of primes map to themselves. This would do as well.

  • $\begingroup$ I'm not very experienced at math(or english), but what does maps primes to a permutation thereof mean? Could you give me a example? $\endgroup$ – user305063 Jan 29 '16 at 9:23
  • $\begingroup$ I did give an example in the very next phrase. Consider a function such that $f(2)=3,\;f(3)=2$, for all other primes $f(p)=p$, and for composite values of argument use the multiplicative property. $\endgroup$ – Ivan Neretin Jan 29 '16 at 9:32
  • $\begingroup$ Oh, I was asking for some other one. For example, is this a multiplicative function that maps primes to a permutation thereof? $f(2)=3,f(3)=5,f(5)=2017,f(2017)=2$ and for all other primes $f(p)=p$? $\endgroup$ – user305063 Jan 29 '16 at 11:08
  • $\begingroup$ Yes, looks like this would work too. $\endgroup$ – Ivan Neretin Jan 29 '16 at 11:12

Don't know that you'll find a "nice" general form.

$f(x) = c x^r$ works, as you noted. But so do the following, and many others.

$$ f(x) = \begin{cases} 1 & \text{if $x$ is odd} \\ 2 & \text{if $x$ is even} \end{cases} $$

$$ f(x) = \text{largest power of a fixed but otherwise arbitrary } p \in \mathbb N \text{ which divides } x $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy