Maths Olympiad Prep

Library / /53 of 520

Number theory Difficulty 6.4 National olympiad Find the answer

Determine all finite nonempty sets SS of positive integers satisfying
i+j(i,j)\mboxisanelementofSforalli,jinS, {i+j\over (i,j)}\qquad\mbox{is an element of S for all i,j in S},
where (i,j)(i,j) is the greatest common divisor of ii and jj.

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

Solution

1. Understanding the Problem:
We need to determine all finite nonempty sets S S of positive integers such that for any i,jS i, j \in S , the expression i+j(i,j)\frac{i+j}{(i,j)} is also an element of S S . Here, (i,j)(i,j) denotes the greatest common divisor (gcd) of i i and j j .

2. Initial Observations:
- If i=j i = j , then i+i(i,i)=2ii=2\frac{i+i}{(i,i)} = \frac{2i}{i} = 2, which implies that 2S 2 \in S if S S contains any repeated element.
- If ij i \neq j , then i+j(i,j)\frac{i+j}{(i,j)} must be an integer and an element of S S .

3. Lemma 1:
- Define f(i,j)=i+j(i,j) f(i,j) = \frac{i+j}{(i,j)} .
- We need to check if f(i,j) f(i,j) is involutive, i.e., if f(i,j)=i f(i,j) = i or f(i,j)=j f(i,j) = j .

4. Case Analysis:
- **Case 1: gcd(i,j)=1 \gcd(i,j) = 1 :**
- Here, f(i,j)=i+j f(i,j) = i + j .
- Since i i and j j are distinct, i+j i + j is greater than both i i and j j . This implies that S S must contain larger elements, leading to an infinite set, which contradicts the finiteness of S S .

- **Case 2: gcd(i,j)=k>1 \gcd(i,j) = k > 1 :**
- Let i=ki i = k \cdot i' and j=kj j = k \cdot j' where gcd(i,j)=1 \gcd(i', j') = 1 .
- Then, f(i,j)=k(i+j)k=i+j f(i,j) = \frac{k(i' + j')}{k} = i' + j' .
- Since i i' and j j' are coprime, i+j i' + j' must be an element of S S .

5. Finite Set Construction:
- Consider S={n} S = \{ n \} for any positive integer n n . This trivially satisfies the condition since there are no distinct pairs i,j i, j to consider.
- Consider S={n,n(n1)} S = \{ n, n(n-1) \} for n>2 n > 2 :
- For i=n i = n and j=n(n1) j = n(n-1) , we have gcd(n,n(n1))=n \gcd(n, n(n-1)) = n .
- Then, f(n,n(n1))=n+n(n1)n=n2n=n f(n, n(n-1)) = \frac{n + n(n-1)}{n} = \frac{n^2}{n} = n .
- This implies nS n \in S , which is already true.

6. Verification:
- For S={n} S = \{ n \} , the condition is trivially satisfied.
- For S={n,n(n1)} S = \{ n, n(n-1) \} , the condition is satisfied as shown above.

7. Conclusion:
- The only finite nonempty sets S S that satisfy the given condition are of the form S={n} S = \{ n \} and S={n,n(n1)} S = \{ n, n(n-1) \} for n>2 n > 2 .

The final answer is S={n} \boxed{ S = \{ n \} } or S={n,n(n1)} S = \{ n, n(n-1) \} for n>2 n > 2 .

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.