Previous in Relation and Functions Next in Relation and Functions
Question Number 19978 by Tinkutara last updated on 19/Aug/17
$$\mathrm{Let}\:{f}\:\mathrm{be}\:\mathrm{a}\:\mathrm{one}-\mathrm{to}-\mathrm{one}\:\mathrm{function}\:\mathrm{from} \\ $$$$\mathrm{the}\:\mathrm{set}\:\mathrm{of}\:\mathrm{natural}\:\mathrm{numbers}\:\mathrm{to}\:\mathrm{itself} \\ $$$$\mathrm{such}\:\mathrm{that}\:{f}\left({mn}\right)\:=\:{f}\left({m}\right){f}\left({n}\right)\:\mathrm{for}\:\mathrm{all} \\ $$$$\mathrm{natural}\:\mathrm{numbers}\:{m}\:\mathrm{and}\:{n}.\:\mathrm{What}\:\mathrm{is}\:\mathrm{the} \\ $$$$\mathrm{least}\:\mathrm{possible}\:\mathrm{value}\:\mathrm{of}\:{f}\left(\mathrm{999}\right)? \\ $$
Answered by mrW1 last updated on 20/Aug/17
![Every natural number N can be written as the product of a serial of prime numbers: N=p_1 ^q_1 ×p_2 ^q_2 ×...×p_k ^q_k p=prime numbers 1,2,3,5,7.... since f(mn)=f(m)f(n) f(N)=[f(p_1 )]^q_1 ×[f(p_2 )]^q_2 ×...×[f(p_k )]^q_k for f(N) to be a one to one funtion, it is to say that f(p_i ) with i=1,2,...∞ must be different. f(1)=f(1×1)=f(1)×f(1) ⇒f(1)=1 i.e. only f(1) should be 1, f(p_i ) with i>2 can be freely choosen. With N=999=1×3^3 ×37 ⇒f(999)=f(1)×[f(3)]^3 ×f(37) to keep f(999) as small as possible we can choose f(3)=2 and f(37)=3 ⇒f(999)=1×2^3 ×3=24](Q19997.png)
$$\mathrm{Every}\:\mathrm{natural}\:\mathrm{number}\:\mathrm{N}\:\mathrm{can}\:\mathrm{be}\:\mathrm{written} \\ $$$$\mathrm{as}\:\mathrm{the}\:\mathrm{product}\:\mathrm{of}\:\mathrm{a}\:\mathrm{serial}\:\mathrm{of}\:\mathrm{prime} \\ $$$$\mathrm{numbers}: \\ $$$$\mathrm{N}=\mathrm{p}_{\mathrm{1}} ^{\mathrm{q}_{\mathrm{1}} } ×\mathrm{p}_{\mathrm{2}} ^{\mathrm{q}_{\mathrm{2}} } ×...×\mathrm{p}_{\mathrm{k}} ^{\mathrm{q}_{\mathrm{k}} } \\ $$$$\mathrm{p}=\mathrm{prime}\:\mathrm{numbers}\:\mathrm{1},\mathrm{2},\mathrm{3},\mathrm{5},\mathrm{7}.... \\ $$$$ \\ $$$$\mathrm{since}\:\mathrm{f}\left(\mathrm{mn}\right)=\mathrm{f}\left(\mathrm{m}\right)\mathrm{f}\left(\mathrm{n}\right) \\ $$$$\mathrm{f}\left(\mathrm{N}\right)=\left[\mathrm{f}\left(\mathrm{p}_{\mathrm{1}} \right)\right]^{\mathrm{q}_{\mathrm{1}} } ×\left[\mathrm{f}\left(\mathrm{p}_{\mathrm{2}} \right)\right]^{\mathrm{q}_{\mathrm{2}} } ×...×\left[\mathrm{f}\left(\mathrm{p}_{\mathrm{k}} \right)\right]^{\mathrm{q}_{\mathrm{k}} } \\ $$$$ \\ $$$$\mathrm{for}\:\mathrm{f}\left(\mathrm{N}\right)\:\mathrm{to}\:\mathrm{be}\:\mathrm{a}\:\mathrm{one}\:\mathrm{to}\:\mathrm{one}\:\mathrm{funtion},\:\mathrm{it}\:\mathrm{is} \\ $$$$\mathrm{to}\:\mathrm{say}\:\mathrm{that}\:\mathrm{f}\left(\mathrm{p}_{\mathrm{i}} \right)\:\mathrm{with}\:\mathrm{i}=\mathrm{1},\mathrm{2},...\infty\:\mathrm{must} \\ $$$$\mathrm{be}\:\mathrm{different}. \\ $$$$ \\ $$$$\mathrm{f}\left(\mathrm{1}\right)=\mathrm{f}\left(\mathrm{1}×\mathrm{1}\right)=\mathrm{f}\left(\mathrm{1}\right)×\mathrm{f}\left(\mathrm{1}\right) \\ $$$$\Rightarrow\mathrm{f}\left(\mathrm{1}\right)=\mathrm{1} \\ $$$$\mathrm{i}.\mathrm{e}.\:\mathrm{only}\:\mathrm{f}\left(\mathrm{1}\right)\:\mathrm{should}\:\mathrm{be}\:\mathrm{1},\:\mathrm{f}\left(\mathrm{p}_{\mathrm{i}} \right)\:\mathrm{with}\:\mathrm{i}>\mathrm{2} \\ $$$$\mathrm{can}\:\mathrm{be}\:\mathrm{freely}\:\mathrm{choosen}. \\ $$$$ \\ $$$$\mathrm{With}\:\mathrm{N}=\mathrm{999}=\mathrm{1}×\mathrm{3}^{\mathrm{3}} ×\mathrm{37} \\ $$$$\Rightarrow\mathrm{f}\left(\mathrm{999}\right)=\mathrm{f}\left(\mathrm{1}\right)×\left[\mathrm{f}\left(\mathrm{3}\right)\right]^{\mathrm{3}} ×\mathrm{f}\left(\mathrm{37}\right) \\ $$$$\mathrm{to}\:\mathrm{keep}\:\mathrm{f}\left(\mathrm{999}\right)\:\mathrm{as}\:\mathrm{small}\:\mathrm{as}\:\mathrm{possible}\:\mathrm{we} \\ $$$$\mathrm{can}\:\mathrm{choose} \\ $$$$\mathrm{f}\left(\mathrm{3}\right)=\mathrm{2}\:\mathrm{and}\:\mathrm{f}\left(\mathrm{37}\right)=\mathrm{3} \\ $$$$\Rightarrow\mathrm{f}\left(\mathrm{999}\right)=\mathrm{1}×\mathrm{2}^{\mathrm{3}} ×\mathrm{3}=\mathrm{24} \\ $$
Commented by Tinkutara last updated on 20/Aug/17
$$\mathrm{Thank}\:\mathrm{you}\:\mathrm{very}\:\mathrm{much}\:\mathrm{Sir}! \\ $$