Maths Olympiad Prep

Library / /285 of 520

Number theory Difficulty 7.0 National olympiad Find the answer

For each positive integer xx, let φ(x)\varphi(x) be the number of integers 1kx1 \leq k \leq x that do not have prime factors in common with xx. Determine all positive integers nn such that there are distinct positive integers a1,a2,,ana_1,a_2, \ldots, a_n so that the set: S={a1,a2,,an,φ(a1),φ(a2),,φ(an)}S = \{a_1, a_2, \ldots, a_n, \varphi(a_1), \varphi(a_2), \ldots, \varphi(a_n)\} Have exactly 2n2n consecutive integers (in some order).

Solution

1. **Understanding the Euler's Totient Function φ(x)\varphi(x)**:
The Euler's Totient Function φ(x)\varphi(x) counts the number of integers from 11 to xx that are coprime with xx. For a prime number pp, φ(p)=p1\varphi(p) = p - 1 because all numbers less than pp are coprime with pp.

2. Initial Observations:
- If 11 is among the aia_i, then φ(1)=1\varphi(1) = 1, which would mean SS contains duplicate elements, violating the distinctness condition.
- If 22 is among the aia_i, then φ(2)=1\varphi(2) = 1 must be in SS. Since φ(3)=2\varphi(3) = 2, 33 cannot be among the aia_i because there are no aa with φ(a)=3\varphi(a) = 3. Thus, the only set SS with 22 is {1,2}\{1, 2\}.

3. **Considering ai>2a_i > 2**:
- For a>2a > 2, φ(a)\varphi(a) is even. Therefore, φ(a1),φ(a2),,φ(an)\varphi(a_1), \varphi(a_2), \ldots, \varphi(a_n) must all be even.
- This implies a1,a2,,ana_1, a_2, \ldots, a_n are all odd because the integers in SS are consecutive.

4. Smallest Element Analysis:
- Let aa be the smallest of a1,a2,,ana_1, a_2, \ldots, a_n. Then φ(a)1\varphi(a) - 1 cannot be in the set since it would be odd and therefore one of the aia_i, but φ(a)1<a\varphi(a) - 1 < a, a contradiction.
- Therefore, the smallest element of SS is φ(a)\varphi(a). We also realize that φ(a)=a1\varphi(a) = a - 1 because if there were a bab \neq a in a1,a2,,ana_1, a_2, \ldots, a_n such that φ(a)=b1\varphi(a) = b - 1, we'd need φ(b)<b\varphi(b) < b to be in SS, but the only element in SS smaller than bb is φ(a)\varphi(a), so we'd have φ(a)=φ(b)\varphi(a) = \varphi(b), which is a contradiction since SS must have 2n2n distinct elements.

5. Inductive Process:
- The two smallest elements of SS are φ(a)\varphi(a) and a=φ(a)+1a = \varphi(a) + 1, in that order.
- Repeating the same process for S{φ(a),a}S - \{\varphi(a), a\}, we find a similar conclusion.
- Proceeding inductively, it's possible to show that if a1<a2<<ana_1 < a_2 < \ldots < a_n, then the elements of SS, in increasing order, are:
φ(a1)<a1<φ(a2)<a2<<φ(an1)<an1<φ(an)<an \varphi(a_1) < a_1 < \varphi(a_2) < a_2 < \ldots < \varphi(a_{n-1}) < a_{n-1} < \varphi(a_n) < a_n

6. Consecutive Numbers and Primes:
- Because they are all consecutive numbers, it means that φ(ai)=ai1\varphi(a_i) = a_i - 1 for all 1in1 \leq i \leq n, which means that all aia_i are prime.
- Since they all form an arithmetic progression of ratio 22, the largest possible value for nn is n=3n = 3, achieved with:
φ(3)<3<φ(5)<5<φ(7)<7 \varphi(3) < 3 < \varphi(5) < 5 < \varphi(7) < 7
- This means that there are also examples for n=1n = 1 and n=2n = 2, namely, {φ(3),3}\{\varphi(3), 3\} and {φ(3),3,φ(5),5}\{\varphi(3), 3, \varphi(5), 5\}.

The final answer is n=1,2,3n = 1, 2, 3

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.