Maths Olympiad Prep

Library / /328 of 397

Algebra Difficulty 6.8 National Olympiad Prove it Taiwan

已知非常數的整係數多項式 f(x)f(x) 滿足
(x3+4x2+4x+3)f(x)=(x32x2+2x1)f(x+1). (x^3 + 4x^2 + 4x + 3)f(x) = (x^3 - 2x^2 + 2x - 1)f(x + 1).
證明:對所有正整數 nn (n8n \ge 8), f(n)f(n) 至少有五個不同的質因數。

Let f(x)f(x) be the polynomial with integer coefficients (f(x)f(x) is not constant) such that
(x3+4x2+4x+3)f(x)=(x32x2+2x1)f(x+1). (x^3 + 4x^2 + 4x + 3)f(x) = (x^3 - 2x^2 + 2x - 1)f(x + 1).
Prove that for each positive integer nn (n8n \ge 8), f(n)f(n) has at least five distinct prime divisors.

Solution

The given condition is equivalent to
(x+3)(x2+x+1)f(x)=(x1)(x2x+1)f(x+1).(1) (x + 3)(x^2 + x + 1)f(x) = (x - 1)(x^2 - x + 1)f(x + 1). \quad (1)
In equation (1), set
x=3,13i2,1+3i2,1 x = -3, \frac{-1 - \sqrt{3}i}{2}, \frac{-1 + \sqrt{3}i}{2}, 1
respectively, then
f(2)=f(13i2)=f(1+3i2)=f(1)=0. f(-2) = f\left(\frac{1 - \sqrt{3}i}{2}\right) = f\left(\frac{1 + \sqrt{3}i}{2}\right) = f(1) = 0.
In equation (1), set x=2,0x = -2, 0. Then f(1)=f(0)=0f(-1) = f(0) = 0. Hence 2,1,0,1-2, -1, 0, 1 and 1±3i2\frac{1 \pm \sqrt{3}i}{2} are roots of f(x)=0f(x) = 0. Then
f(x)=(x+2)(x+1)x(x1)(x2x+1)g(x),(2) f(x) = (x + 2)(x + 1)x(x - 1)(x^2 - x + 1)g(x), \quad (2)
where g(x)g(x) is a polynomial with real coefficients. From (2) we obtain
f(x+1)=(x+3)(x+2)(x+1)x(x2+x+1)g(x+1).(3) f(x + 1) = (x + 3)(x + 2)(x + 1)x(x^2 + x + 1)g(x + 1). \quad (3)
Substituting (2), (3) into (1) gives
g(x)=g(x+1). g(x) = g(x + 1).
Let g(x)=k=0nakxkg(x) = \sum_{k=0}^{n} a_k x^k. Then k=0nakxk=k=0nak(x+1)k\sum_{k=0}^{n} a_k x_k = \sum_{k=0}^{n} a_k (x+1)^k. Comparing the coefficients of the (n1)(n-1)-th degree term on both sides, we know
an1=nan+an1nan=0. a_{n-1} = n a_n + a_{n-1} \Rightarrow n a_n = 0.
Therefore, g(x)g(x) is a constant cc. Hence f(x)=c(x+2)(x+1)x(x1)(x2x+1)f(x) = c(x + 2)(x + 1)x(x - 1)(x^2 - x + 1), where the constant cc is a nonzero integer.

First we prove: (n+2)(n+1)n(n1)(n + 2)(n + 1)n(n - 1) (n8n \ge 8) has at least four distinct prime divisors.
Otherwise, (n+2)(n+1)n(n1)(n+2)(n+1)n(n-1) has at most three distinct prime divisors 2,3,p2, 3, p (p2,3p \ne 2, 3). But since the greatest common divisors between (n1),n,(n+1),(n+2)(n-1), n, (n+1), (n+2) pairwise are 1,2,31, 2, 3, among the two odd numbers, which are coprime to each other, one is 3a3^a and the other is pbp^b, where a,ba,b are positive integers. Consequently, the two even numbers are 2c+1,2×3d2^{c+1}, 2 \times 3^d, where c,dc,d are positive integers. Hence 2c3d=1|2^c - 3^d| = 1. Solving this gives (c,d)=(2,1),(3,2)(c,d) = (2,1), (3,2).
Therefore, these two even numbers are 8, 6 or 16, 18. The former does not fit. The latter gives the other two odd numbers as 15, 17 or 17, 19, both of which lead to a contradiction.

