redacted

LLL2019 wrote: Not hard to prove based on induction on the number of divisors $x$ has, i think. The answer should be we assign primes $\{p_i\}_{i=1}^\infty$ and $f(x)=\prod_{i=1}^{d(n)} p_i$ Like yesterday, I did not think this through before posting (so that I can be the first poster ), there may very likely be a mistake. This seems incorrect, I think you'll have $\tau(f(x))=2^{\tau(x)}\neq \tau(x)$ this way

Nice problem. The solutions are $$\boxed{f(x)=q^{d(x)-1}} \ \ \forall x \in \mathbb{N}$$where $q$ is any fixed prime. Interestingly, showing that these work is itself non-trivial. The first condition is trivially satisfied, but for the second, you have to use the fact that if $a \mid b$ and $a<b$, then $f(a)<f(b)$. So if $x \nmid y$ and $y \nmid x$, $\gcd(x,y)$ is a proper divisor of both $x,y$, so $$f(\gcd(x,y))<\min\{f(x),f(y)\} = \gcd(f(x),f(y))$$since $f(x),f(y)$ are both powers of the same prime. Now the harder part. Putting $x=1$ gives $f(1)=1$ trivially, and if $x$ is prime, $f(x)$ has exactly two positive divisors, so $f(x)$ is also prime. Further, choosing $x,y$ to be distinct primes in (ii), we get $f(x)=f(y)=q$, say, for all primes $x$. Now assume $x=p^2$ for some prime $p$. $f(x)$ has exactly $3$ positive divisors, so $f(x)$ is also a square of a prime. Now, take $x=p^2$ and $y=p_1$ for any prime $p_1 \neq p$ in (ii) to get $f(x)=q^2$ whenever $x$ is a square of a prime. We prove by induction on $d(x)$ that $f(x)=q^{d(x)-1}$. Base cases $d(x)=1,2,3$ are done above. Assume the statement is true for all $d(x)<D$, for some $D \geq 4$. Let $n$ have exactly $D$ positive divisors. We investigate $f(n)$ in two different cases: Case I: $n$ has at least two prime divisors. In this case, choose two prime divisors $p_1,p_2$ of $n$ such that $v_{p_1}(n) \geq v_{p_2}(n)$, and note that we must have $d(n)>d(\frac{np_1}{p_2})$, by direct calculation; in more detail: $$\frac{d(\frac{np_1}{p_2})}{d(n)}=\frac{v_{p_2}(n)(v_{p_1}(n)+2)}{(v_{p_2}(n)+1)(v_{p_1}(n)+1)}<1.$$Further, these two numbers don't divide each other, and their $\gcd$ is $\frac{n}{p_2}$, which also has strictly less than $D$ positive divisors; say it has $D'$. Then again from direct calculation, $\frac{D'}{D}=\frac{v_{p_2}(n)}{v_{p_2}(n)+1} \geq \frac12$. Now, putting all this in (ii), we get $$\gcd(f(n),f(\frac{np_1}{p_2}))>q^{D'-1},$$and since $f(\frac{np_1}{p_2})$ is also a power of $q$ by induction hypothesis, $q^{D'} \mid f(n)$. If $f(n)$ has a prime factor apart from $q$, then $$d(f(n)) \geq 2(D'+1)>2D' \geq D,$$contradiction! Hence $f(n)$ is a power of $q$, and it must be $q^{D-1}$ due to the divisors condition. Case II: $n=p^{D-1}$ for some prime $p$. Consider $m=p^{\lfloor\frac{D}{2}\rfloor-1}p_1$ where $p_1 \neq p$. Then $d(m)=2 \lfloor \frac{D}{2} \rfloor \leq D$, and since $D \geq 4$, $m$ has at least two prime divisors. Hence by induction hypothesis or Case I, $f(m)=q^{2 \lfloor \frac{D}{2} \rfloor-1}$. Now, clearly $n,m$ don't divide each other, and their $\gcd$ is $p^{\lfloor \frac{D}{2} \rfloor-1}$, which again has strictly less than $D$ positive divisors. So by (ii), $\gcd(f(n),f(m))>q^{ \lfloor \frac{D}{2} \rfloor-1}$, and since $f(m)$ is also a power of $q$, this implies $q^{ \lfloor \frac{D}{2} \rfloor} \mid f(n)$. Again, if $f(n)$ has a prime divisor apart from $q$, we would get $$d(f(n)) \geq 2(\lfloor \frac{D}{2} \rfloor+1)>D,$$contradiction! Hence $f(n)$ is a power of $q$, so must be $q^{D-1}$, as required. And we are done by induction. $\blacksquare$

