4
$\begingroup$

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?

  • 0
    Can you explain the proof by induction?2012-06-08
  • 0
    I have a strong sense of déjà vu that I've seen this question before, but couldn't find it.2012-06-08
  • 1
    @countinghaus An inductive proof is given in "Putnam and Beyond" by Gelca and Andreescu #11.2012-06-08
  • 0
    @Gigili The general result is attributed to Paul Erdős, but I do not know where it is found.2012-06-08
  • 3
    Google Books link ot Gelca, Andreescu: Putnam and Beyond, [p.8](http://books.google.com/books?id=eqnUG85ZIJMC&pg=PA8).2012-06-08
  • 1
    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.2012-06-08
  • 0
    You can define $f$ over powers of prime numbers and then $f$ can extend in a unique way to all numbers. But, why $f(p^n)=p^{n\alpha}$ for prime numbers?2012-06-08
  • 0
    For multiplicative functions *Introduction to analytic number theory* of T. Apostol is a good book (first chapters).2012-06-08
  • 2
    You have a proof of this Erdös result here http://www.jstor.org/discover/10.2307/2322314?uid=3738240&uid=2&uid=4&sid=211008413565812012-06-09

0 Answers 0