This question already has an answer here:

$f:\mathbb{N}\rightarrow \mathbb{N}$ is a one-to-one function such that $f(mn)=f(m)f(n).$ Find the lowest possible value of $f(999)$.

The answer is given as $24$ but I never get that.


marked as duplicate by Chris Culter, user91500, Jeremy Rickard, Claude Leibovici, Empiricist Aug 25 '15 at 8:13

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Wow, a one-to-one function which takes the same value at $mn$ and $n$... :). $\endgroup$ – Erick Wong Aug 25 '15 at 4:30
  • $\begingroup$ @Erik Wong Sorry just edited it. $\endgroup$ – tatan Aug 25 '15 at 4:32
  • 1
    $\begingroup$ Hint: Start by showing that $f(n)$ is determined by the values of $f(p)$ at all primes $p$. Which primes determine $f(999)$? $\endgroup$ – Erick Wong Aug 25 '15 at 4:33
  • $\begingroup$ $3,37$ are the primes. $\endgroup$ – tatan Aug 25 '15 at 4:37
  • 2
    $\begingroup$ Now $f(3), f(37)$ cannot be $1,$ so we might take $\begin{cases}f(3)=2\\f(37)=3\end{cases}.$ And the lowest value is $2^3\times3.$ $\endgroup$ – awllower Aug 25 '15 at 4:40

$f(999)=f(37)\cdot f(3)\cdot f(3)\cdot f(3)$

Now, $f(3)$ or $f(37)$ cannot be $1.$ Because, if, for example, $f(3)=1,$ then $f(999)=f(37)$ which implies $999=37$ (because the function is one-to-one).

Therefore, $f(3)$ can have the lowest value $2.$ And hence $f(37)$ can have the lowest value $3.$ Thus, $f(999)=3\cdot 2\cdot 2\cdot 2=24.$

  • 1
    $\begingroup$ Please use MathJax formatting on this site--enclose math in dollar signs, and use \cdot for times. See the MathJax basic tutorial and quick reference. $\endgroup$ – 6005 Aug 25 '15 at 4:59
  • $\begingroup$ Re: "$f(3)$ can have lowest value $2$. And hence $f(37)$ can have lowest value $3$": It could be the other way around. However, that would make $f(999) = 2\cdot 3\cdot 3\cdot 3 > 3 \cdot 2 \cdot 2 \cdot 2$. $\endgroup$ – Christopher Carl Heckman Aug 25 '15 at 5:02

$$m=n=1 \Rightarrow f(1)=1$$ so we have $f(3)\ge 2,f(37)\ge 2$ since $f(3)\neq f(37)$

$$f(999)=f(27)\cdot f(37)=(f(3))^3 \cdot f(37)\ge 2^3\cdot 3=24$$

Let us define $f(2)=37,f(3)=2,f(37)=3$ and $f(p)=p$ for all primes $p\neq 2,p\neq 3,p\neq 37$

Let us show the function is injective.

The condition implies $f(\prod_{i=1}^k p_i^{e_i})=\prod_{i=1}^k f(p_i)^{e_i}$

let $m=2^{a}\cdot 3^{b}\cdot 37^{c}\cdot\prod_{i=1}^k p_i^{e_i},n=2^{p}\cdot 3^{q}\cdot 37^{r}\cdot\prod_{i=1}^l p_i^{e_i}, $ be prime factorizations of $m$ and $n$ and $f(m)=f(n)$ then

$$f(m)=f(n) \Leftrightarrow 37^{a}\cdot2^{b}\cdot 3^{c}\cdot \prod_{i=1}^k p_i^{e_i}=37^{p}\cdot2^{q}\cdot 3^{r}\cdot \prod_{i=1}^l p_i^{e_i} \Rightarrow$$

$$a=p,b=q,c=r,\land \prod_{i=1}^k p_i^{e_i}=\prod_{i=1}^l p_i^{e_i} \Rightarrow m=n$$

so the funciton is injective


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