BdMO National Secondary 2020 P7

[Mursalin]

$f$ হলো ধনাত্মক পূর্ণসংখ্যার সেট থেকে ধনাত্মক পূর্ণসংখ্যার সেটে এমন একটা ফাংশন যেন যেকোনো পূর্ণসংখ্যা $n$-এর জন্য যদি $x_1, x_2, \cdots , x_s$ সংখ্যাগুলো $n$-এর সবগুলো ধনাত্মক উৎপাদক হয়, তাহলে $f(x_1)f(x_2)\cdots f(x_s)=n$। $f(343)+f(3012)$-এর সম্ভাব্য সকল মানের যোগফল নির্ণয় করো।

Let $f$ be a function from the set of positive integers to the set of positive integers such that for each positive integer $n$, if $x_1,x_2, \cdots, x_s$ are all the positive divisors of $n$, then $f(x_1)f(x_2)\cdots f(x_s)=n$. Find the sum of all possible values of $f(343)+f(3012)$.

[Anindya Biswas]

Claim-1: $f(1)=1$
Proof : it follows directly from the definition when $n=1$.

Claim-2: $f(p)=p$ for all prime $p$
Proof: Let's substitute $n=p$ where $p$ is a prime number in the given equation, we get:
$$p=f(p)f(1)$$.
$$\therefore p=f(p)$$ since $f(1)=1$. (Proved)

Claim-3: $f(p^k)=p$ for all prime $p$ and positive integer $k$
Proof: The base case with $k=1$ is true and proved in Claim-2.
Inductive step: Let's assume Claim-3 is true for $k=1,2,3,4,\dots,m$ and some prime number $p$.
By substituting $n=p^{m+1}$ where $p$ is that prime number, we get:
$$p^{m+1}=f(p^{m+1})\cdot f(p^m)\cdots f(p)\cdot f(1)$$
$$\rightarrow p^{m+1}=f(p^{m+1})\cdot p^m$$
$$\rightarrow f(p^{m+1})=p$$
$\therefore$ Claim-3 is true for $k=m+1$.
$\therefore$ By the principle of mathematical induction, Claim-3 is true for all prime $p$ and positive integer $k$. (Proved)

Claim-4: If $n$ has more than one prime divisors, then $f(n)=1$
Proof: Let's assume $n=p_{1}^{a_1}\cdot p_{2}^{a_2}\cdots p_{m}^{a_m}$ where $p_1, p_2, \dots, p_m$ are prime numbers.
And let $d_1, d_2, \dots, d_k$ be divisors of $n$ that contains more than one prime divisors.
$$\therefore n=f(d_1)\cdot f(d_2)\cdots f(d_k)\cdot \left( f(p_1)\cdots f(p_{1}^{a_1})\right) \cdot \left( f(p_2)\cdots f(p_{2}^{a_2})\right) \cdots \left(f(p_m)\cdots f(p_{m}^{a_m})\right)\cdot f(1)$$
$$\rightarrow n=f(d_1)\cdot f(d_2)\cdots f(d_k)\cdot p_{1}^{a_1}\cdot p_{2}^{a_2}\cdots p_{m}^{a_m}$$
$$\rightarrow f(d_1)\cdot f(d_2)\cdots f(d_k)=1$$
$$\rightarrow f(d_1)=f(d_2)=\dots=f(d_k)=1$$
Since $n\in \{d_1, d_2, \dots, d_k\}$ $\therefore f(n)=1$ (Proved)

Since $343=7^3$ and $3012=2^2\cdot 3\cdot 251$, by Claim-3 and Claim-4,
$f(343)=7$ and $f(3012)=1$. So, only possible value of $f(343)+f(3012)$ is $7+1=8$
So, our answer is $8$.

[Thephysimatician]

Thanks to Anindya Biswas for solving a general form of the problem