Olympiad Maths Prep

Library / /3 of 4

Number theory Difficulty 6.2 National olympiad Prove it Bulgaria

Find all positive integers kk, so that there exists a polynomial f(x)f(x) with rational coefficients, such that for all sufficiently large nn,
f(n)=lcm(n+1,n+2,,n+k). f(n) = \operatorname{lcm}(n + 1, n + 2, \dots, n + k).

Solution

For k=1k=1 and k=2k=2, the required polynomials are f(x)=x+1f(x) = x+1 and f(x)=(x+1)(x+2)f(x) = (x+1)(x+2), respectively. Let k3k \ge 3 and assume that such a polynomial f(x)f(x) exists. For any prime number pp, its degree in lcm(n+1,n+2,,n+k)\operatorname{lcm}(n+1, n+2, \dots, n+k) is max{α1,α2,,αk1}\max\{\alpha_1, \alpha_2, \dots, \alpha_{k-1}\}, where αi\alpha_i is the power of pp in the canonical representation of n+in+i, i=1,,ki=1, \dots, k. If this is, for example, αs\alpha_s, then it would be obtained if we take
(n+1)(n+2)(n+k)pα1pα2pαs1pαs+1pαk, \frac{(n+1)(n+2)\cdots(n+k)}{p^{\alpha_1}p^{\alpha_2}\cdots p^{\alpha_{s-1}}p^{\alpha_{s+1}}\cdots p^{\alpha_k}},
it being clear that the powers of pp in the denominator are divisors of 1isk(si)\prod_{1 \le i \ne s \le k} (s - i). Therefore
lcm(n+1,n+2,,n+k)=(n+1)(n+2)(n+k)Cn,(1) \operatorname{lcm}(n+1, n+2, \dots, n+k) = \frac{(n+1)(n+2)\dots(n+k)}{C_n}, \quad (1)
where CnC_n is a divisor of 1i<jk(ji)\prod_{1 \le i < j \le k} (j - i). Since CnC_n can take a finite number of possible values, there will be a natural number CC such that for infinitely many nn, f(n)=(n+1)(n+2)(n+k)Cf(n) = \frac{(n+1)(n+2)\dots(n+k)}{C}. So for infinitely many xx, f(x)=(x+1)(x+2)(x+k)Cf(x) = \frac{(x+1)(x+2)\dots(x+k)}{C}, whence
f(x)=(x+1)(x+2)(x+k)C,xR. f(x) = \frac{(x+1)(x+2)\dots(x+k)}{C}, \quad \forall x \in \mathbb{R}.
Therefore
lcm(n+1,n+2,,n+k)=(n+1)(n+2)(n+k)C,for all nN. \operatorname{lcm}(n+1, n+2, \dots, n+k) = \frac{(n+1)(n+2)\dots(n+k)}{C}, \quad \text{for all } n \in \mathbb{N}.
Let's assume this is possible. Let's choose a prime p<kp < k such that pp does not divide kk. Let n+k+1=pmn + k + 1 = p^m for sufficiently large mm. From the above formula we have
lcm(n+2,n+3,,n+k+1)lcm(n+1,n+2,,n+k)=n+k+1n+1.(2) \frac{\operatorname{lcm}(n+2, n+3, \dots, n+k+1)}{\operatorname{lcm}(n+1, n+2, \dots, n+k)} = \frac{n+k+1}{n+1}. \quad (2)
The degree of pp in the numerator of the left side is mm and in the denominator – at least 1, while the degree of pp in the numerator of the right side is mm and in the denominator – 0. We derive a contradiction! Therefore, the assumption is wrong and for k3k \ge 3 there does not exist a polynomial with the desired property. \square

Looking for a route rather than 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.