Maths Olympiad Prep

Library / /56 of 397

Number theory Difficulty 5.0 AIME, harder Prove it Taiwan

Consider a polynomial P(x)=(x+d1)(x+d2)(x+d9)P(x) = (x + d_1)(x + d_2) \cdots (x + d_9), where d1,d2,,d9d_1, d_2, \cdots, d_9 are 9 distinct positive integers. Prove that there exists a positive integer NN such that for all integers xNx \ge N, P(x)P(x) can be divided by a prime greater than 20.

Solution

First observe that for each index i{1,2,,9}i \in \{1, 2, \cdots, 9\},
Di=1j9, jididj D_i = \prod_{1 \le j \le 9,\ j \ne i} |d_i - d_j|
is a positive number. Let N=max{D1d1,D2d2,,D9d9}N = \max\{D_1 - d_1, D_2 - d_2, \cdots, D_9 - d_9\}. We will show below that NN satisfies the requirement of the problem.

Suppose there exists an integer xNx \ge N such that all prime factors of P(x)P(x) are less than 20. For all 1i91 \le i \le 9, consider the reduced fraction of (x+di)/Di(x+d_i)/D_i, denoted as Ai/BiA_i/B_i. Note that AiP(x)A_i|P(x), and since x+di(Didi+1)di>Dix+d_i \ge (D_i-d_i+1)-d_i > D_i, Ai>1A_i > 1, so there must exist a prime pip_i less than 20 such that piAip_i|A_i. Moreover, since there are only 8 primes less than 20, by the pigeonhole principle there exist 1i<j91 \le i < j \le 9 such that pi=pj=pp_i = p_j = p. Hence there exist positive integers αi,αj\alpha_i, \alpha_j, and positive integers qi,qjq_i, q_j coprime to pp, such that x+di=pαiqix+d_i = p^{\alpha_i}q_i and x+dj=pαjqjx+d_j = p^{\alpha_j}q_j. Without loss of generality, assume αi<αj\alpha_i < \alpha_j.

But at the same time, note that pαiAix+dip^{\alpha_i}|A_i|x+d_i and pαipαjAjx+djp^{\alpha_i}|p^{\alpha_j}|A_j|x+d_j, so pαididjDip^{\alpha_i}|d_i-d_j|D_i, hence
pAix+diDipαiqipiαi=qi, p|A_i \frac{x+d_i}{D_i} \frac{p^{\alpha_i}q_i}{p_i^{\alpha_i}} = q_i,
but qiq_i is coprime to pp, a contradiction! Therefore NN satisfies the requirement of the problem.

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 translated into English from zh; metadata (topic, difficulty) added by this project.