Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Given a function $f$ defined on the set of all natural numbers $\mathbb{N}$ with three conditions:

  1. If $m,n$ relatively prime, then $f(mn) = f(m)f(n)$.

  2. $f$ strictly increasing.

  3. $f(2) = 2$.

Find a 4th condition such that the result will be that $f(n)$ must equal $n$ for any natural number $n$. (Of course all the conditions together are needed. Your 4th condition should not make any of these three conditions redundant.)

This is posted in my university website:

[1]: http://

share|cite|improve this question
Maybe we shouldn't answer this here, if there's a prize waiting for students at University of Hyderabad for solving it. – Rasmus Aug 16 '10 at 16:44
up vote 2 down vote accepted

In fact, it's a theorem of Erdős that every non-decreasing multiplicative function $f:\mathbb{N}\to\mathbb{R}$ is $f(n)=n^c$ for some constant $c$. This implies that those three conditions are already enough to prove that $f(n)=n$.

You can read a proof by Pierre Pbornsztein here.

share|cite|improve this answer
Yes, actually "multiplicative" means that $f(mn)=f(m)f(n)$ is true for $m,n$ relatively prime. If $f(mn)=f(m)f(n)$ for all $m,n$ then $f$ is said to be "completely multiplicative". For more on this read – Jorge Miranda Aug 16 '10 at 17:06
@Charles: All you need it f:N->N. Perhaps that is the fourth condition :-) If f:N->N, then f(1) = 1 and that makes it multiplicative... – Aryabhata Aug 16 '10 at 17:07
@Jorge: Those three conditions are probably not sufficient, f(1) = 0.1 is a possibility, isn't it? I think the 4th condition could be that the range of f is N. – Aryabhata Aug 16 '10 at 17:18
@moron @jorge f(1) is already 1 by implication: hcf(n,1)=1 for all n so f(m)=f(mx1)=f(m)f(1)- divide through by f(m) to see f(1)=1 – Tom Boardman Aug 16 '10 at 17:20
@Tom: Duh! You are right :-) – Aryabhata Aug 16 '10 at 17:22

Your Answer


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