EGMO 2024 | Problem 5 | Solution - 14 April 2024

Problem 5. Let N denote the set of positive integers. Find all functions f : N → N such that the following conditions are true for every pair of positive integers ( x, y ):
(i) x and f ( x ) have the same number of positive divisors.
(ii) If x does not divide y and y does not divide x , then

gcd( f ( x ) , f ( y )) > f (gcd( x, y )) .

Here gcd( m, n ) is the largest positive integer that divides both m and n .

Solution 1

he 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.

Solution 2

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.

Solution 3

he 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 $\lfloor{\frac{d(n)}{x}\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)$ . $\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 $\lfloor{\frac{2k}{k+1}\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)>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
$\lfloor{\left(\frac{2\prod_{i=1}^k (n_i+1)}{\prod_{i=1}^k (n_i+1)+1}\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)>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
$\lfloor{\left(\frac{(l+2)\prod_{i=1}^k (n_i+1)}{(l+1)\prod_{i=1}^k (n_i+1)+1}\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 our hypotheses.

By citing the fundamental theorem of arithmetic, we are done.