Maths Olympiad Prep

Library / /278 of 299

Algebra Difficulty 7.6 National Olympiad, round 2 Prove it Iran

Prove there are coprime polynomials P(x)P(x) and Q(x)Q(x) with integer coefficients and a real number u>0u > 0 such that if
ac12021udc1010,(ac)2020bdudc1010, \left| \frac{a}{c} - 1 \right|^{2021} \leq \frac{u}{d c^{1010}}, \quad \left| \left( \frac{a}{c} \right)^{2020} - \frac{b}{d} \right| \leq \frac{u}{d c^{1010}},
for some positive integers a,b,c,da, b, c, d, then we have bP(ac)=dQ(ac)bP\left(\frac{a}{c}\right) = dQ\left(\frac{a}{c}\right).

Solution

We shall prove a more general statement in the following lines.
Proposition. Let kk be a positive integer. Prove that for all pairs (c,d)(c, d) of integers such that c|c| and d|d| are prime numbers there is a positive integer NN such that the number of pairs (a,b)(a, b) of integers satisfying the following inequalities is at most NN, for all sufficiently small positive real numbers u,vu, v.
bac2021uc1011,akbckdvck1010. |b||a-c|^{2021} \le u|c|^{1011}, \quad |a^k b - c^k d| \le v|c|^{k-1010}.
Let us rewrite the original inequalities as bac12021uc1010|b|\left|\frac{a}{c} - 1\right|^{2021} \le u|c|^{-1010} and (ac)kbdvc1010\left|\left(\frac{a}{c}\right)^k b - d\right| \le v|c|^{-1010}. Then if k1010k \le 1010 then akb=ckda^k b = c^k d and hence, we only have finitely many solutions for a,ba, b. Hence, assume that k>1010k > 1010. We then prove the following lemma:
Lemma. There are polynomials P(x),Q(x)P(x), Q(x) of degree 10101010 with integer coefficients such that the polynomial P(x)xkQ(x)P(x) - x^k Q(x) has a 20212021-fold zero at x=1x = 1.
Proof. We shall prove that for all triples (m,n,k)(m, n, k) of natural numbers such that n>kn > k there are polynomials P(x)=P(m,n,k)(x)P(x) = P_{(m,n,k)}(x), Q(x)=Q(m,n,k)(x)Q(x) = Q_{(m,n,k)}(x) of degrees m,nm, n with rational coefficients such that P(x)xkQ(x)P(x) - x^k Q(x) is divisible by (x1)m+n+1(x-1)^{m+n+1}. We shall prove this through induction, considering the following expression:
x(P(m,n1,k)(x)xkQ(m,n1,k)(x))+r(P(m1,n,k)(x)xkQ(m1,n,k)(x)). x (P_{(m,n-1,k)}(x) - x^k Q_{(m,n-1,k)}(x)) + r (P_{(m-1,n,k)}(x) - x^k Q_{(m-1,n,k)}(x)).
Since both brackets are divisible by (x1)m+n(x-1)^{m+n} then there would be a rational number rr such that the above expression is divisible by (x1)m+n+1(x-1)^{m+n+1} then defining P(m,n,k)(x)=xP(m,n1,k)(x)+rP(m1,n,k)(x)P_{(m,n,k)}(x) = xP_{(m,n-1,k)}(x) + rP_{(m-1,n,k)}(x) and Q(m,n,k)(x)=xQ(m,n1,k)(x)+Q(m1,n,k)(x)Q_{(m,n,k)}(x) = xQ_{(m,n-1,k)}(x) + Q_{(m-1,n,k)}(x). Moreover, for the base case, that is when one of m,nm, n are zero, the statement is obvious. This completes our proof.

