Maths Olympiad Prep

Library / /36 of 40

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=p1p1p2p2pnpnA = 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 2xA2x \mid A, note that A=4p2p2pnpnA = 4 \cdot p_2^{p_2} \cdots p_n^{p_n}. We may suppose that x=2α1p2α2pnαnx = 2^{\alpha_1} p_2^{\alpha_2} \cdots p_n^{\alpha_n}, where 0α110 \le \alpha_1 \le 1, 0αipi0 \le \alpha_i \le p_i (i=2,3,,ni = 2, 3, \dots, n). Then, we have
Ax=22α1p2p2α2pnpnα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α2pnα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) (n2n \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)=23α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=k1n = k - 1 (k3k \ge 3), then when n=kn = k, 1\textcircled{1} becomes
(3α1)(p2α2+1)(pk1αk1+1)(pkαk+1)2=2α1p2α2pk1αk1pkα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 αk2\alpha_k \ge 2, considering
0<pkαk+1<pk, 0 < p_k - \alpha_k + 1 < p_k,
0<piαi+1pi+1<pk(1ik1), 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)(pk1αk1+1)(pk+1)3=2α1p2α2pkα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)(pk1αk1+1)=2α1p2α2pk1αk1. (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==αk1=1\alpha_1 = \alpha_2 = \cdots = \alpha_{k-1} = 1.
Thus, α1=α2==αk1=α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=2p2pn=p1p2pnx = 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,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.