Maths Olympiad Prep

Track / Stage 6 / 166 of 400 #1806 of 2604

Problem 1806

National Olympiad, first round
Number theory Difficulty 6.2 Prove it Autumn Tournament · 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).

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official 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 k≥3k \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,…,αk−1}\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α2⋯pαs−1pαs+1⋯pα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 ∏1≤i≠s≤k(s−i)\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 ∏1≤i<j≤k(j−i)\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,∀x∈R. 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 n∈N. \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 k≥3k \ge 3 there does not exist a polynomial with the desired property. □\square

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.