Maths Olympiad Prep

Library / China Southeastern Mathematical Olympiad /36 of 39

China Southeastern Mathematical Olympiad

Number theory Difficulty 7.3 National Olympiad, round 2 Prove it China

Let nn be an integer greater than 11. Denote the first nn primes in increasing order by p1,p2,…,pnp_1, p_2, \dots, p_n (i.e., p1=2,p2=3,…p_1 = 2, p_2 = 3, \dots). Let A=p1p1p2p2⋯pnpnA = p_1^{p_1} p_2^{p_2} \cdots p_n^{p_n}. Find all positive integers xx such that Ax\frac{A}{x} is even and has exactly xx distinct positive divisors.

Solution

By 2x∣A2x \mid A, note that A=4⋅p2p2⋯pnpnA = 4 \cdot p_2^{p_2} \cdots p_n^{p_n}. We may suppose that x=2α1p2α2⋯pnαnx = 2^{\alpha_1} p_2^{\alpha_2} \cdots p_n^{\alpha_n}, where 0≤α1≤10 \le \alpha_1 \le 1, 0≤αi≤pi0 \le \alpha_i \le p_i (i=2,3,…,ni = 2, 3, \dots, n). Then, we have
Ax=22−α1p2p2−α2⋯pnpn−αn. \frac{A}{x} = 2^{2-\alpha_1} p_2^{p_2-\alpha_2} \cdots p_n^{p_n-\alpha_n}.
Hence, the number of different divisors of Ax\frac{A}{x} is
(3−α1)(p2−α2+1)⋯(pn−αn+1). (3 - \alpha_1)(p_2 - \alpha_2 + 1)\cdots(p_n - \alpha_n + 1).
We know that
(3−α1)(p2−α2+1)⋯(pn−αn+1)=x=2α1p2α2⋯pnαn.1◯ (3 - \alpha_1)(p_2 - \alpha_2 + 1)\cdots(p_n - \alpha_n + 1) = x = 2^{\alpha_1} p_2^{\alpha_2} \cdots p_n^{\alpha_n}. \qquad \textcircled{1}
By induction on nn, we shall prove that the array (α1,α2,…,αn)(\alpha_1, \alpha_2, \dots, \alpha_n) satisfying 1◯\textcircled{1} is (1,1,…,1)(1, 1, \dots, 1) (n≥2n \ge 2).

(1) If n=2n=2, then 1◯\textcircled{1} becomes (3−α1)(4−α2)=2α13α2(3 - \alpha_1)(4 - \alpha_2) = 2^{\alpha_1} 3^{\alpha_2}, where α1∈{0,1}\alpha_1 \in \{0, 1\}. If α1=0\alpha_1 = 0, then 3(4−α2)=3α23(4 - \alpha_2) = 3^{\alpha_2} which has no integer solution α2\alpha_2. If α1=1\alpha_1 = 1, then 2(4−α2)=2⋅3α22(4 - \alpha_2) = 2 \cdot 3^{\alpha_2}. We have α2=1\alpha_2 = 1. Thus, (α1,α2)=(1,1)(\alpha_1, \alpha_2) = (1, 1). That is, the conclusion is true for n=2n=2.

(2) Suppose that the conclusion is true for n=k−1n = k - 1 (k≥3k \ge 3), then when n=kn = k, 1◯\textcircled{1} becomes
(3−α1)(p2−α2+1)⋯(pk−1−αk−1+1)(pk−αk+1)2◯=2α1p2α2⋯pk−1αk−1pkαk. (3 - \alpha_1)(p_2 - \alpha_2 + 1)\cdots(p_{k-1} - \alpha_{k-1} + 1)(p_k - \alpha_k + 1) \qquad \textcircled{2} \\ = 2^{\alpha_1} p_2^{\alpha_2} \cdots p_{k-1}^{\alpha_{k-1}} p_k^{\alpha_k}.
If αk≥2\alpha_k \ge 2, considering
0<pk−αk+1<pk, 0 < p_k - \alpha_k + 1 < p_k,
0<pi−αi+1≤pi+1<pk(1≤i≤k−1), 0 < p_i - \alpha_i + 1 \le p_i + 1 < p_k \quad (1 \le i \le k - 1),
we see that the left-hand side of 2◯\textcircled{2} cannot be divided by pkp_k, but the right-hand side of 2◯\textcircled{2} is a multiple of pkp_k, which is a contradiction.

If αk=0\alpha_k = 0, then 2◯\textcircled{2} becomes
(3−α1)(p2−α2+1)⋯(pk−1−αk−1+1)(pk+1)3◯=2α1p2α2⋯pkαk. (3 - \alpha_1)(p_2 - \alpha_2 + 1)\cdots(p_{k-1} - \alpha_{k-1} + 1)(p_k + 1) \quad \textcircled{3} \\ = 2^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}.
Note that p2,p3,…,pkp_2, p_3, \dots, p_k are odd primes, thus, on the one hand, pk+1p_k + 1 is even. So the left-hand side of 3◯\textcircled{3} is even. On the other hand, the right side of 3◯\textcircled{3} is odd. So α1=1\alpha_1 = 1. But then 3−α1=23 - \alpha_1 = 2, so the left-hand side of 3◯\textcircled{3} is a multiple of 44, but the right-hand side of 3◯\textcircled{3} is not, which is a contradiction.

By the above argument, we must have αk=1\alpha_k = 1, and in 2◯\textcircled{2},
pk−αk+1=pkαk=pk. p_k - \alpha_k + 1 = p_k^{\alpha_k} = p_k.
Thus,
(3−α1)(p2−α2+1)⋯(pk−1−αk−1+1)=2α1p2α2⋯pk−1αk−1. (3 - \alpha_1)(p_2 - \alpha_2 + 1)\cdots(p_{k-1} - \alpha_{k-1} + 1) = 2^{\alpha_1} p_2^{\alpha_2} \cdots p_{k-1}^{\alpha_{k-1}}.
By the induction hypotheses, α1=α2=⋯=αk−1=1\alpha_1 = \alpha_2 = \cdots = \alpha_{k-1} = 1.
Thus, α1=α2=⋯=αk−1=αk=1\alpha_1 = \alpha_2 = \cdots = \alpha_{k-1} = \alpha_k = 1, that is, the conclusion is true for n=kn = k.

By (1) and (2), we conclude that (α1,α2,…,αn)=(1,1,…,1)(\alpha_1, \alpha_2, \dots, \alpha_n) = (1, 1, \dots, 1), so the integer required is x=2p2⋯pn=p1p2⋯pnx = 2p_2 \cdots p_n = p_1 p_2 \cdots p_n.

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.