Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


share|cite|improve this question
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
up vote 3 down vote accepted

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.

share|cite|improve this answer
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… – 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), $$


$$ 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).

share|cite|improve this answer

Your Answer


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.