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

Let $f:\mathbb{N}\rightarrow\mathbb{N}$ be a strictly increasing function such that $$f(2)=2$$ and $$f(mn)=f(m)f(n)$$ for all positive integers $m,n$ such that $$\gcd(m,n)=1$$ Prove that $f(n)=n$ for every positive integer $n$.

This is the original question which I have solved by induction, but a comment is given that $f:\mathbb{N}\rightarrow\mathbb{C}$ with $f(1)=1$ and $f(mn)=f(m)f(n)$ whenever $m$ and $n$ are coprime is called a multiplication function. We have the general result that for any increasing multiplicative function that is not constant is of the form $$f(n)=n^\alpha$$ for some $\alpha > 0$

My initial approach to the original problem was to use group theory; is that how this additional, more general, result is derived? I thought that the map is a homomorphism and this preserves order of elements, but I wasn't sure how to go further.

Can anyone give a proof (to either the original problem or the more general result) in terms of this method? Or provide an alternate method?

share|cite|improve this question
Can you explain the proof by induction? – user29743 Jun 8 '12 at 16:47
@countinghaus An inductive proof is given in "Putnam and Beyond" by Gelca and Andreescu #11. – zzzzzzzzzzz Jun 8 '12 at 16:57
Google Books link ot Gelca, Andreescu: Putnam and Beyond, p.8. – Martin Sleziak Jun 8 '12 at 17:00
If you are required to prove a statement for all integers at once, I can't imagine a scenario where you could avoid induction, or something equivalent to it. Certainly "group theory" isn't a substitute. – rschwieb Jun 8 '12 at 17:06
You have a proof of this Erdös result here… – DonAntonio Jun 9 '12 at 3:45

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.