1024th post Obviously $f(1)=1$ and $f(\text{prime})=\text{prime}$. Suppose $p_1,p_2$ are primes, then $P(p_1,p_2): \gcd(f(p_1),f(p_2))>1$. However, since both are primes, we have $f(p_1)=f(p_2)=P$ where $P$ is a prime constant. Now for any $y$, pick a sufficiently large prime $p_1$. $P(p_1,y): \gcd(P,f(y))>1$, which means $P\mid f(y)$ for all $y>1$. In particular, for any prime $q$, $f(P^{q-1})=P^{q-1}$, since only $P^{q-1}$ has $q$ divisors and is a multiple of $P$. We now show by induction that $f(P^x)=P^x$ for any positive integer $x$. Base cases $x=1,2$ are done. Suppose $f(P^{x-1})=P^{x-1}$ and $f(P^{x-2})=P^{x-2}$. Pick any prime $q$. $P(P^{x-1},qP^{x-2}): \gcd(P^{x-1},f(qP^{x-2}))>f(P^{x-2})=P^{x-2}$. This means that $P^{x-1}\mid f(qP^{x-2})$. However, $f(qP^{x-2})$ has $2(x-1)$ divisors, so it must be exactly $P^{2(x-2)}$. (If it has a different prime factor, then it has at least $2x$ divisors.) Now, take $P(P^x,qP^{x-2}): \gcd(f(P^x),P^{2(x-1)})>P^{x-2}$. Thus, we must have $P^{x-1}\mid f(P^x)$. Since it has $x+1$ divisors, it must be exactly $P^x$. We now show that $f(x)=P^{d(x)-1}$ for all $x$ by induction on the number of prime factors of $x$ that are not $P$. The base case, where all prime factors are $P$, is done above. Pick any number $N$ and let $N=qT$ where $q\ne P$ is a prime. Then, by the induction hypothesis, $f(PT)=P^{d(PT)-1}$ and $f(T)=P^{d(T)-1}$. Hence, $P(PT,N): \gcd(P^{d(PT)-1},f(N))>P^{d(T)-1}$. This means that $P^{d(T)}\mid f(N)$. Suppose that $f(N)$ has a prime factor not $P$. Then, it has at least $2(d(T)+1)$ divisors. Write $N=q^xR$ where $q\nmid R$. Then, $$2(xd(R)+1)=2(d(T)+1)\le d(N)=d(q^xR)=(x+1)d(R),$$which can never happen. Thus, by induction, $f(x)=P^{d(x)-1}$ for all $x$ and some fixed prime $P$, which on checking works.

This problem is nothing more than routine. The idea is very simple: after a quick substituion of some numbers, you easily get that the answer is most probably: if $p$ is any prime, then $f(n)=p^{d(n)-1}$. It can be proven that all functions have this form by using induction on $d(n)$

Excellent problem!! I enjoyed this problem a lot! Answer: $f(x) = p^{\tau(x) - 1}$ for some prime $p$. (As usual, $\tau(n)$ is the number of divisors of $n$) Note that $f(1) = 1$ and $f(q)$ is a prime for all prime $q$ and $\gcd(f(p_1), f(p_2)) > f(1) = 1$, so $f(p_1) = f(p_2) = p$ for some prime $p$. In particular, $f(q) = p$ for all prime $q$. Now let $n$ be an arbitrary positive integer and take a prime $q > n$. Then $\gcd(f(q), f(n)) > f(1) = 1$, so $p \mid f(n)$. Let $s$ be an arbitrary prime. Then $\tau(f(q^{s-1})) = \tau(q^{s-1}) = s$, so $f(q^{s-1})$ is a power of prime. Since $p \mid f(q^{s-1})$, thus $f(q^{s-1}) = p^{s-1}$ for all primes $q, s$. Claim 1: $f(q^{s-1}r) = p^{2s-1}$ for all primes $q, s, r$. Proof. Let $t$ be a large enough prime. Since $\gcd(f(q^{s-1}r), f(q^{t-1})) = \gcd(f(q^{s-1}r), p^{t-1}) > \gcd(q^{s-1}) = p^{s-1} \implies p^s \mid f(q^{s-1}r)$. Since $\tau(f(q^{s-1}r)) = \tau(q^{s-1}r) = 2s$, so combining it with the fact that $p^s \mid f(q^{s-1}r)$, we see that $f(q^{s-1}r)$ cannot have another prime divisor other than $p$. Therefore, we may conclude $f(q^{s-1}r) = p^{2s-1}$. $\blacksquare$ Claim 2: $f(q^a) = p^a$ for all prime $q$ and all positive integer $a$. Proof. Let $s$ be the largest prime not exceeding $a$. Then we have $a \ge s > s-1$, so $\gcd(f(q^a), f(q^{s-1}r)) > f(q^{s-1}) = p^{s-1}$ and if we let $r$ be a prime, then $f(q^{s-1}r)$ is a power of $p$, so $p^s$ must divide $f(q^a)$. By Bertrand's postulate, there exists a prime between $\frac{a}{2}$ and $a$, so we may assume $s \ge \frac{a}{2}$. Now assume that $f(q^a)$ has a prime divisor other than $p$. Then $f(q^a)$ has at least $2(s+1)$ divisors $\implies a + 1 \ge 2(s+1) \ge 2(\frac{a}{2} + 1) = a + 2$, a contradiction. Hence $f(q^a) = p^a$. $\blacksquare$ Now we'll prove by induction on the number of prime divisors of $n$ that $f(n) = p^{\tau(n) - 1}$. Induction base is claim 2. Now assume that it's true on $k$ and we'll prove that for $k+1$.We'll prove by induction on $i$ that $f(p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}r^i) = p^{(a_1+1)(a_2+1)\cdots (i+1)-1}$ for all primes $p_1, p_2, \dots, p_k$ and all positive integers $a_1, a_2, \dots, a_k$. Induction base $i = 0$ is clear. Now assume it's true on $i$ and let's prove on $i+1$. By induction hypothesis, $f(p_1^{a_1+1}p_2^{a_2+1}\cdots p_k^{a_k+1}r^i) = p^{(a_1+2)(a_2+2)\cdots (a_k+2)(i+1) - 1}$, so $\gcd(f(p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}r^{i+1}), f(p_1^{a_1+1}p_2^{a_2+1}\cdots p_k^{a_k+1}r^i)) > f(p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}r^i) = p^{(a_1+1)(a_2+1)\cdots (a_k+1)(i+1)-1}$. Thus $p^{(a_1+1)(a_2+1)\cdots (a_k+1)(i+1)} \mid f(p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}r^{i+1})$. From this, we can easily conclude that $f(p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}r^{i+1})$ is a power of $p$. Therefore, the induction is completed and $f(n) = p^{\tau(n) - 1}$ for all $n \in \mathbb{N}$, so we're done. $\blacksquare$