Next, suppose there exists some positive integer nn (n8n \ge 8) such that every prime divisor of n2n+1n^2 - n + 1 is also a prime divisor of
(n+2)(n+1)n(n1), (n+2)(n+1)n(n-1),
and (n+2)(n+1)n(n1)(n+2)(n+1)n(n-1) has exactly four prime divisors; otherwise, the conclusion holds.
Clearly, (n2n+1,n(n+1))=1(n^2 - n + 1, n(n+1)) = 1. From n2n+1=(n+2)(n3)+7n^2 - n + 1 = (n+2)(n-3) + 7, we know
(n2n+1,n+1)=1 or 3,(n2n+1,n+2)=1 or 7. (n^2 - n + 1, n + 1) = 1 \text{ or } 3, \quad (n^2 - n + 1, n + 2) = 1 \text{ or } 7.
Hence n2n+1=3a7bn^2 - n + 1 = 3^a 7^b, where a,ba,b are 0 or positive integers. But 9(n2n+1)9 \nmid (n^2 - n + 1), so a{0,1}a \in \{0,1\}, and then b>0b > 0. By assumption, the prime divisors of n+2,n+1,n,n1n+2, n+1, n, n-1 are 2,3,7,p2, 3, 7, p (p2,3,7p \ne 2, 3, 7), so 7(n+2)7|(n+2).

Consider the sets of prime divisors A,BA, B of the two even numbers and the two odd numbers respectively among these. Clearly, 2A2 \in A, B2|B| \ge 2, AB{3}A \cap B \subseteq \{3\}. So A=2|A| = 2 or A=3|A| = 3 with 3A3 \in A.
If A={2,3}A = \{2,3\} or {2,7}\{2,7\}, then the two even numbers are 2c+1,2×3d2^{c+1}, 2 \times 3^d or 2c+1,2×7d2^{c+1}, 2 \times 7^d, giving
2c3d=1 or 2c7d=1. |2^c - 3^d| = 1 \text{ or } |2^c - 7^d| = 1.
Hence these two even numbers are 16, 18 or 16, 14. The former gives 7(n+2)7 \nmid (n+2); the latter makes (n+2)(n+1)n(n1)(n+2)(n+1)n(n-1) have prime divisors 2,3,5,72, 3, 5, 7 and 1313 (or 1717), a contradiction.

If A={2,p}A = \{2,p\}, then n+2n+2 is odd, and n1n-1 is even.
From 3A3(n1)3(n2). \text{From } 3 \notin A \Rightarrow 3 \nmid (n-1) \Rightarrow 3 \nmid (n-2).
Hence n+2=7c,n=3dn+2 = 7^c, n = 3^d, and 2e{n+1,n1}2^e \in \{n+1, n-1\} (c,d,ec,d,e are 0 or positive integers, c,d2,e3c,d \ge 2, e \ge 3).
Consequently, 3d2e=1(d,e)=(2,3)|3^d - 2^e| = 1 \Rightarrow (d,e) = (2,3). Then n=9n=9. Then n+2=117cn+2 = 11 \ne 7^c, a contradiction.

If A={2,3,7}A = \{2,3,7\}, then B={3,p}B = \{3,p\}, and n+2n+2 is even, (n+2,n1)=3(n+2, n-1) = 3. Hence 2×3×7(n+2)2 \times 3 \times 7|(n+2).
Consequently, n=2c,n1=3d,n+1=pen = 2^c, n-1 = 3^d, n+1 = p^e (c,d,ec,d,e are positive integers, c3,d2c \ge 3, d \ge 2).
Then 2c3d=1(c,d)=(2,1)2^c - 3^d = 1 \Rightarrow (c,d) = (2,1), a contradiction.

If A={2,3,p}A = \{2,3,p\}, then B={3,7}B=\{3,7\}, and n+2n+2 is odd, (n+2,n1)=3(n+2, n-1) = 3. Hence 3×7(n+2)3 \times 7|(n+2). But (n,n+2)=1(n, n+2) = 1, so the odd prime divisors of nn are not 3,73,7, a contradiction.

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.