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?
Best Answer
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.