The answer is $f(x)=c^{\tau(x)-1}$ where $c$ is prime(more specific $c=f(2)$) For this we do induction after $\tau(x)$: Base case: $n=1$ and $n$ is prime For $n=1$ trivial and for prime just put $(f(p),f(q))>1$ and since both are prime it means $f$ is constant over primes so base case is done. Induction step:We have $\tau(x)=k$ and we want $f(x)=c^{k-1}$ There are 2 cases: Case 1: $\omega(n)\ge 2$ Then let $n=p_1^{\alpha_1}\cdot p_2^{\alpha_2} \dots p_t^{\alpha_t}$ and WLOG $\alpha_2\ge \alpha_1$.Then choose $y=p_1^{\alpha_1-1}\cdot p_2^{\alpha_2+1} \dots p_t^{\alpha_t}$ We have $\tau(y)<\tau(x)$ so we know $f(y)$ by induction hyphotesis. We get $(f(x),c^{\alpha_1(\alpha_2+2)\dots(\alpha_t+1)-1})>c^{\alpha_1(\alpha_2+1)\dots(\alpha_t+1)-1}$.Let $f(x)=c^j\cdot l$ where $l$ is not divisible by $c$ and $j\ge \alpha_1(\alpha_2+1)\dots(\alpha_t+1)$.Easy bounding yelds $l=1$ so $f(x)$ is a power of $c$ and we are done. Case 2: $x=p^{k-1}$ where $p$ is prime. Take $x=\lfloor \frac{k}{2} \rfloor -1$ and $y=p^x\cdot q$.Then $\tau(y)=2(x+1)\le k$ and we know $y$ is not power of prime so $f(y)=c^{\tau(y)-1}=c^{2x+1}$.Applying to x and y we have $(f(p^{k-1}),c^{2x+1})>c^x$ so $f(p^{k-1})=c^a\cdot b$ with $a\ge \lfloor \frac{k}{2} \rfloor$ then bounding again yelds $b=1$ so $f(x)$ is a power of $c$ and we are done.

