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

How do I go about proving that where $f(k)$ is multiplicative that: $$\sum_{k\geq 1}{\frac{f({k})}{k^{s}}}=\prod_{p}\sum_{k\geq 0}{\frac{f(p^{k})}{p^{ks}}}$$

I first tried to use the fundamental theorem of arithmetic over all $k$'s to get a unique prime factorization, but then I get stuck here. I don't know how to formalize that since we are looking at every $k$ to infinity, that we will be able to go through every combination of prime factorizations. More on this, I'm not sure how to link the denominator, besides that it is the Riemann Zeta Function.

share|cite|improve this question
up vote 1 down vote accepted

It is clear that, being $f$ multiplicative, $f(p^k)f(q^j)=f(p^kq^j)$ whenever $p$ and $q$ are distinct primes. The key observation is that $\frac{f(k)}{k^s}$ is a quotient of two multiplicative functions.

More precisely, for every $k$ on the left hand side consider its factorization: $k=p_1^{a_1}\cdot...\cdot p_n^{a_n}$. Then:

$$\frac{f(k)}{k^s}= \frac{f(p_1^{a_1})\cdot...\cdot f(p_n^{a_n})}{p_1^{a_1s}\cdot...\cdot p_n^{a_ns}}= \frac{f(p_1^{a_1})}{p^{a_1s}}\cdot...\cdot\frac{f(p_n^{a_n})}{p_n^{a_ns}}.$$

Now you only need to put the pieces together. Since every $k$ on the left hand side has a unique prime factorization on the right hand side the thesis follows.

Let us explicit this argument. The Fundamental Theorem of Arithmetic tells us that there is a $1-1$ correspondence between natural numbers $k\in\mathbb{N}$ and prime factorizations $p_1^{a_1} \cdot ... \cdot p_n^{a_n}$, where the $p_i$ are distinct primes and the $a_i$ are again natural numbers. So we can rewrite the left hand side of your expression as:

$$\sum_{k=1}^\infty \frac{f(k)}{k^s} = \sum_{\text{prime factorizations }p_1^{a_1}\cdot...\cdot p_n^{a_n}} \frac{f(p_1^{a_1}\cdot...\cdot p_n^{a_n})}{(p_1^{a_1}\cdot...\cdot p_n^{a_n})^s}.$$

How to obtain the sum over prime factorization? We take the product over all the possible factors of the form $p^k$ where $p$ is a prime and $k$ is a natural number: $$\{\text{prime factorizations } p_1^{a_1}\cdot...\cdot p_n^{a_n}\}\underset{\text{set}}{=} \{\left(\sum_{k=0}^\infty 2^k\right)\cdot\left(\sum_{k=0}^\infty 3^k\right)\cdot\left(\sum_{k=0}^\infty 5^k\right)\cdot...\}.$$

Observe that we must include the factor $p^0=1$ because otherwise we would only have infinite products.

Edit: I believe this kind of argument was first used by Euler to give an analytic proof of the infiniteness of primes. Indeed we know that for every prime $p$ the geometric series: $\sum_{k=1}^\infty \frac{1}{p^k}$ is convergent. While the armonic series $\sum_{n=1}^\infty \frac{1}{n}$ is divergent. But the argument above implies:

$$\prod_{p \text{ prime}} \sum_{k=0}^\infty \frac{1}{p^k}= \sum_{n=1}^\infty \frac{1}{n} = \infty.$$

So the number of primes must be infinite.

share|cite|improve this answer
So I also got a hint that there's supposed to be an intermediate step where: $$\prod_{p}(1+{\frac{f(p^{})}{p^{}}}+{\frac{f(p^{2})}{p^{2}}}+{\frac{f(p^{3})}{p‌​^{3}}}+...)$$ How does this fit in with what you said? I don't know how to split the product into a sum. More, I'm not sure how you are able to say that the denominators in your last step ${p_n^{a_ns}}$ cancel and become what's on the right hand side $p^ks$. – Gbean Nov 12 '12 at 10:19
Ok, I'm going to edit my answer to make the combinatorial passage a bit more explicit! – Giovanni De Gaetano Nov 12 '12 at 10:23
Tell me if now it's fine or you still have some doubts! :) – Giovanni De Gaetano Nov 12 '12 at 10:36
Yes, I did not know that the # of prime factorizations was countable, that helped a lot! However, I am still stuck on this: We take the product over all the possible factors of the form pk where p is a prime and k is a natural number, observe that we must include the factor p0=1 because otherwise we would only have infinite products. How did you know to take the factors of p^k out, and how did you know that their product will give you the sum from the previous step? And what do you mean by infinite products? – Gbean Nov 12 '12 at 10:46
When I said "infinite product" I was a bit sloppy, I apologize. I just meant that if you do not allow $k$ to be zero then you have a infinite product of integers larger than $1$, and this is always infinity. You can see it easily with a practical example: $12= 2^2 \cdot 3^1 \cdot 5^0 \cdot 7^0 \cdot...$. You see that we must use $k=0$ for every prime that does not divide $12$. Regarding your first question, i.e. how did I know that I had to take the prime factors out I would just answer "by experience". I knew other similar arguments and I just manipulated them to fit your specific question. – Giovanni De Gaetano Nov 12 '12 at 11:20

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.