Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Okay, now I really need real help, maybe the task is not too heavy but I do not know the easy way to solve this. Let´s start with the problem, now.

Suppose that we have some function $f: \mathbb N \to \mathbb N$ which satisfies this functional identity:

$f(a*b)=f(f(a)*f(b))$

To see that functions with such an identity exist I have constructed the following function which takes values depending on whether the input is odd or even number and it is easily obtained that it satisfies above stated functional equation:

$f(a)=\begin{cases}2 & \text{if $a=2k$}\\ 1&\text{if $a=2k-1$}\end{cases}$

Now, my question is:

Does ($f(a*b)=f(f(a)*f(b))\implies Im(f)$ has only finite number of elements?) (if we exclude the trivial case of the identity function $f(a)=a$)

(Thank you Dejan for observing that there is a trivial counterexample, the identity function, now excluded in this edited version of the question.)

In other words, do all the functions that satisfy above functional equation have as their range (or image set) a set with only finite number of values?

Can we somehow prove this?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

Assuming $*$ is multiplication, the answer is negative. For example let $f$ be defined by $f(x)=x$. In this case, $\operatorname{Im}f$ has infinitely many elements and the functional identity holds.

Here's a non-trivial example.

To each $n\in\mathbb N$ assign the set $$P(n)=\{p\in\mathbb N|\;p\text{ is prime and } n \text{ is divisible by } p\}$$ Now define the function $f$ by $$f(n)=\prod_{p\in P(n)}p$$ i.e. $f(n)$ is the product of all primes that divide $n$.

For example: $$f(540) = f(2^2\cdot 3^3\cdot 5) = 2\cdot 3\cdot 5 = 30.$$

Now, $\operatorname{Im}f$ is infinite, since it (among other things) contains all primes. Furthermore $f(f(a)f(b))$ is the product of all primes that appear in the product of the product of all primes in $a$ and the product of all primes in $b$. This is precisely the product of all primes that appear in $ab$ which means that $f(f(a)f(b))=f(ab)$.

share|improve this answer
    
That is correct. I will edit my post to exclude such trivialities. If you have idea, construct another function that has above mentioned functional identity and infinitely many values in the image set. Do you believe there exists another? –  A.P. Jan 30 '13 at 17:38
    
Yes, the $*$ sign is multiplication. –  A.P. Jan 30 '13 at 17:41
    
@A.P.: I added a non-trivial counterexample. In case something might be unclear, comments are welcome. –  Dejan Govc Jan 30 '13 at 23:09
    
All is clear and I accept your answer, maybe it would be good just to define $f(1)=1$ because by the standard definition of prime numbers $P(1)$ would be empty. –  A.P. Jan 31 '13 at 8:11
    
@A.P.: I should probably have mentioned that. The following convention is useful: link. –  Dejan Govc Jan 31 '13 at 8:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.