, 2024

Solution:
Let $f$ be a function satisfying these properties. From the first one, it follows that $f(1)=1$ and for each prime number $p$, $f(p)=q_p$ for some prime number $q_p$. Assume $p \neq 2$, the pair $(2, p)$ in property 2 gives
$$\operatorname{gcd}\left(q_2, q_p\right) = \operatorname{gcd}(f(2), f(p)) > f(\operatorname{gcd}(2, p)) = f(1) = 1$$
so $q_p = q_2$ for all $p$. Set $q = q_2$.
Denote by $d(n)$ the number of divisors of a positive integer $n$.
We will prove the following claim by induction on $k \geq 0$, the number of distinct prime divisors of $n$: For a positive integer $n$, $f(n)$ is a power of $q$.
The claim, together with the first property, imply that $f(n) = q^{d(n)-1}$.
For $k=0$ the claim is already proved.
For $k=1$, we need to prove that $f\left(p^m\right)$ is a power of $q$ for all positive $m$. The case $m=1$ was already proved. Assume now the result being proved for all positive integers $\leq m$. As $d\left(p^t\right) = t+1$, we then know $f\left(p^t\right) = q^t$ for all $t \leq m$. Now we consider $t = m+1$.
Let $r \neq p$ be a prime. Plug the pair $\left(p^{m-1} r, p^m\right)$ into the second property:
$$\operatorname{gcd}\left(f\left(p^{m-1} r\right), q^m\right) = \operatorname{gcd}\left(f\left(p^{m-1} r\right), f\left(p^m\right)\right) > f\left(p^{m-1}\right) = q^{m-1}$$
This implies $q^m$ divides $f\left(p^{m-1} r\right)$. Since $f\left(p^{m-1} r\right)$ has $2m$ divisors, and $v_q\left(f\left(p^{m-1} r\right)\right) \geq m$, it follows that $f\left(p^{m-1} r\right)$ does not have prime divisors other than $q$, since it would then have at least $2 \cdot \left(v_q\left(f\left(p^{m-1} r\right)\right)+1\right) > 2m$ divisors. Thus, $f\left(p^{m-1} r\right)$ is a power of $q$. And since it has $2m$ divisors, we must have $f\left(p^{m-1} r\right) = q^{2m-1}$.
Now, plug the pair $\left(p^{m+1}, p^{m-1} r\right)$ into the second property. We have
$$\operatorname{gcd}\left(f\left(p^{m+1}\right), q^{2m-1}\right) = \operatorname{gcd}\left(f\left(p^{m+1}\right), f\left(p^{m-1} r\right)\right) > f\left(p^{m-1}\right) = q^{m-1}.$$
Then $f\left(p^{m+1}\right)$ is divisible by $q^m$. If $f\left(p^{m+1}\right)$ had a prime factor other than $q$, it would have at least $2(m+1)$ divisors, but it has $m+2$ divisors and $2(m+1) > m+2$ since $m \geq 1$. Hence, $f\left(p^{m+1}\right)$ must also be a power of $q$. By induction, the proof is finished for $k=1$.
Suppose the claim is true for all integers $n$ with at most $k$ distinct prime factors, for some $k \geq 1$. In order to prove the claim for integers with $k+1$ distinct prime factors, it suffices
to show that for every positive integer $N$ with $k$ distinct prime factors, every positive integer $m$ and every prime $p$ which does not divide $N$, the number $f\left(N p^m\right)$ is a power of $q$. We will prove this by induction on $m$. The case $m=0$ follows from the previous induction hypothesis. Now suppose it has already been proved for a certain $m \geq 0$.
Let $s$ be a prime divisor of $N$. Consider the numbers $\left(N p^{m+1}, N s p^m\right)$. By the second property,
$$\operatorname{gcd}\left(f\left(N p^{m+1}\right), q^{d\left(N s p^m\right)-1}\right) = \operatorname{gcd}\left(f\left(N p^{m+1}\right), f\left(N s p^m\right)\right) > f\left(N p^m\right) = q^{d\left(N p^m\right)-1}$$
Then $q^{d\left(N p^m\right)}$ divides $f\left(N p^{m+1}\right)$. If $f\left(N p^{m+1}\right)$ has a prime factor other than $q$, it would have at least $2\left(d\left(N p^m\right)+1\right) = 2((m+1)d(N)+1) = (2m+2)d(N)+2$ divisors, but it has only $(m+2)d(N)$ divisors. Hence, $f\left(N p^{m+1}\right)$ must also be a power of $q$.
Finally, let us check that the function $f(n) = q^{d(n)-1}$ does satisfy the properties of the problem for any prime number $q$. The first property obviously holds. To check the second one, note that
$$\operatorname{gcd}(f(x), f(y)) = q^{\min (d(x), d(y))} > q^{d(\operatorname{gcd}(x, y))} = f(\operatorname{gcd}(x, y))$$
whenever $x \nmid y$ and $y \nmid x$.

Solution:
Firstly, one can prove that for any prime $p$ and any $m \geq 0$, $f\left(p^m\right) = q^m$, in the same way as in the first solution.
We will prove the claim this time by induction on $k = d(n)$. We notice again that the claim implies that $f(n) = q^{d(n)-1}$.
The cases $k=1,2,3$ are then already proved. Now suppose that for some $k \geq 3$ we have proved the claim for all positive integers $n$ with at most $k$ divisors.
Consider a positive integer $n$ with $k+1$ divisors. If $n$ is a power of a prime, then it is already proved that $f(n)$ is a power of $q$. Suppose $n$ is not a power of a prime. Consider distinct prime numbers $p_1$ and $p_2$ which divide $n$, such that $v_{p_1}(n) \leq v_{p_2}(n)$. Consider the number $\frac{n p_2}{p_1}$: its number of divisors is $\frac{v_{p_1}(n)(v_{p_2}(n)+2)}{(v_{p_1}(n)+1)(v_{p_2}(n)+1)} d(n)$, which is strictly less than the number of divisors of $n$. Thus, by induction hypothesis, $f\left(\frac{n p_2}{p_1}\right)$ is a power of $q$.
By applying the second property to the pair $\left(n, \frac{n p_2}{p_1}\right)$, we have
$$\operatorname{gcd}\left(f(n), q^{d\left(\frac{n p_2}{p_1}\right)-1}\right) = \operatorname{gcd}\left(f(n), f\left(\frac{n p_2}{p_1}\right)\right) > f\left(\frac{n}{p_1}\right) = q^{d\left(\frac{n}{p_1}\right)-1}$$
This implies that $q^{d\left(\frac{n}{p_1}\right)}$ divides $f(n)$. Again, if other primes than $q$ divided $f(n)$, it would have at least $2\left(d\left(\frac{n}{p_1}\right)+1\right)$ divisors. But $2\left(d\left(\frac{n}{p_1}\right)+1\right) = 2\left(\frac{v_{p_1}(n)}{v_{p_1}(n)+1} d(n)+1\right) > d(n)$. So $f(n)$ is a power of $q$ and the Claim is proved.
We finally check as in the first solution that $f(n) = q^{d(n)-1}$ satisfies the 2 properties for all prime $q$.