Take the 2-minute tour ×
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.

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|improve this question
Ah, sorry. Typo: I have edited the question to include 'strictly increasing' –  rckrd 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 –  rckrd Jun 6 '12 at 18:52

1 Answer 1

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|improve this answer
I've found that $f(3)=6$ and this implies that $2^x < 3^y \iff 3^x < 6^y$ –  rckrd 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. –  rckrd 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.