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

I'm a bit stuck on this... my only thought was to use second induction on $n$, which works well enough for the case where $n$ is composite and has two or more distinct prime factors, but if $n$ is prime or a prime power the induction hypothesis does nothing, so I'm thinking there must be another way. Any ideas?

share|cite|improve this question
I don't think it's true. You must have $a_1=1$, certainly; but pick an arbitrary value for $a_p$ for each prime $p\gt 2$, and define $a_{m}$ in term of its prime factorization. Seems to me that will satisfy the given condition without satisfying $a_n=n$ (unless you pick $a_p=p$ for all $p$). E.g., define $a_m=2^k$, where $k$ is the number of prime factors in the factorization of $m$. Then $a_n$ is completely multiplicative, hence multiplicative, but it does not have the property of your conclusion. – Arturo Magidin Sep 6 '11 at 17:07
Maybe the simplest counterexample is given by $a_n=1$ if $n$ is odd, $a_n=2$ if $n$ is even. – André Nicolas Sep 6 '11 at 17:11
Oh ok, yeah for sure it seemed impossible to find a constructive proof for even a few cases, I must have heard the problem wrong (it was said to me verbally). Sorry about that :( – tyler reed Sep 6 '11 at 17:13
Writing $a*b$ when you mean ordinary multiplication is a usage invented for occasions when you're restricted to the symbols on the keyboard, as in computer programming languages. In $\TeX$ you can write $a\times b$ or $a\cdot b$. Or $ab$. You don't need to eat mashed potatoes with your bare hands when silverware is available. (I edited the title accordingly.) – Michael Hardy Sep 6 '11 at 21:08
This may be a duplicate of – Willie Wong Sep 7 '11 at 10:46

As Arturo's answer (and André's comment) points out, this question is incorrect.

But there are related statements that are, in fact, true. Erdős showed the interesting

Theorem. If $f$ is an increasing multiplicative function, then there exists a constant $\alpha \geq 0$ such that $f(n) = n^{\alpha}$ for all $n \geq 1$.

Here, "increasing" means that $f(n) \geq f(m)$ if $n \geq m$. Also, a function $f$ is said to be multiplicative if it satisfies $f(nm) = f(n) \cdot f(m)$ for all relatively prime $n, m$. This is precisely the condition satisfied by the sequence $a_n$ in the question. For the sake of consistency, we will use the notation $f(n)$ in place of $a_n$.

Now, coming to the question, if we also add the condition that $f$ is increasing, then by the theorem, $f(n) = n^{\alpha}$ for some $\alpha$. The base condition $f(2) = 2$ guarantees that the only possible function satisfying all these conditions is $f(n) = n$, corresponding to $\alpha = 1$.

For the theorem I quote, please refer to A new proof of Erdős's theorem on Monotone Multiplicative Functions by Everett Howe (JSTOR link: here). I cannot be fully sure about this, but I do remember seeing some direct/elementary proofs for the special case when $f(2)$ is equal to $2$. I think this is false. I now think the easier proofs deal with the special case when $f$ is integer-valued. Thanks to Michael Lugo and Mark Bennet pointing this out.

share|cite|improve this answer
Copy and paste: Erdős. – lhf Sep 6 '11 at 17:42
A direct proof is probably easier if one is allowed the further assumption that $f$ is integer-valued. – Michael Lugo Sep 6 '11 at 18:30
The "increasing" condition seemed to me to be decisive, but not particularly trivial. Increasing function to integers is more straightforward. th – Mark Bennet Sep 6 '11 at 18:32
@Michael, I think you are correct. All the real functions satisfying the increasing+multiplicative conditions are equivalent in difficulty, because if $a_n$ is a solution, then so is $a_n^{\beta}$ for any constant $\beta$. So fixing $\beta = 1/\log_2 f(2)$, we can wlog assume that $f(2) = 2$. (One should also take care of the possibility that $f(2) = 1$ etc.) So, even I believe that the correct special case is when $f$ is integer-valued. – Srivatsan Sep 6 '11 at 19:08
@Mark I agree. See my previous comment. – Srivatsan Sep 6 '11 at 19:08

Let $a_1=1$, $a_2=2$. For each positive integer $k\gt 1$, let $a_{2^k}=c_{2^k}$ be arbitrary; and for each prime $p$ and positive integer $\ell\gt 0$, let $a_{p^{\ell}} = c_{p^{\ell}}$ be arbitrary. For a positive integer $m$, factor $m$ into primes $$m = p_1^{\alpha_1}\cdots p_r^{\alpha_r},$$ $\alpha_i\gt 0$, and $p_1\lt p_2\lt\cdots \lt p_r$ primes. Then define $$\begin{align*} a_m &= a_{p_1^{\alpha_1}}\times\cdots\times a_{p_r^{\alpha_r}}\\ &= c_{p_1^{\alpha_1}}\times\cdots\times c_{p_r^{\alpha_r}} \end{align*}$$ Satisfies the given conditions; but unless $c_{p^k}=p^k$, the conclusion will be false.

For example, define $a_m$, with $m$ factored as above, to be $a_m = 2^{\alpha_1+\cdots + \alpha_r}$. Then $a_{mn}=a_ma_n$ for all $m,n$ (not just those that are coprime), but $a_m$ is always a power of $2$.

share|cite|improve this answer

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.