Maths Olympiad Prep

Library / /177 of 299

Algebra Difficulty 6.7 National Olympiad Prove it Iran

We call a polynomial xn1+xn2++xn1398+1x^{n_1} + x^{n_2} + \dots + x^{n_{1398}} + 1 special if n1,n2,,n1398n_1, n_2, \dots, n_{1398} are distinct positive integers. Do there exist an infinite set of polynomials with real coefficients such that the product of each two of them is special?

Solution

We first prove the following lemma.

Lemma. Let f(x)f(x) be a polynomial with complex coefficients such that its leading coefficient is rational. If for some positive integer kk we have f(x)kZ[X]f(x)^k \in \mathbb{Z}[X], then the polynomial f(x)f(x) would also be in Z[X]\mathbb{Z}[X].

Proof. Assume f(x)=anxn++a0f(x) = a_n x^n + \cdots + a_0. Then we can write f(x)k=bkxkn++b1x+b0f(x)^k = b_k x^{kn} + \cdots + b_1 x + b_0. Now, assume inductively that an,an1,,ansa_n, a_{n-1}, \ldots, a_{n-s} are rational then we must prove ans1a_{n-s-1} is rational. For proving this, we compare the coefficient of xkns1x^{kn-s-1} in the both sides. Then we can say that bkns1=ans1ank1+Sb_{kn-s-1} = a_{n-s-1}a_n^{k-1} + S where SS is a rational number. We conclude that ans1a_{n-s-1} is also a rational number. That is, f(x)f(x) must have rational coefficients.

Now we want to prove that f(x)f(x) has integer coefficients. If for some kk we have f(x)k=f(x)k1f(x)Z[X]f(x)^k = f(x)^{k-1} \cdot f(x) \in \mathbb{Z}[X], then by use of Gauss's lemma, we can say that there exists a rational number qq such that the polynomials qf(x)qf(x) and q1f(x)k1q^{-1}f(x)^{k-1} have integer coefficients. Assume q=abq = \frac{a}{b} where gcd(a,b)=1\gcd(a, b) = 1. Thus we can say that af(x)af(x) and bf(x)k1bf(x)^{k-1} have integer coefficients. Therefore, the polynomial ak1f(x)k1a^{k-1}f(x)^{k-1} has integer coefficients. We know there exist integers s,ts, t such that ak1s+bt=1a^{k-1}s + bt = 1. Thus the polynomial ak1sf(x)k1+btf(x)k1=f(x)k1a^{k-1}sf(x)^{k-1} + btf(x)^{k-1} = f(x)^{k-1} has integer coefficients. Continuing this process we can observe that f(x)f(x) has integer coefficients.

We also need the following lemma.

Lemma. Let P(x)P(x) and Q(x)Q(x) be two polynomials with rational coefficients such that Q(x)Q(x) divides P(x)P(x) then the quotient of these polynomials, i.e., R(x)=P(x)Q(x)R(x) = \frac{P(x)}{Q(x)} has rational coefficients.

Proof. It is clear based on the division algorithm of polynomials.

Back to our problem, let R(x)R(x), S(x)S(x) and T(x)T(x) be three elements of the desired set. Since R(x)S(x)R(x)S(x), R(x)T(x)R(x)T(x) and S(x)T(x)S(x)T(x) all have integer coefficients then R(x)2=R(x)S(x)R(x)T(x)S(x)T(x)R(x)^2 = \frac{R(x)S(x)R(x)T(x)}{S(x)T(x)} has also rational coefficients. Let r,sr, s and tt be the leading coefficients of R(x)R(x), S(x)S(x) and T(x)T(x), respectively. Since R(x)S(x)R(x)S(x), S(x)T(x)S(x)T(x) and R(x)T(x)R(x)T(x) are all special, it follows that rs=st=tr=1rs = st = tr = 1. Hence, r=s=t=±1r = s = t = \pm 1. Applying above lemma, we find that R(x)R(x), S(x)S(x) and T(x)T(x) have rational coefficients. Thus, R(1)R(1), S(1)S(1) and T(1)T(1) are rational numbers. Further, R(1)T(1)=R(1)S(1)=T(1)S(1)=1399R(1)T(1) = R(1)S(1) = T(1)S(1) = 1399. It follows that R(1),S(1),T(1){±1399}R(1), S(1), T(1) \in \{\pm\sqrt{1399}\}. This is impossible. So, such a set doesn't exist. ■

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 reproduced verbatim; metadata (topic, difficulty) added by this project.