Find all functions $f:\mathbb{N}\rightarrow\mathbb{N}$ such that for every positive integer $n$ the following is valid: If $d_1,d_2,\ldots,d_s$ are all the positive divisors of $n$, then $$f(d_1)f(d_2)\ldots f(d_s)=n.$$
Problem
Source: 2020HKTST1 Q1
Tags: number theory, functional equation, function
24.08.2019 14:36
$f(1)=1$. It's easy to conclude by induction, that $f(p^n)=p$, where $p$-prime. Let's consider prime factorization of $n$ and let $p_1,p_2,\ldots,p_s$ be set of its prime divisors. Then, $\prod_{i=1}^{a_1}f(p_1)^{i}\prod_{i=1}^{a_2}f(p_2)^{i}\ldots \prod_{i=1}^{a_s}f(p_s)^{i}\cdot A =n$, where $A$ is the multiple of rest divisors. So, $A = 1$, which means, each member of $A$ is equal to $1$. Answer is $f(p^a)=p$ for all primes $p$, and $f(x)=1$ for the rest.
24.08.2019 15:57
It's obvious that at most one $f$ works. Now observe that $f(n) = e^{\Lambda(n)}$ works due to the identity $$\sum_{d\mid n} \Lambda(n) = \log n.$$($\Lambda$ is von Mangoldt function)
24.10.2019 16:52
$P(1): f(1)=1$ $P(p): f(p)f(1)=p =>f(p)=p$, for primes $p$. Say that $f(p)=f(p^2)=...=f(p^{\alpha})=p$. $P(p^{\alpha+1}): f(1)f(p)f(p^2)...f(p^{\alpha})f(p^{\alpha+1})=p^{\alpha+1} =>f(p^{\alpha+1})=p$. Let $n = p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k}$. Notice that $p_i,p_i^2,...,p_i^{\alpha_i}$ are all divisors of $n$, thus: $P(n): p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k} \cdot$ ( product of $f(m_i)$ where $m_i$ are all divisors of $n$ not of the form $p_i^t$ )$=p_1^{\alpha_1}...p_k^{\alpha_k}$. Hence $f(p^{\alpha})=p$, where $p$ is prime, and $f(m)=1$, where $m \neq p^{\alpha}$. Cute concept of a problem, although playing with divisors in FEs is certainly not new, it's implementation here seems quite cool and original...
25.10.2019 05:57
Möbius inversion formula gives $$f(n)=\prod \limits _{d \mid n}d^{\mu(\frac{n}{d})}$$
01.11.2019 18:14
02.10.2020 15:03
redacted
02.10.2020 15:07
It's not uncommon for olympiad problems to be reused. There was this one problem that was used by the Soviets, South Korea, the Morocco TST, the Putnam, etc.
08.10.2020 16:31
By condition we get that $f(1)=1$ since $1$ is the only divisor of $1$. Next, we get that $f(p)f(1)=p$ so $f(p)=p$. Also $f(p^2)f(p)f(1)=p^2$ so $pf(p^2)=p^2$ so $f(p^2)=p$. By induction for every integer $k$, we have that $f(p^k)=p$. By prime factorization we have that $n$ $=$ $\prod_{i=1}^{s}{p_{i}^{a_i}}$, and $P$ $=$ $\prod_{k=1}^{a_1}{f(p_{1}^{k})}$ $\cdots$ $\prod_{k=1}^{a_s}{f(p_{s}^{k})}$ times all $f(x)$ such that $x$ has at least two prime factors is equal to $n$ .But $P=\prod_{i=1}^{s}{p_{i}^{a_i}}=n$ since $f(p^k)=p$ , so for every $x$ such that it has at least two prime factors $f(x)=1$. So our solution is: $ \begin{cases} f(p^k)=p & \forall k \in \mathbb{Z}\ \text{and}\ \forall p \in \mathbb{P}\ \\ f(x)=1\ & \text{x has at least two prime factors} \\ \end{cases} $
07.12.2021 21:25
We claim that $f(1)=1, f(p^k)=1$, and if $m$ isn't a prime power then $f(m)=1$. This clearly satisfies the relation for all $n$. Let $P(n)$ be the condition. Note that $P(1)$ gives $f(1)=1$. Then, we claim by induction that $f(p^k)= p$ for all $k\geq 1$. The base case is clear, $P(p)$ gives $f(p) = f(p)\cdot f(1) = p$. For the inductive step, considering $P(p^{k+1})$ gives $f(p^{k+1}) = \frac{p^{k+1}}{\prod_{i=0}^k f(p^k)} = p$. Now, we claim that all other values are 1. Consider some integer $m= \prod_{i=1}^t p_i^{e_i}$ which is not a prime power. Then, since $f\colon \mathbb{N}\to \mathbb{N}$, we have that based on $P(m)$: \[f(m) \mid \frac{m}{\prod_{i=1}^t f(p_i^{e_i})} = \frac{m}{m} = 1\]Thus, $f(m)=1$ if $m$ isn't a prime power and we're done.
08.12.2021 00:00
With $n=1$ we find $f(1)=1$. Setting $n=p$ prime, we have $f(p)=p$. Now we prove by strong induction that $f(p^k)=p$ for $k\in\mathbb N$, with the base case already shown. If $f(p^i)=p$ for all $i<k$, then: $$p^k=\prod_{i=1}^kf(p^i)=p^{k-1}\cdot f(p^k)$$so $f(p^k)=p$. Now let $n$ not be a prime power. Writing $n$ as $\prod_{i=1}^kp_i^{a_i}$ (the primes $\{p_\ell\mid 1\le\ell\le k\}$ are not necessarily distinct and $k>1$), we have: $$\prod_{i=1}^kp_i=\prod_{i=1}^k\prod_{j=1}^{a_i}f(p_i^j)\cdot\prod_{S\subseteq\{p_\ell\mid 1\le\ell\le k\},1<|S|<n}f\left(\prod_{d\in S}d\right)\cdot f(n).$$Since: $$\prod_{i=1}^k\prod_{j=1}^{a_i}f(p_i^j)=\prod_{i=1}^k\prod_{j=1}^{a_i}p_i=\prod_{i=1}^kp_i^{a_i}$$the rest of the factors, including $f(n)$, must be $1$. So $f(p^k)=p$ for prime $p$ and $k\in\mathbb N$, and otherwise $f(n)=1$.
16.03.2023 15:36
How to prove uniqueness?