Maths Olympiad Prep

Library / /6 of 6

Number theory Difficulty 7.7 National olympiad, round 2 Find the answer

Find all functions f:NNf : \mathbb{N} \rightarrow \mathbb{N} such that the following conditions are true for every pair of positive integers (x,y)(x, y):
(i)(i): xx and f(x)f(x) have the same number of positive divisors.
(ii)(ii): If xyx \nmid y and yxy \nmid x, then:
gcd(f(x),f(y))>f(gcd(x,y))\gcd(f(x), f(y)) > f(\gcd(x, y))

A number or a short expression. Spacing and $ signs are ignored.

Solution

Given the problem, we aim to find all functions f:NN f : \mathbb{N} \rightarrow \mathbb{N} satisfying the following conditions for every pair of positive integers (x,y)(x, y):

1. x x and f(x) f(x) have the same number of positive divisors.
2. If xy x \nmid y and yx y \nmid x , then:
gcd(f(x),f(y))>f(gcd(x,y)) \gcd(f(x), f(y)) > f(\gcd(x, y))

Let's denote d(x) d(x) as the number of positive divisors of x x .

### Analysis

#### Condition (i): Number of Positive Divisors

The first condition implies that d(x)=d(f(x)) d(x) = d(f(x)) . This suggests that f(x) f(x) must be related to the structure of x x in a way that the number of divisors remains the same.

#### Condition (ii): GCD Condition

For distinct positive integers x x and y y , if xy x \nmid y and yx y \nmid x , then the greatest common divisor condition
gcd(f(x),f(y))>f(gcd(x,y)) \gcd(f(x), f(y)) > f(\gcd(x, y))
suggests that f f preserves some multiplicative properties, ensuring that f f does not assign smaller values or inappropriate divisibility relationships.

### Solution

Since f(x) f(x) and x x share the same number of divisors, a natural choice is to let:

f(x)=qd(x)1 f(x) = q^{d(x)-1}

where q q is a fixed prime number. This function f(x)=qd(x)1 f(x) = q^{d(x)-1} has the following properties:
- The number of divisors of qd(x)1 q^{d(x)-1} is d(x) d(x) , aligning with condition (i).
- This choice maintains the strict manipulation of the number of divisors, ensuring multiplicative relationships hold, satisfying condition (ii) when q q is a fixed prime.

Therefore, the solution to the problem, where every condition is met, is:

f(x)=qd(x)1 \boxed{f(x) = q^{d(x)-1}}

This conclusion follows from the necessity to find a function that inherently matches the divisor count while satisfying the inequality requirements imposed by the gcd condition.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.