The answer is $\boxed{f(x)=p^{d(x)-1}}$, which clearly satisfies the conditions. Here, $d(x)$ denotes the number of divisors of $x$ and $p$ is a fixed prime. Note that for $N=\prod_{i=1}^k p_i^{n_i}$, where $p_1, p_2,\dots, p_k$ are distinct primes, $d(N)=\prod_{i=1}^k (n_i+1)$. Let $P(x, y)$ denote the assertion: $$\gcd(f(x), f(y)) > f(\gcd(x, y)).$$ Due to the first condition, it is easy to see that $f(1)=1$ and $f(q) = p$, where $p$ and $q$ are (not necessarily distinct) primes. If we consider any two primes $p_1$ and $p_2$, $P\left(p_1, p_2\right)\implies \gcd(f(p_1), f(p_2))>1$, but this suggests that they do have a common factor. So, $f(q)=p$ for any prime $q$. For some $x$, pick a prime $Q$ such that $\gcd(Q, x)=1$. Then, $P(Q, x) \implies \gcd(f(Q), f(x))>1$ and as $f(Q)=p$, $p\mid f(x) \,\, \forall x\in\mathbb{N}$. Note that for primes $q$ and $r$, $f(q^{r-1})$ has $r$ divisors. But the number of divisors of a number is a prime only if the number is a prime power, and as $p\mid f(q^{r-1})$, we can deduce that $f(q^{r-1})=p^{r-1}$. Thus, $f(q^2)=p^2$. Lemma: For a prime $p$, if $p^{x-1}\mid n$ and $\left\lfloor\frac{d(n)}{x}\right\rfloor=1$, then $n=p^{d(n)-1}$. Proof. Suppose not. So, $n=kp^{x-1}$, where $\gcd(p, k)=1$. Then, $$d(n)=xd(k) \implies 1 \leq d(k)=\frac{d(n)}{x}< 2 \implies d(k)=1.$$This forces $k=1$, and $x=d(n)$, as desired. $\blacksquare$ We show that $f(q^n)=p^n$ by strong induction. We have already covered the base cases $n=1, 2$. Suppose it is true for $n\leq k$. For a prime $r\neq q$, $P(q^k, rq^{k-1}) \implies \gcd(f(q^k), f(rq^{k-1}))>p^{k-1}$. Since $f(q^k)=q^k$, we can say that $p^k\mid f(rq^{k-1})$. According to the first condition, $f(rq^{k-1})$ has $2k$ divisors. As $\left\lfloor\frac{2k}{k+1}\right\rfloor=1$, we can ensure that $f(rq^{k-1})=p^{2k-1}$ by our lemma. Again, $$P(q^{k+1}, rq^{k-1}) \implies \gcd(f(q^{k+1}), f(rq^{k-1}))=\gcd(f(q^{k+1}), p^{2k-1})>p^{k-1} \implies p^k\mid f(q^{k+1})$$and as $\lfloor{\frac{k+2}{k+1}\rfloor}=1$, $f(q^{k+1})=p^{k+1}$ as desired. Next, we show that $f\left(\prod_{i=1}^m q_i^{n_i}\right)=p^{\prod_{i=1}^m (n_i+1)-1}$ for distinct primes $q_1, q_2, \dots, q_m$ and any $n_1, n_2, \dots, n_m$ by induction on $m$. We have already proved the base case. Suppose it is true for $m=k$. We wish to show that it is true for $m=k+1$. To achieve this, we must prove that $f\left(\prod_{i=1}^{k+1} q_i^{n_i}\right)=p^{\prod_{i=1}^{k+1} (n_i+1)-1}$ for any $n_{k+1}.$ Again, we proceed by induction on $n_{k+1}.$ To prove the base case: $$P\left(f\left(q_{k+1}\prod_{i=1}^k q_i^{n_i}\right), f\left(\prod_{i=1}^k q_i^{n_i+1}\right)\right)\implies \gcd\left(f\left(q_{k+1}\prod_{i=1}^k q_i^{n_i}\right), f\left(\prod_{i=1}^k q_i^{n_i+1}\right)\right)=\gcd\left(f\left(q_{k+1}\prod_{i=1}^k q_i^{n_i}\right), p^{\prod_{i=1}^{k} (n_i+2)-1} \right),$$and $$\gcd\left(f\left(q_{k+1}\prod_{i=1}^k q_i^{n_i}\right), p^{\prod_{i=1}^{k} (n_i+2)-1} \right)>p^{\prod_{i=1}^k (n_i+1)-1} \implies p^{\prod_{i=1}^k (n_i+1)} \mid f\left(q_{k+1}\prod_{i=1}^k q_i^{n_i}\right),$$but $$\left\lfloor\left(\frac{2\prod_{i=1}^k (n_i+1)}{\prod_{i=1}^k (n_i+1)+1}\right)\right\rfloor=1 \implies f\left(q_{k+1}\prod_{i=1}^k q_i^{n_i}\right)=p^{2\prod_{i=1}^k (n_i+1)-1}$$by our lemma, as desired. Suppose it is true for $n_{k+1}=l$. To prove that it holds for $n_{k+1}=l+1$, observe that $$P\left(f\left(q_{k+1}^{l+1}\prod_{i=1}^k q_i^{n_i}\right), f\left(q_{k+1}^l\prod_{i=1}^k q_i^{n_i+1}\right)\right)\implies \gcd\left(f\left(q_{k+1}^{l+1}\prod_{i=1}^k q_i^{n_i}\right), f\left(q_{k+1}^l\prod_{i=1}^k q_i^{n_i+1}\right)\right)=\gcd\left(f\left(q_{k+1}^{l+1}\prod_{i=1}^k q_i^{n_i}\right), p^{(l+1)\prod_{i=1}^{k} (n_i+2)-1} \right),$$and $$\gcd\left(f\left(q_{k+1}^{l+1}\prod_{i=1}^k q_i^{n_i}\right), p^{(l+1)\prod_{i=1}^{k} (n_i+2)-1} \right)>p^{(l+1)\prod_{i=1}^k (n_i+1)-1} \implies p^{(l+1)\prod_{i=1}^k (n_i+1)} \mid f\left(q_{k+1}^{l+1}\prod_{i=1}^k q_i^{n_i}\right),$$but $$\left\lfloor\left(\frac{(l+2)\prod_{i=1}^k (n_i+1)}{(l+1)\prod_{i=1}^k (n_i+1)+1}\right)\right\rfloor=1 \implies f\left(q_{k+1}^{l+1}\prod_{i=1}^k q_i^{n_i}\right)=p^{(l+2)\prod_{i=1}^k (n_i+1)-1}$$by our lemma, which finishes both of our hypotheses. By citing the fundamental theorem of arithmetic, we are done. $\square$

