Maths Olympiad Prep

Library / /11 of 16

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) 1a1<a2<<an501 \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
mbiciaifor i=1,,n. m \cdot b_i \equiv c_i^{a_i} \quad \text{for } i = 1, \dots, n.
Prove that n16n \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 iji \ne j. Put ai=uda_i = u \cdot d, aj=vda_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
mbi=ciaiandmbj=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=p1a1pkak. 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 mbim \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 n17n \ge 17 then among 2a2<a3<<an502 \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 n16n \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,p11: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 5322=605 \cdot 3 \cdot 2 \cdot 2 = 60.

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.