Let $d(n)$ be the number of positive divisors of a positive integer $n$. Let $\mathbb{N}$ be the set of all positive integers. Say that a function $F$ from $\mathbb{N}$ to $\mathbb{N}$ is divisor-respecting if $d(F(mn)) = d(F(m)) d(F(n))$ for all positive integers $m$ and $n$, and $d(F(n)) \le d(n)$ for all positive integers $n$. Find all divisor-respecting functions. Justify your answer.
Problem
Source:
Tags: Math Prize for Girls
anser
16.11.2018 17:22
I claim that the only divisor-respecting function $F:\mathbb{N}\rightarrow\mathbb{N}$ is $F(x)=1$. It is clear that this satisfies the constraints of a divisor-respecting function.
Since $d(F(1))\le d(1) = 1$, we need $d(F(1))=1$ and $F(1)=1$. For all primes $p$, $d(F(p))\le d(p)=2$. For the sake of contradiction, suppose that there exists a prime $q$ such that $d(F(q))=2$. Note that $d(F(q^2))=d(F(q))d(F(q))=4$, but $d(F(q^2))\le d(q^2)=3$, a contradiction. Thus, $d(F(p))=1$ which means that $F(p)=1$ for all primes $p$.
Now we will prove that $F(x)=1$ for all positive integers by strong induction. We have already shown that $F(1)=1$. Suppose $F(x)=1$ for all $1\le x < k$. We will show that $F(k)=1$. If $k$ is prime, we showed previously that $F(k)=1$. If $k$ is composite, there exist positive integers $1<a,b<k$ such that $k=ab$. Since $d(F(k))=d(F(a))d(F(b))=1$, this means that $F(k)=1$.
Therefore, $F(x)=1$ is the only divisor-respecting function. $\blacksquare$
Mr.Sharkman
14.07.2022 20:37
The only part of the solution that I think is off is the last part. A better way to finish than strong induction is let $k=p_{1} \cdot p_{2} \cdot .....\cdot p_{r}$, where all of the $p$'s are primes. Then use the multiplicative property to prove this is 1.