this is probably the most beautiful problem i've ever seen in like multiple months. wow. Let $P(x,y)$ be the assertion. First, note $f(1)=1$. Now notice that $f(p)$ is always prime for prime $p$. Then $P(p,q)$ for distinct $p$ and $q$ yields \[\gcd(f(p),f(q))>1\implies f(p)=f(q)=P\]where $P$ is some prime. Clearly, then, all primes output to $P$. Let $d$ be the divisor-counting function. The claim is that \[f(x)=P^{d(x)-1}\]which obviously works. We prove this by induction on $d(x)$. We already handled the base cases of $d(x)\in \{1,2\}$. Suppose we want to show that $f(x_n)=P^{n-1}$ where $x_n$ has $n\ge 3$ divisors, having proven the problem for $d(x)<n$. The idea is to consider some divisor $D$ where $d(D)\ge \frac{n}{2}$, then choose $y_n$ such that $d(y_n)<n=d(x_n)$ and $\gcd(x_n,y_n)=D$. The trickier part is proving that such a $y_n$ exists. Actually, it isn't too difficult. The first case is as follows: if at least two primes $p$ and $q$ divide $x_n$, then WLOG $1\le a=\nu_p(x_n)\le \nu_q(x_n)=b$. Set \[y_n := x_n\cdot \frac{q}{p},\]\[D := x_n\cdot \frac{1}{p}.\]Then \[\frac{d(y_n)}{d(x_n)}=\frac{a}{a+1}\cdot \frac{b+2}{b+1}<1\iff a<b+2\]which is true. Additionally \[\frac{d(D)}{d(x_n)}=\frac{a}{a+1}\ge \frac{1}{2}\iff a\ge 1\]which is true. Hence if $x_n$ is not a prime power then \[\nu_P(f(x_n))>\nu_P(f(D))\ge \frac{n}{2}-1\implies \nu_P(f(x_n))\ge \frac{n-1}{2}.\]If $f(x_n)$ is divisible by another prime $q$ then \[n=d(f(x_n))\ge \frac{n+1}{2}\cdot 2=n+1\]which is a contradiction. Hence $f(x_n)=P^{n-1}$. It remains to solve the case where $x_n=p^{n-1}$. Take cases on the parity of $n$. If $n=2k$, then write \[D := p^{k-1}\]\[y_n := p^{k-1}\cdot q\]and notice despite $d(y_n)=n$ that $P(x_n,y_n)$ yields \[\gcd(f(x_n),P^{n-1})>P^{k-1}\implies P^k\mid f(x_n)\implies f(x_n)=P^{n-1}.\] If $n=2k+1$, then write \[D := p^{k-1}\]\[y_n := p^{k-1}\cdot q\]and notice \[\gcd(f(x_n),P^{n-2})>P^{k-1}\implies P^k\mid f(x_n)\implies f(x_n)=P^{n-1}.\] We are done. $\blacksquare$