Comment 1. If P(m,n,k)(0)=0P_{(m,n,k)}(0) = 0 for some non-zero m,nm, n then the polynomial P(m,n,k)(x)xkQ(m,n,k)(x)P_{(m,n,k)}(x) - x^k Q_{(m,n,k)}(x) has at most m+nm+n non-zero coefficients, impossible.
Lemma. P(m,n,k)(x),Q(m,n,k)(x)P_{(m,n,k)}(x), Q_{(m,n,k)}(x) have no common factor.
Proof. Assume for the contradiction that there is a non constant polynomial D(x)D(x) of degree dd dividing both of them. Then at least (x1)m+n+1d(x-1)^{m+n+1-d} divides P(m,n,k)(x)D(x)xkQ(m,n,k)(x)D(x)\frac{P_{(m,n,k)}(x)}{D(x)} - x^k \frac{Q_{(m,n,k)}(x)}{D(x)}. Since the not-zero coefficient of this polynomial is at most m+n2d+2m+n-2d+2. But, according to our lemma 2 it must at least have m+n+2dm+n+2-d non-zero coefficients. Therefore, d0d \le 0. This completes our proof.

Now, there are coprime polynomials P(x),Q(x)P(x), Q(x) of degree 10101010 with integer coefficients such that P(x)xkQ(x)P(x) - x^k Q(x) is divisible by (x1)2021(x-1)^{2021} and hence there are polynomials A(x),B(x)A(x), B(x) with integer coefficients of the same degree that doesn't exceed 10101010 such that
A(x)P(x)+B(x)Q(x)=R,(1) A(x)P(x) + B(x)Q(x) = R, \quad (1)
for some non-zero constant RR.
Lemma. If a,b,ca, b, c and dd satisfy the statement of our problem then bP(ac)=dQ(ac)bP\left(\frac{a}{c}\right) = dQ\left(\frac{a}{c}\right).
Proof. We prove the lemma for polynomial P(x)xkQ(x)P(x) - x^k Q(x), for some positive integer kdegP(x)=degQ(x)=dk \ge \deg P(x) = \deg Q(x) = d. Then, the second inequality becomes akbckdvck1010|a^k b - c^k d| \le v|c|^{k-1010}. Since b1|b| \ge 1, take u<1u < 1 then acc|a-c| \le |c| therefore, a2c|a| \le 2|c|. Moreover, let d=1010d = 1010, and R(x)=P(x)xkQ(x)R(x) = P(x) - x^k Q(x), the following quantity is an integer:
cd(bP(ac)dQ(ac))=bcdR(ac)+(akbckd)cdkQ(ac). c^d \left( bP\left(\frac{a}{c}\right) - dQ\left(\frac{a}{c}\right) \right) = bc^d R\left(\frac{a}{c}\right) + (a^k b - c^k d) c^{d-k} Q\left(\frac{a}{c}\right).
Now, if bP(ac)dQ(ac)bP(\frac{a}{c}) \neq dQ(\frac{a}{c}) then, cd(bP(ac)dQ(ac))1|c^d (bP(\frac{a}{c}) - dQ(\frac{a}{c}))| \ge 1. Thus, by triangle inequality, we find that
bcdR(ac)+(akbckd)cdkQ(ac)1. |bc^d R\left(\frac{a}{c}\right)| + \left| (a^k b - c^k d) c^{d-k} Q\left(\frac{a}{c}\right) \right| \ge 1.
Write R(x)=(1x)2d+1S(x)R(x) = (1-x)^{2d+1} S(x) then, bcdR(ac)=bcd(1ac)2d+1S(ac)=cd1b(ca)2d+1S(ac)bc^d R\left(\frac{a}{c}\right) = bc^d (1-\frac{a}{c})^{2d+1} S\left(\frac{a}{c}\right) = c^{-d-1} b(c-a)^{2d+1} S\left(\frac{a}{c}\right). Thus,
cd1b(ca)2d+1S(ac)+(akbckd)cdkQ(ac)1. |c^{-d-1} b(c-a)^{2d+1} S\left(\frac{a}{c}\right)| + \left| (a^k b - c^k d) c^{d-k} Q\left(\frac{a}{c}\right) \right| \ge 1.
That is, bca2d+1cd1S(ac)+akbckdcdkQ(ac)1|b||c-a|^{2d+1} |c^{-d-1}| |S(\frac{a}{c})| + |a^k b - c^k d| |c^{d-k}| |Q(\frac{a}{c})| \ge 1. By use of problem's assumption, we find for all u,vu, v: uS(ac)+vQ(ac)1|u| |S(\frac{a}{c})| + |v| |Q(\frac{a}{c})| \ge 1.

