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
-
3I 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. – 2011-09-06
-
3Maybe the simplest counterexample is given by $a_n=1$ if $n$ is odd, $a_n=2$ if $n$ is even. – 2011-09-06
-
0Oh 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 :( – 2011-09-06
-
0Writing $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.) – 2011-09-06
-
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.
-
0Copy and paste: Erdős. – 2011-09-06
-
0A direct proof is probably easier if one is allowed the further assumption that $f$ is integer-valued. – 2011-09-06
-
0The "increasing" condition seemed to me to be decisive, but not particularly trivial. Increasing function to integers is more straightforward. th – 2011-09-06
-
0@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. – 2011-09-06
-
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$.