4
$\begingroup$

The Big Omega function $\Omega(n)$ gives you the total number of prime factors of the number n.

A function $f(x)$ is completely additive if $f(ab)=f(a)+f(b)$ for all positive numbers $a$ and $b$, even if they aren't coprime.

Wiki states that $\Omega(n)$ is completely additive. How could I go about proving this, if possible,, rigorously? [https://en.wikipedia.org/wiki/Additive_function#Completely_additive]

$\endgroup$
2
  • 1
    $\begingroup$ Write prime factorizations of $a$ and $b$, also $ab$. Then compare the values $\Omega(a)$, $\Omega(b)$, and $\Omega(ab)$. $\endgroup$ Commented Jun 12, 2016 at 4:57
  • $\begingroup$ Yup. Got it @i707107 $\endgroup$ Commented Jun 12, 2016 at 5:02

1 Answer 1

3
$\begingroup$

Let's say $a = p^m$ and $b = p^n$, where $p$ is some prime number and $m$ and $n$ are non-negative integers. Clearly $\Omega(a) = m$ even though $\omega(a) = 1$ (or $0$ if $m = 0$); the similar statement for $b$ is easily derived.

Then $ab = p^m p^n = p^{m + n}$ follows from the basic properties of exponentiation, and therefore $\Omega(ab) = \Omega(a) + \Omega(b) = m + n$. This proves the function is additive when $a$ and $b$ are powers of the same prime.

Suppose instead $a = p^m$ like before but $b = q^n$ where $q \neq p$ is also prime. We still have $\Omega(b) = n$, and since $ab = p^m q^n$, we still have $a$ contributing $m$ prime factors to $ab$ and $b$ contributing $n$ factors.

Rather than examine the remaining cases ($a$ and $b$ have more than one distinct prime factor each, they share some prime factors, etc.) we can just observe that all this function does is count exponents in the prime factorization (with the exponent $1$ understood in those cases where it's not explicitly written out)

$\endgroup$
1
  • $\begingroup$ Not too rigorous. I proved the property myself later on, by using the unique factorization (Fund. theorem of Arithmetic) of a number to generalize. Thanks for the answer. $\endgroup$ Commented Jun 14, 2016 at 1:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .