# Prove that $f(n) = 2^{\omega(n)}$ is multiplicative where $\omega(n)$ is the number of distinct primes

Prove that $f(n) = 2^{\omega(n)}$ is multiplicative where $\omega(n)$ is the number of distinct primes.

My attempt:

Let $a = p_1p_2\cdots p_k$ and $b = q_1q_2\cdots q_t$ where $p_i$ and $q_j$ are prime factors, and $p_i \neq q_j$ for all $1 \leq i \leq k$ and $1 \leq j \leq t$. We will show that $2^{\omega(ab)} = 2^{\omega(a)} \times 2^{\omega(b)}$

Indeed, $\omega(a) = k$ and $\omega(b) = t$. Then $2^{\omega(a)} \times 2^{\omega(b)} = 2^{k + t}$
Where $2^{\omega(ab)} = 2^{k + t}$
$\therefore 2^{\omega(ab)} = 2^{\omega(a)} \times 2^{\omega(b)}$

Am I in the right track?

Thanks,

-
You are right. But it's better to specify that $p_i$ and $q_j$ are different for all $i,j$, because in your formulation, $p_i$ can repeat itself, so can $q_j$. – Soarer Mar 1 '11 at 5:35
@Soarer: Thanks for your feedback. I really have to say it explicitly. – Chan Mar 1 '11 at 5:37
@Chan: You are probably saying $p_i \neq q_j$ for all $1 \leq i \leq k$ and $1 \leq j \leq t$. – Soarer Mar 1 '11 at 5:43
@Soarer: Yes I did, something with that? – Chan Mar 1 '11 at 5:49
You said $p_i$ and $p_j$. Edit: Seems like Arturo has edited it for you :) – Soarer Mar 1 '11 at 5:51

Hint: Notice $$2^{\omega(a)}\times 2^{\omega(b)}=2^{\omega(a)+\omega(b)}$$ so try to relate $\omega(a)+\omega(b)$ and $\omega(ab)$.

To simplify things, you need only show it holds for $a=p^r$, $b=q^t$ where $q,p$ are prime numbers.

-
Thanks for your hint. So what my attempt was incorrect? Could you show where did I miss? Thank you. – Chan Mar 1 '11 at 5:50
@Chan: Everything looks correct to me. The only thing I suggest in the future is notice that multiplicative functions are given completely by the prime powers, and it suffices to show that a function is multiplicative by looking only at the prime powers. (Consequence of FTA) This makes solutions quicker I find. – Eric Naslund Mar 1 '11 at 5:53
got it. Thank you. By the way would you mind taking a look at this thread again math.stackexchange.com/questions/24143/… – Chan Mar 1 '11 at 5:57
Done, hope that helps. – Eric Naslund Mar 1 '11 at 6:18

Note that if $f : \mathbb{N} \to \mathbb{C}$ is additive:

$$\gcd(m,n) = 1 \quad \Longrightarrow \quad f(mn) = f(m) + f(n),$$

then for any $t > 0$, $g(n) := t^{f(n)}$ is multiplicative:

$$\gcd(m,n) = 1 \quad \Longrightarrow \quad g(mn) = g(m) g(n),$$

since

$$g(mn) = t^{f(mn)} = t^{f(m) + f(n)} = t^{f(m)}t^{f(n)} = g(m) g(n).$$

Note also that this $g$ will never be the zero function. Therefore, it suffices to show that $\omega(n)$ is additive (which has indeed already been shown).

-