# Proof of Multiplicity

What is the general method for proving that an arithmetic function is multiplicative? I will list the definitions that I’m working with for multiplicity

An arithmetic function $f$ is said to be multiplicative if $f(mn) = f(m) f(n)$ whenever $m$ and $n$ are relatively prime positive integers. An arithmetic function $f$ is said to be completely multiplicative if $f(mn) = f(m) f(n)$ for all positive integers $m$ and $n$.

Now consider the following example from my textbook that I do not understand.

Let $g$ be an arithmetic function such that $g(1) = 1$ and $g(n) = 2^m$ where $m$ represents the number of unique prime numbers in the prime factorization of n. Now how would you show that $g$ is multiplicative, but not completely multiplicative?

The first thought I had was to use induction, but I started to get confused at the inductive step. But is this the way these type of problems must be solved?

-
For not completely multiplicative, note that $g(2)=2^1$, and $g(4)=2^1$, so $g(4)\ne g(2)g(2)$. To prove multiplicativity, look at the prime power decompositions of $m$, $n$, and $mn$. In principle one perhaps should use induction, but it's not really worth bothering. –  André Nicolas Feb 20 '13 at 8:16

If $m$ and $n$ are relatively prime, can you figure out a relationship between the (number of) prime divisors of $m$, the prime divisors of $n$ and the prime divisors of $mn$?
You CAN use induction, but generally you will want to use strong induction. That is, suppose $m$ and $n$ are relatively prime: You will assume that the formula $f(ab) = f(a)f(b)$ holds for ALL pairs $a,b$, with $a$ and $b$ relatively prime, $a \leq m$ and $b \leq n$ (but not both equal). Then you can reduce to a smaller case by, perhaps, factoring some prime number out of $m$ or $n$ to make it smaller. This is only one technique, though, and it is not always the most effective.