Let $d(x)$ be the number of divisors of $x$. We claim that the only solutions are $f(x)=c^{d(x)-1}$, where $c$ is a prime number. This works because... TADA it does! Note that $1$ and $f(1)$ have same number of divisors, which forces $f(1)=1$. From condition i, if $p$ is a prime then $f(p)$ is a prime and $f(p^2)$ is the square of a prime. Let $f(2)=c$ be a prime. Then, $\gcd(f(2),f(3))>f(1)=1$ and since $f(2),f(3)$ are both primes, we must have $f(2)=f(3)$. As a corollary to ii, we have $\gcd(f(x),f(x+1))>1$ for every $x>1$. It follows that there is a common factor in $f(4)$ and $f(3)$, which forces $f(4)=f(3)^2=c^2$. Similarly, $\gcd(c^2,f(5))=\gcd(f(4),f(5))>1$ which forces $f(5)=c$. Now what about $f(6)$? Unfortunately, $f(6)$ is either the product of distinct primes or the cube of a prime, so you can't be sure. However, note that in ii, $4\nmid6$ and $6\nmid4$, which means $\gcd(c^2,f(6))=\gcd(f(4),f(6))>f(2)=c$. So, if $f(6)=cc'$ were true for some prime $c'\ne c$, then $c<\gcd(c^2,f(6))=c$, which is absurd. Hence, $f(6)=c^3$ must be true. It is left for the reader to try and prove $f(8)=c^3$. (Just kidding, idea's at the end of the solution.) The ideas on this paragraph form the basis of the problem and are essential in completing it. The above idea can be generalized: If $x$ is prime, then $f(x)=c$ and $f(x^2)=c^2$. The outline is: if $x>2$ is prime, $\gcd(f(x),f(2))>1$, which means $f(x)=f(2)=c$, because both numbers are prime. Similarly, $f(x^2),f(4)(=c^2)$ have common factor, which means $c\mid f(x^2)$ and $f(x^2)=c^2$. Now, for any positive integer $x$ if $x'$ is a prime, then $f(x')=c$ and $\gcd(f(x),c)>f(\gcd(x,x'))$, which means $c\mid f(x)$ for all $x$. We now induct on $d(x)$ to show that $f(x)=c^{d(x)-1}$ holds for all $x$. Base cases have been done with. Suppose $n$ is NOT a power of a prime. Then, we can write $n=\text{product of powers of primes}$. Suppose $p^e\mid \mid n$ and $q^f\mid \mid n$ with $e\geq f>0$. Then, note that $d(n)=\prod_{e}(e+1)$. If we consider $\frac{np}q$, then the divisor count is definitely reduced, because $\frac{e+2}{e+1}<\frac{f+1}f$. From induction hypothesis, we already have: $f\left(\frac{np}q\right)=c^{d\left(\frac{np}q\right)-1}$. Then, using ii, we have \[\gcd\left(f\left(\frac{np}q\right),f(n)\right)>f\left(\gcd\left(\frac{np}q,n\right)\right)=f\left(\frac{n}q\right)\]Since $f\left(\frac{np}{q}\right)$ and $f\left(\frac{n}p\right)$ are both powers of $c$, it means that \[v_c\left(f(n)\right)>v_c\left(f\left(\frac nq\right)\right)\]Let $f(n)=c^vs$ where $c\nmid s$. Then, $d(f(n))=(v+1)d(s)=d(n)$ by i, and $v+1>d\left(\frac nq\right)$. However, we also know that $d(s)<\frac{d(n)}{d\left(\frac nq\right)}=\frac{f+1}{f}\leq2$, which forces $d(s)=1$ and hence $s=1$. So, $f(n)=c^v$, and hence $v=d(n)-1$ is forced as well. So, we only need to consider the case when $n$ is a power of a prime. Let $n=p^u$, where $u+1=d(n)$. If $u+1$ is prime, then we're done because $c\mid f(n)$ and $n$ must be a $u$th power of some prime. So, assume that $u+1$ is composite. Then, there exists $n'$ such that $n'$ is NOT a perfect power of a prime, and $d(n')=u$. From above arguments, we have that $f(n')=c^u$. From ii, we have that $\gcd(f(n),f(n'))>f\left(\gcd(n,n')\right)$. Let $f(n)=c^wt$ where $c\nmid t$. Suppose $t>1$. So, $w<u$. Then, taking $n'=p^wt'$, where $p,c\nmid t'$ and $d(t)=d(t')$, we see that \[c^w=\gcd(f(n),f(n'))>f(\gcd(n,n'))=f(p^w)=c^w,\]which is impossible. The induction is complete. $\blacksquare$

Imagine wasting an hour because you thought the answer was something else....

Solution from Twitch Solves ISL: The answer is \[ f(x) = \ell^{d(x)-1} \]where $\ell$ is a fixed prime, and $d(\bullet)$ is the divisor counting function. This works, because when $x \nmid y$ and $y \nmid x$ we obviously have $d(\gcd(x,y)) < \min(d(x), d(y))$. So now we prove this is the only solution. Obviously $f(1) = 1$; we ignore this case further. Note that $f(p)$ is always a prime for each prime $p$. But if $p$ and $q$ are two different primes, then apparently \[ \gcd\left( f(p), f(q) \right) > f(\gcd(p,q)) = f(1) \ge 1\]and yet the left-hand side is the GCD of two primes. So this could only happen if they are the same prime; hence we conclude $f(p)$ is constant, say $\ell$. Claim: Every output of $f$ besides $f(1)$ must be a multiple of $\ell$ Proof. To show $\ell \mid f(x)$ for $x > 1$, take $y$ to be any prime not dividing $x$. Then $\gcd(f(x), \ell) > 1$, as needed. $\blacksquare$ This allows us to extend our earlier claim as follows: Claim: If $p_1$, \dots, $p_k$ are distinct primes and $q_1$, \dots, $q_k$ are primes then \[ f\left( p_1^{q_1-1} \dots p_k^{q_k-1} \right) = \ell^{q_1 \dots q_k - 1}. \]Proof. By induction on $k$. For the base case $k = 1$, we know $f(p^{q-1})$ needs to be a multiple of $\ell$, and the only multiple of $\ell$ with $q$ prime divisors is $\ell^{q-1}$. Suppose $k \ge 2$ and WLOG $q_1 \ge q_2 \ge \dots \ge q_k$. We let $p$ be any other prime. Then \[ \gcd\left( f(p_1^{q_1-1} \dots p_k^{q_k-1}), f(p_1^{q_1-1} \dots p_{k-1}^{q_{k-1}-1}p) \right) > f\left( p_1^{q_1-1} \dots p_{k-1}^{q_{k-1}-1} \right) = q_1 q_2 \dots q_{k-1}. \]Hence $f(p_1^{q_1-1} \dots p_k^{q_k-1})$ is divisible by $\ell^{q_1 \dots q_{k-1}}$. There are no proper divisors of $q_1 \dots q_k$ exceeding $q_1 \dots q_{k-1}$, so this forces $f(p_1^{q_1-1} \dots p_k^{q_k-1}) = \ell^{q_1 \dots q_k - 1}$ exactly. $\blacksquare$ We will now attack the main problem in the following presentation: Claim: Suppose $p_1$, \dots, $p_k$, $r_1$, \dots, $r_m$ are pairwise distinct primes, and $q_1$, \dots, $q_k$ are also prime numbers, and $e_1, \dots, e_m \ge 2$. Let \[ x = p_1^{q_1-1} \dots p_k^{q_k-1} r_1^{e_1-1} \dots r_m^{e_m-1} \]and set \[ n = d(x) = q_1 \dots q_k e_1 \dots e_m. \]Then $f(x) = \ell^{n-1}$. Proof. The proof is by induction on $m$, with the base case $m=0$ already done. For the inductive step, look at $e_m$. If $e_m$ is prime there is nothing to do. Otherwise, $e_m \ge 3$, and we can take a prime $q$ satisfying \[ \frac{e_m}{2} < q < e_m. \]and let $z$ be a random other prime not appearing already; then choosing \begin{align*} y &= p_1^{q_1-1} \dots p_k^{q_k-1} r_1^{e_1-1} \dots r_{m-1}^{q-1} z \\ \gcd(x,y) &= p_1^{q_1-1} \dots p_k^{q_k-1} r_1^{e_1-1} \dots r_{m-1}^{q-1}. \end{align*}Then \begin{align*} f(y) &= \ell^{2q_1 \dots q_k \cdot e_1 \dots e_{m-1} \cdot q - 1} > \ell^{n-1} \\ f(\gcd(x,y)) &= \ell^{q_1 \dots q_k \cdot e_1 \dots e_{m-1} \cdot q - 1} = \ell^{n \cdot \frac{q}{e_m} - 1} > \ell^{\frac n2 - 1}. \end{align*}It follows that $\nu_{\ell}(f(x)) + 1 > \frac n2$. We know $n = d(f(x)) = \prod_{p} \left( \nu_p(f(x)) + 1 \right)$. If a number greater than $n/2$ appears on the product of the RHS, then in fact the product consists only of $n$. This completes the induction. $\blacksquare$

Does this work? Sketch: We claim the only function is $f(x) = p_0^{d(x) - 1}$ for a fixed prime $p_0$. Easy to see that it satisfies the condition. Now the idea is to strong induct on $d(x)$. In particular let's say $d(x) < n \implies$ above function only; and prove $d(x) = n$ case. If $x$ is a prime power $p^a$, we choose $y = p^{\left \lceil \frac{a-2}{2} \right \rceil}q$; and otherwise, if $x = \prod_{i = 1}^k p_i^{a_i}$ with $a_1 \ge \cdots \ge a_k$, then consider $y = p_1^{a_1 + 1} p_2^{a_2} \cdots p_k^{\left \lceil \frac{a_k - 1}{2} \right \rceil}$. Then $P(x, y)$, first on non-prime-powers, then on prime powers, should give the desired result.

$P(x,y): \gcd(f(x),f(y))>f(\gcd(x,y))$ We will show that the only solution is $f(n)=a^{\tau(n)-1}$ where $\tau(n)$ denotes the number of positive divisors of $n$ and $a$ is an arbitrary prime number (but fixed). We clearly have that $f(1)=1$ and $f(n)=p$ if $n$ is prime where $p$ is also a prime (not fixed). Now from $P(n,m)$ where $n$ and $m$ are primes we deduce that $f(n)=a$ where $a$ is a arbitrary, but fixed, prime number. We can similarly get that $f(n^2)=a^2$ for all prime $n$. Now we proceed by induction on $\tau(n)$. Case 1. $n$ is squarefree. Let $n=p_1\cdot\ldots\cdot p_k$ be the prime factorization of $n$ and let $m=p_1\cdot\ldots\cdot p_{k-2}\cdot p_{k-1}^2$. We have that $\tau(m)=2^{k-2}\cdot 3$ and $\tau(n)=2^k$ so $\tau(m) < \tau(n)$, hence $f(m)=a^{2^{k-2}\cdot 3-1}$. Now we have that $\gcd(n,m)= p_1\cdot\ldots\cdot p_{k-2}\cdot p_{k-1}$ so clearly $f(\gcd(n,m))=a^{2^{k-1}-1}$. Therefore, $\gcd(f(n), a^{2^{k-2}\cdot 3-1}) > a^{2^{k-1}-1}$ hence we get that $a^{2^{k-1}}\mid f(n)$. So $f(n)$ can’t have any other prime factors, hence $f(n)=a^{2^k-1}$. Case 2. $n$ isn’t squarefree and $n\neq p^{t}$ Let $n=p_1^{q_1}\cdot \ldots\cdot p_k^{q_k}$ be the prime factorization of $n$ such that $q_1\le q_2\le \ldots\le q_k$ (notice that $q_k\ge 2$) and let $m= p_1^{q_1}\cdot \ldots\cdot p_{k-1}^{q_{k-1}+1}\cdot p_k^{q_k-1}$. Notice that $d=\tau(m)=(q_1+1)\cdot\ldots\cdot(q_{k-1}+2)\cdot q_k < \tau(n)$ so $f(m)=a^{d-1}$. Now $\gcd(n,m)= p_1^{q_1}\cdot \ldots\cdot p_{k-1}^{q_{k-1}}\cdot p_k^{q_k-1}$ so $e=\tau(\gcd(n,m)) < \tau(n)$, hence $f(\gcd(n,m))=a^{e-1}$. So we get that $\gcd(f(n),a^{d-1})>a^{e-1}\Rightarrow a^e\mid f(n)$ but since $q_k\ge 2$ we have $e>\frac{\tau(n)}{2}$ hence $f(n)$ can’t have any other prime factors. Therefore $f(n)=a^{\tau(n)-1}$. Case 3. $n=p^k$, where $p$ is a prime a number. Let $m=p^{\left\lfloor \frac{k-2}{2}\right\rfloor}\cdot q$ where $q$ is a different prime number. We have that $m$ isn’t a power of a prime hence $\tau(m)\le n \Rightarrow f(m)=a^ {\left(\left\lfloor \frac{k-2}{2}\right\rfloor+1\right)\cdot 2-1}$. And clearly $f(\gcd(n,m))=a^{\left\lfloor \frac{k-2}{2}\right\rfloor-1}$, hence $a^{\left\lfloor \frac{k-2}{2}\right\rfloor}\mid f(n)$. Now if $k$ is even, it can’t have any other prime factor because it can’t be at a power of $1$ since it is even and if its power is $2$ or higher, we get a size contradiction. If $k=2t+1$, let $m=p^t\cdot q$ since $\tau(m)=\tau(n)$ and $m$ isn’t a power of a prime, we get that $f(m)=a^{2t+1}$ and we clearly have $f(\gcd(n,m))=a^t$. Therefore $a^{t+1}\mid f(n)$ so $f(n)$ can’t have any other prime factors, hence $f(n)=a^{2t+1}$. $\square$

We will prove that the only solutions are $$f(x)=q^{d(x)-1}$$for a certain prime $q$. This clearly satisfies $(i)$ and $(ii)$ as $$\gcd(f(x), f(y))=q^{\min\{d(x)-1, d(y)-1\}}>q^{d(\gcd(x, y))-1}=f(\gcd(x, y)),$$where we used, $d(\gcd(x, y)) < \min(d(x), d(y))$ which comes from $\gcd(x, y) \mid x, y$ and $\gcd(x, y) \neq x,y$. Claim 1. $f(p)=q$ and $f(p^2)=f(q^2)$ for all primes $p$ Proof Notice that $d(p)= 2$, so $f(p)$ is a prime for all p. For the sake of contradiction, suppose $f(p)=q$ and $f(p')=q'$. Then $\gcd(f(p), f(p')=1$ so $1>f(\gcd(p, p'))$. However, this is a contradiction as $f$ only has natural outputs. We also have $d(p^2)=3$ so $f(p^2)$ must be a prime squared too. Now consider a prime $r$ and plug in $(p^2, r)$ to get $f(p^2)=q^2$ by the same argument as above. We now proceed by strong induction on $n$. Base step. For $n=1$, we indeed have $f(n)=q^{d(1)-1}=q^0=1$ as $1$ is the only number with $1$ divisor. Inductive step. So now, assume that $f(i)=q^{d(i)-1}$ for all $i$ less than $n$. For the sake of contradiction, suppose $f(n)=q^{\alpha}p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$ and $n=q^{\beta}q_1^{\beta_1}q_2^{\beta_2}\cdots q_k^{\beta_k}$ where $f(n)$ has atleast two prime divisors. We now distinguish two seperate cases. Case 1. $n$ has more than one prime divisor We now distinguish two further cases, depending on whether $q>q_k$ or not. Case 1.1. $q>q_k$ Choose $i=q^{\beta-1}q_1^{\beta_1}q_2^{\beta_2}\cdots q_k^{\beta_k+1}$. We have $\gcd(f(n), f(i))=q^{\min\{\alpha, d(i)-1\}}$ and $f(\gcd(n, i))=q^{d(q^{\beta-1}q_1^{\beta_1}q_2^{\beta_2}\cdots q_k^{\beta_k})-1}=q^{\frac{d(n)\beta}{\beta+1}-1}$ so $$\min\{\alpha, d(i)-1\}>\frac{d(n)\beta}{\beta+1}-1$$however, we know $\alpha+1\leq \frac{d(n)}{2}$ and $d(i)-1>\frac{d(n)\beta}{\beta+1}-1 \geq \frac{d(n)}{2}-1$ so in fact $\min\{\alpha, d(i)-1\}=\alpha$. Hence, $$\min\{\alpha, d(i)-1\}=\alpha\leq \frac{d(n)}{2}-1$$. But $\frac{d(n)\beta}{\beta+1}-1\geq \frac{d(n)}{2}-1$ so this implies, $\frac{d(n)}{2}-1>\frac{d(n)}{2}-1$, which is a clear contradiction. Case 1.2. $q<q_k$ Choose $i=q^{\beta+1}q_1^{\beta_1}q_2^{\beta_2}\cdots q_k^{\beta_k-1}$ and repeat the same argument as in Case 1.1. Case 2. $n=p^k$ for a certain prime $p$. Recall that we already have proven the result for $k=1,2$ so we only have to consider the cases where $k\geq3$. Choose $i=p^{k-2}\cdot3$ if $p\neq 3$ and $i=p^{k-2}\cdot2$ otherwise. Then, using the same notation as above, we get $\min\{\alpha, d(i)-1\}>k-2$ but $d(i)-1=2(k-1)-1$ and $\alpha+1\leq \frac{d(n)}{2}=\frac{k+1}{2}$ so $$\min\{\alpha, d(i)-1\}=\alpha\leq \frac{k-1}{2}$$. However, $\frac{k-1}{2}\leq k-2$ for all $k\geq 3$, so this case too leads to a contradiction. Thus, we have exhausted all possible choices of $n$, so indeed $f(n)=q^{d(n)-1}$, and we are done by strong induction.