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
3
$\begingroup$
elementary-number-theory
-
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