Problem 1668

### Part (a)

We need to prove that there are no injective functions $f: \mathbb{N} \to \mathbb{N} \cup \{0\}$ such that
$$f(mn) = f(m) + f(n) \quad \forall \, m,n \in \mathbb{N}.$$

1. Initial Conditions:
- Let $m = 1$. Then $f(mn) = f(n)$ implies $f(1 \cdot n) = f(1) + f(n)$. Hence, $f(n) = f(1) + f(n)$.
- This implies $f(1) = 0$.

2. Prime Powers:
- For any prime $p$ and non-negative integer $a$, we have:
$$f(p^a) = af(p).$$
- This follows by induction. For $a = 1$, it is trivially true. Assume it holds for $a$, then:
$$f(p^{a+1}) = f(p \cdot p^a) = f(p) + f(p^a) = f(p) + af(p) = (a+1)f(p).$$

3. Distinct Primes:
- For pairwise distinct primes $p_1, p_2, \ldots, p_k$ and non-negative integers $a_1, a_2, \ldots, a_k$, we have:
$$f(p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}) = a_1 f(p_1) + a_2 f(p_2) + \cdots + a_k f(p_k).$$
- This follows from the multiplicative property of $f$ and the fact that $f$ is additive over products of distinct primes.

4. Contradiction:
- Assume $f$ is injective. Then $f(2) \neq 0$ and $f(3) \neq 0$.
- Consider $f(2^{f(3)})$ and $f(3^{f(2)})$:
$$f(2^{f(3)}) = f(2) \cdot f(3) \quad \text{and} \quad f(3^{f(2)}) = f(3) \cdot f(2).$$
- Since $f$ is injective, $2^{f(3)} \neq 3^{f(2)}$. However, $f(2^{f(3)}) = f(3^{f(2)})$ implies $2^{f(3)} = 3^{f(2)}$, which is a contradiction.

Thus, no such injective function $f$ exists.

$\blacksquare$

### Part (b)

We need to prove that for all positive integers $k$, there exist injective functions $f: \{1, 2, \ldots, k\} \to \mathbb{N} \cup \{0\}$ such that $f(mn) = f(m) + f(n)$ for all $m, n \in \{1, 2, \ldots, k\}$ with $mn \leq k$.

1. **Choice of Prime $p$:**
- Let $k$ be given, and let $p$ be a prime greater than all the exponents appearing in the prime decompositions of the numbers $1, 2, \ldots, k$.

2. Function Definition:
- Define $f(1) = 0$.
- Let $p_1, p_2, \ldots, p_m$ be the primes not greater than $k$. Thus, each of the numbers $2, 3, \ldots, k$ only decomposes with the $p_i$'s.
- For each $i$, let $f(p_i) = p^i$.

3. Non-prime Numbers:
- For all non-primes $t \leq k$, define $f(t)$ using the property:
$$f(p_1^{a_1} p_2^{a_2} \cdots p_m^{a_m}) = a_1 f(p_1) + a_2 f(p_2) + \cdots + a_m f(p_m).$$

4. Verification:
- It is clear that $f(mn) = f(m) + f(n)$ for all $m, n$ such that $mn \leq k$.
- Using the uniqueness of the decomposition in base $p$, the equality $f(t) = f(t')$ is equivalent to the fact that $t$ and $t'$ have the same prime decompositions, which implies $t = t'$. Hence, $f$ is injective.

$\blacksquare$