$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)$. [duplicate]

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, EmpiricistAug 25 '15 at 8:13

• Wow, a one-to-one function which takes the same value at $mn$ and $n$... :). – Erick Wong Aug 25 '15 at 4:30
• @Erik Wong Sorry just edited it. – tatan Aug 25 '15 at 4:32
• Hint: Start by showing that $f(n)$ is determined by the values of $f(p)$ at all primes $p$. Which primes determine $f(999)$? – Erick Wong Aug 25 '15 at 4:33
• $3,37$ are the primes. – tatan Aug 25 '15 at 4:37
• 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.$ – 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.$$

• 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. – 6005 Aug 25 '15 at 4:59
• 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$. – 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