Assume that S(x)=ckd1xkd1++c0S(x) = c_{k-d-1}x^{k-d-1} + \cdots + c_0 be a polynomial with integer coefficients. Then, S(ac)i=0kd1ci2i=C1|S(\frac{a}{c})| \le \sum_{i=0}^{k-d-1} |c_i|2^i = C_1 which is a constant number. Furthermore, by the same argument we can find that Q(ac)C2|Q(\frac{a}{c})| \le C_2 for some constant C2C_2. This yields to:
uC1+vC21. u C_1 + vC_2 \ge 1.
The last inequality would be absurd for all sufficiently small u,vu, v. We are done.

Putting x=acx = \frac{a}{c} in (1) and multiply both sides by c2020c^{2020} it follows that
c1010A(ac)c1010P(ac)+c1010B(ac)c1010Q(ac)=c2020R. c^{1010}A\left(\frac{a}{c}\right) c^{1010}P\left(\frac{a}{c}\right) + c^{1010}B\left(\frac{a}{c}\right) c^{1010}Q\left(\frac{a}{c}\right) = c^{2020}R.
Now, using lemma 4 yielding to
c1010P(ac)(dc1010A(ac)+bc1010B(ac))=c2020dR. c^{1010} P\left(\frac{a}{c}\right) \left( d c^{1010} A\left(\frac{a}{c}\right)+b c^{1010} B\left(\frac{a}{c}\right)\right) = c^{2020} d R.
Note that if gcd(a,c)>1\gcd(a, c) > 1 then cc must divide aa. But then, bac2021uc1011|b||a-c|^{2021} \le u|c|^{1011} becomes bac1c2021uc1010|b|^{\frac{a}{c}-1}|c|^{2021} \le u|c|^{-1010}. Hence, it follows that a=ca=c. Thus, assume that gcd(a,c)=1\gcd(a, c) = 1.
Hence, c1010P(ac)c^{1010}P(\frac{a}{c}) divides c2020dRc^{2020}dR. Note that
gcd(c1010P(ac),c)=gcd(c,a1010a1010)=gcd(c,a1010)=ga1010, \gcd\left(c^{1010}P\left(\frac{a}{c}\right), c\right) = \gcd\left(c, a_{1010}a^{1010}\right) = \gcd(c, a_{1010}) = g \le |a_{1010}|,
where a1010a_{1010} is the leading coefficient of P(x)P(x). Writing c=gfc = gf, gcd(f,a1010)=1\gcd(f, a_{1010}) = 1 it follows that c1010P(ac)c^{1010}P(\frac{a}{c}) divides g2020dRg^{2020}dR. Since the number of divisors of Rdg2020Rdg^{2020} is at most 2Rg20202Ra101020202|R|g^{2020} \le 2|R|a_{1010}^{2020}, hence the total number of possibilities for aa is at most 2020Ra101020202020|R|a_{1010}^{2020}. Finally for each certain a,b=dQ(ac)P(ac)a, b = \frac{dQ(\frac{a}{c})}{P(\frac{a}{c})} would be determined uniquely. Moreover, note that P(ac)0P(\frac{a}{c}) \ne 0 because otherwise, P,QP, Q will have a common factor. Since RR only depends on the coefficients of P(x),Q(x)P(x), Q(x) we can put N=2020Ra10102020N = 2020|R|a_{1010}^{2020}. ■

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.