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?
Given $a_2 = 2$ and $a_{mn}=a_m a_n$ for $m$, $n$ coprime, show $a_n=n$ for all natural numbers
-
1This may be a duplicate of http://math.stackexchange.com/q/2593/1543 – 2011-09-07
2 Answers
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.
-
0@Mark I agree. See my previous comment. – 2011-09-06
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$.