Show that there are infinitely many functions $f:\mathbb N\rightarrow\mathbb N$ satisfying $f(2)=2$ and$f(mn)=f(m)f(n) \forall m,n\in \mathbb N$

Question

Show that there are infinitely many functions $f:\mathbb N \rightarrow \mathbb N$ such that

(a) $f(2)=2$

(b) $f(mn)=f(m)f(n)$ for all $m,n\in \mathbb N$$

Solution as in book:

Here we use another property of natural numbers: Given any natural number n, there exist a unique set $\{{p_1,p_2,\cdots , p_k}\}$ of prime numbers and unique set $\{\alpha_1, \alpha_2,\cdots,\alpha_k\}$ of positive integers such that $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$

The condition (b) show that in order to know $f$, it is sufficient to know its value at each prime. We have its value at $p=2$, We can define $f$ arbitrary on primes $\neq 2$ and use (b) to extend it to all other natural number using prime decomposition.

Note that (b) forces $\;f(1)=1$

For example let us enumerate the set of all prime numbers as an increasing sequence: $3=p_2<p_3<p_4<\cdots$.

Define for each $k\geq 1$ $f_k$ by $f_k(p_j)=p_{j+k}$ for all $j\geq 2$.

If $n=q_1^{\alpha_1}q_2^{\alpha_2}\cdots q_k^{\alpha_k}$ is prime decomposition of $n$, then we define $f_k(n)=f_k(q_1)^{\alpha_1}f_k(q_2)^{\alpha_2}\cdots f_k(q_l)^{\alpha_l}$

Thus $f_1(3)=5, f_1(5)=7, f_1(7)=11,f_1(15)=35,f_1(16)=16$ and so on.

My doubt: (1) Why only function of kind $f_k(p_j)=p_{j+k}$?

(2) Can the function be like $f_k(p_j)=(p_{k+1})^2$ too?

(3) Can anyone else suggest other way to solve this problem?

Answer 1

Recall that any positive integer can be written uniquely as $l= 2^n(2m+1)$. Now define $$ f(2^n(2m+1)) = 2^n(2m+1)^2$$ This function satisfies both (a) and (b) but does not satisfies (1).

Your book only asks for infinitely many examples of such functions. Not for the full list.

Answer 2

(1) It is just an example of infinitely many such functions, that's all. You could have chosen something different, but the goal is simply to show there exist infinitely many such functions, that's all, not all the functions. From the definition, it is also clear that all these functions are different from each other.

(2) Your example would also work, yes, although I do have to say, it might be a little less clear why all the functions are different from each other only by looking at the definition.

(3) One could also choose $f_k(p_j) = j$ or $f_k(p_j)=k$, it really does not matter, the crucial part is that through prime decomposition, you can simply define the functions on the primes and that is enough.

Answer 3

The key point is this: Suppose $f$ is a function defined on all prime(with $f(2)=2$) numbers as well as the number $1$(with $f(1)=1$), then one can (uniquely) extend the function $f$ to all natural numbers, and have $f(mn)=f(m)f(n)$. The reason is that every natural number $>2$, can be written as a unique product of primes. So for instance if you have $f(3)=5$ then you get $f(6)=f(2)f(3)=10$.

Seeing that there are infinitely many such functions is not hard.

Answer 4

I'll answer your third question. I think you mean you want a way that does not just find a family of infinite $f$'s, so here it is.

Observe $f(n)=n$ is one possible function, also

$$f(p)=\begin{cases} p &(p=2)\\ p^2&(p\ne2)\\ \end{cases}$$

is possible as well. So we have at least two possible $f$'s.

Assume the number of $f$'s is finite, and name these $f_1, f_2, \cdots, f_k$.

Notice that if we define $f_{k+1}(n)=f_1(n) f_2(n) \cdots f_k(n)$ where $n \ne 2$ and $f_{k+1}(2)=2$, this has to satisfy all the constraints. Plus, the value of $f_{k+1}(n)$ is greater than that of any other $f$'s, so it is not identical to any of them.

This contradicts that the number of $f$'s can be determined as a finite number, hence the proof.

However, in this process, we could have just found

$$f_k(p)=\begin{cases} p &(p=2)\\ p^{k}&(p\ne2)\\ \end{cases}$$

which is quicker and easier. If you want to prove the infinity of something, the best way is usually one of those two methods.