Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

1 Answer 1

up vote 1 down vote accepted

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$?

There are many examples of multiplicative functions whose definition is based on the divisors and/or prime divisors of a number. Numbers which are relatively prime share no factors, and this is a helpful fact that can help you show results like this.

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.

share|improve this answer

Your Answer

 
discard

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.