# Given $a_2 = 2$ and $a_{mn}=a_m a_n$ for $m$, $n$ coprime, show $a_n=n$ for all natural numbers

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?

-
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 math.stackexchange.com/q/2593/1543 –  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.

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