Explain why the following is or isn't a multiplicative function.

Question

I'm working through practice problems for my exam in class and I need some help with the following problem:

A function $f(n)$ is defined to be the greatest power of $2$ that divides $n$.

For example, $f(20) = 2^2 = 4$, $f(32) = 2^5 = 32$, $f(72) = 2^3 = 8$, etc.

Is $f(n)$ a multiplicative function? Explain your answer.

I believe that it is a multiplicative function by looking at the examples, but I'm not sure how to explain the logic behind it and prove it for all cases.

Please correct me if I'm wrong, thank you for the help!

Answer 1

A multiplicative function satisfies $f(1)=1$ (true in your case) and $f(ab)=f(a)f(b)$ for any coprime $a,b$. This is easily verified, by writing $a=2^mx$ for $x$ odd, $b=2^ny$ for $y$ odd, and noting that $f(a)=2^m,f(b)=2^n$ and $f(ab)=2^{m+n}$ which is good.

In fact, $f$ is what is known as totally (or completely) multiplicative because the relation is satisfied for all pairs $a,b$, not just coprime ones.

Answer 2

I would start by noting that you can write any positive integer $n$ as $n = a \cdot 2^k$ where $a$ is odd, and $f(n) = 2^k$. Based on that, consider what happens if you have $n_1 = a_1 \cdot 2^{k_1}$ and $n_2 = a_2 \cdot 2^{k_2}$.

Answer 3

Suppose $a = 2^\alpha p$ where $p$ is an odd prime, and $b = 2^\beta q$, where $q$ is also an odd prime (it may even be the same as $p$, actually). Thus $f(a) = 2^\alpha$ and $f(b) = 2^\beta$. Then what is $ab$? Obviously $ab = 2^\alpha 2^\beta pq = 2^{\alpha + \beta} pq$, so $f(ab) = 2^{\alpha + \beta}$. Now you only need to consider $p$ and $q$ that may not be prime but are odd to complete the proof.