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

Show that there does not exist a strictly increasing function $f:\mathbb{N}\rightarrow\mathbb{N}$ satisfying

$$f(2)=3$$ $$f(mn)=f(m)f(n)\forall m,n\in\mathbb{N}$$

Progress: Assume the function exists. Let $f(3)=k$ Since $2^3 < 3^2$, $$3^2=f(2)^3=f(2^3)<f(3^2)=f(3)^2=k^2$$ so $k>5$ and since $3^3 < 5^2$, then $$k^3=f(3)^3=f(3^3)<f(2^5)=f(2)^5=3^5=243<343=7^3$$ so $k<7$ therefore $k=6$.

I've messed around with knowing $f(3)=6$ and $f(2)=3$ but I am stuck.

share|cite|improve this question
Ah, sorry. Typo: I have edited the question to include 'strictly increasing' – zzzzzzzzzzz Jun 6 '12 at 18:38
Have you made any attempt to solve the problem yourself? – Ben Millwood Jun 6 '12 at 18:47
I have updated my progress so far – zzzzzzzzzzz Jun 6 '12 at 18:52
up vote 7 down vote accepted

Hint: suppose not. You know what $f(2^k)$ must be. You'll show that $f(3)$ can't be any natural number. You have bounds since $f(2) < f(3) < f(4)$. Start considering $f(3^j) = f(3)^j$ for some small values of $j$ and compare to $f(2^k)$ for some small values of $k$ to eliminate all possibilities for $f(3)$.

share|cite|improve this answer
I've found that $f(3)=6$ and this implies that $2^x < 3^y \iff 3^x < 6^y$ – zzzzzzzzzzz Jun 6 '12 at 18:54
You're almost there. Keep fiddling --- you'll enjoy it more if you get it without any more hints. But if you get really stuck, come back. – John Engbers Jun 6 '12 at 18:56
Got it! Using logarithms: The final step and contradiction was $65536 = 2^{5 \times 3.2} < 2^{5(1+\sqrt{5})}=9^5=59049$. Thanks for giving me a chance to work it out. – zzzzzzzzzzz Jun 6 '12 at 19:05
No problem - we learn most from the struggle. – John Engbers Jun 6 '12 at 19:14

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.