Maths Olympiad Prep

Library / /4 of 4

Number theory Difficulty 6.6 National olympiad Find the answer

Let N1\mathbb{N}_{\geqslant 1} be the set of positive integers.
Find all functions f ⁣:N1N1f \colon \mathbb{N}_{\geqslant 1} \to \mathbb{N}_{\geqslant 1} such that, for all positive integers mm and nn:
GCD(f(m),n)+LCM(m,f(n))=GCD(m,f(n))+LCM(f(m),n).\mathrm{GCD}\left(f(m),n\right) + \mathrm{LCM}\left(m,f(n)\right) = \mathrm{GCD}\left(m,f(n)\right) + \mathrm{LCM}\left(f(m),n\right).

Note: if aa and bb are positive integers, GCD(a,b)\mathrm{GCD}(a,b) is the largest positive integer that divides both aa and bb, and LCM(a,b)\mathrm{LCM}(a,b) is the smallest positive integer that is a multiple of both aa and bb.

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

Solution

Given the problem, we seek all functions f:N1N1 f: \mathbb{N}_{\geq 1} \to \mathbb{N}_{\geq 1} such that for all positive integers m m and n n , the following holds:

GCD(f(m),n)+LCM(m,f(n))=GCD(m,f(n))+LCM(f(m),n). \mathrm{GCD}(f(m), n) + \mathrm{LCM}(m, f(n)) = \mathrm{GCD}(m, f(n)) + \mathrm{LCM}(f(m), n).

To solve this, let's explore the properties of f f .

### Step 1: Simplification and Substitution

Start by testing for simple values. Let m=n=1 m = n = 1 :

GCD(f(1),1)+LCM(1,f(1))=GCD(1,f(1))+LCM(f(1),1). \mathrm{GCD}(f(1), 1) + \mathrm{LCM}(1, f(1)) = \mathrm{GCD}(1, f(1)) + \mathrm{LCM}(f(1), 1).

Since GCD(a,1)=1\mathrm{GCD}(a,1) = 1 and LCM(1,a)=a\mathrm{LCM}(1, a) = a, the equation simplifies to:

1+f(1)=1+f(1). 1 + f(1) = 1 + f(1).

This holds trivially for any f(1) f(1) .

### Step 2: Consider m=n m = n

Next, consider m=n m = n :

GCD(f(m),m)+LCM(m,f(m))=GCD(m,f(m))+LCM(f(m),m). \mathrm{GCD}(f(m), m) + \mathrm{LCM}(m, f(m)) = \mathrm{GCD}(m, f(m)) + \mathrm{LCM}(f(m), m).

This equation is trivially true since it mirrors both sides of the equation exactly.

### Step 3: General Case Examination

Now, reconsider the original condition:

GCD(f(m),n)+mf(n)GCD(m,f(n))=GCD(m,f(n))+f(m)nGCD(f(m),n). \mathrm{GCD}(f(m), n) + \frac{m \cdot f(n)}{\mathrm{GCD}(m, f(n))} = \mathrm{GCD}(m, f(n)) + \frac{f(m) \cdot n}{\mathrm{GCD}(f(m), n)}.

Assume f(n)=n f(n) = n for each n n :
- Then, each side simplifies symmetrically:
GCD(n,n)+LCM(m,n)=GCD(m,n)+LCM(n,n). \mathrm{GCD}(n, n) + \mathrm{LCM}(m, n) = \mathrm{GCD}(m, n) + \mathrm{LCM}(n, n).
- This becomes:
n+mnGCD(m,n)=GCD(m,n)+n. n + \frac{m \cdot n}{\mathrm{GCD}(m, n)} = \mathrm{GCD}(m, n) + n.
- Both sides are equal, confirming f(n)=n f(n) = n is a solution.

### Step 4: Consider if Other Solutions Exist

Let’s consider if there can be other forms. The original condition:
- Ensures symmetry requiring function values GCD(f(m),n) \mathrm{GCD}(f(m), n) and f(n) f(n) to align with structural equivalence.
- Due to properties of GCD\mathrm{GCD} and LCM\mathrm{LCM}, assuming f(n)=n f(n) = n ensures equal, canonical decomposition on both sides.

### Conclusion:

Given the symmetry and simplifications made under functional substitutions, the solution function is:

f(n)=n f(n) = n

for all positive integers n n .

Thus, the solution is: f(n)=n\boxed{f(n) = n}.

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.