Maths Olympiad Prep

Library / Cesko-Slovacko-Poljsko /11 of 16

Cesko-Slovacko-Poljsko

Number theory Difficulty 6.9 National Olympiad Prove it Czech-Polish-Slovak Mathematical Match

The nn-tuple of positive integers a1,…,ana_1, \dots, a_n satisfies the following conditions:
(i) 1≤a1<a2<⋯<an≤501 \le a_1 < a_2 < \dots < a_n \le 50;
(ii) for any nn-tuple of positive integers b1,…,bnb_1, \dots, b_n, there exist a positive integer mm and an nn-tuple of positive integers c1,…,cnc_1, \dots, c_n such that
m⋅bi≡ciaifor i=1,…,n. m \cdot b_i \equiv c_i^{a_i} \quad \text{for } i = 1, \dots, n.
Prove that n≤16n \le 16 and find the number of different nn-tuples a1,…,ana_1, \dots, a_n satisfying the given conditions for n=16n = 16.

Solution

First we prove the numbers a1,…,ana_1, \dots, a_n are mutually relatively prime. If this is not true, we have (ai,aj)=d>1(a_i, a_j) = d > 1 for some i≠ji \ne j. Put ai=u⋅da_i = u \cdot d, aj=v⋅da_j = v \cdot d. Set bi=1b_i = 1, bj=2b_j = 2. By (ii), there exist mm, cic_i, and cjc_j such that
m⋅bi=ciaiandm⋅bj=cjaj,thereforem=(ciai)dand2m=(cjvj)d. m \cdot b_i = c_i^{a_i} \quad \text{and} \quad m \cdot b_j = c_j^{a_j}, \quad \text{therefore} \quad m = (c_i^{a_i})^d \quad \text{and} \quad 2m = (c_j^{v_j})^d.
So 2(ciai)d=(cjvj)d2(c_i^{a_i})^d = (c_j^{v_j})^d, which is not possible, since the exponent of 22 in the prime factorization of the right hand side is and the one of the left hand side is not a multiple of dd.

Assume that a1,…,ana_1, \dots, a_n are mutually relatively prime. We shall prove that the condition (ii) is fulfilled. Let b1,…,bnb_1, \dots, b_n be any nn-tuple of positive integers and p1,…,pkp_1, \dots, p_k be all the prime divisors of b1,…,bnb_1, \dots, b_n. We look for aia_i in the form
m=p1a1⋯pkak. m = p_1^{a_1} \cdots p_k^{a_k}.
For i=1,…,ni = 1, \dots, n, denote by βi,j\beta_{i,j} the exponent of pjp_j in the prime factorization of bib_i. In order for m⋅bim \cdot b_i to be an aia_i-th power, it suffices αj+βi,j\alpha_j + \beta_{i,j} to be a multiple of aia_i for j=1,…,kj = 1, \dots, k. So we need αj\alpha_j fulfilling the congruences
αj≡−β1,j(moda1),αj≡−β2,j(moda2),…αj≡−βn,j(modan). \alpha_j \equiv -\beta_{1,j} \pmod{a_1}, \quad \alpha_j \equiv -\beta_{2,j} \pmod{a_2}, \quad \dots \quad \alpha_j \equiv -\beta_{n,j} \pmod{a_n}.
The existence of such αj\alpha_j is guaranteed by Chinese Remainder Theorem (as a1,…,ana_1, \dots, a_n being mutually relatively prime).

We have proved the condition (ii) is satisfied if and only if the numbers a1,…,ana_1, \dots, a_n are mutually relatively prime. Among 1,2,…,501, 2, \dots, 50, there are exactly 1515 primes. If n≥17n \ge 17 then among 2≤a2<a3<⋯<an≤502 \le a_2 < a_3 < \dots < a_n \le 50, there must be at least two numbers sharing the same prime number in their prime factorizations, hence not being relatively prime. Therefore we have n≤16n \le 16.

If n=16n = 16, then a1=1a_1 = 1 and a2,a3,…,a16a_2, a_3, \dots, a_{16} must be the powers of different primes. We list the powers of primes which can be used:
p=2:2,4,8,16,32,p=3:3,9,27,p=5:5,25,p=7:7,49,p≥11:only p. \begin{array}{lclcl} p & = & 2: & 2, 4, 8, 16, 32, \\ p & = & 3: & 3, 9, 27, \\ p & = & 5: & 5, 25, \\ p & = & 7: & 7, 49, \\ p & \ge & 11: & \text{only } p. \end{array}
Then the total number of the corresponding 1616-tuples is 5⋅3⋅2⋅2=605 \cdot 3 \cdot 2 \cdot 2 = 60.

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.