Maths Olympiad Prep

Library / /12 of 22

Algebra Difficulty 5.3 AIME, harder Find the answer Italy

Two monic polynomials (that is, with leading coefficient equal to 1) with integer coefficients p(x)p(x) and q(x)q(x) are such that their greatest common divisor is (x1)(x2)(x-1)(x-2), their least common multiple is (x1)2(x2)3(x3)(x+1)(x-1)^2(x-2)^3(x-3)(x+1) and the degree of p(x)p(x) is less than or equal to the degree of q(x)q(x). In how many ways can p(x)p(x) be chosen?

Pick one

Solution

The answer is (C)\mathbf{(C)}. Let us consider the four factors of the least common multiple A(x)=(x1)2A(x) = (x-1)^2, B(x)=(x2)3B(x) = (x-2)^3, C(x)=x3C(x) = x-3 and D(x)=x+1D(x) = x+1. In order for the least common multiple of p(x)p(x) and q(x)q(x) to be A(x)B(x)C(x)D(x)A(x) B(x) C(x) D(x), it is necessary that each of the four factors divides at least one of the two polynomials; on the other hand, each factor divides exactly one of the two polynomials, otherwise it would divide the greatest common divisor of the two (which we know to be equal to (x1)(x2)(x-1)(x-2)).

Let us first ignore the condition on the degree of the two polynomials. Once we have decided which of the four factors appear in p(x)p(x), it is determined: it is the least common multiple between the product of the chosen factors and (x1)(x2)(x-1)(x-2); likewise, q(x)q(x) is also determined: it is the least common multiple between the factors not chosen and (x1)(x2)(x-1)(x-2).

Note that p(x)p(x) and q(x)q(x) cannot have the same degree, since their product turns out to be A(x)B(x)C(x)D(x)(x1)(x2)A(x) B(x) C(x) D(x) (x-1)(x-2), which has degree 99, hence odd. We conclude that the number of ordered pairs of polynomials (p(x),q(x))(p(x), q(x)) with the given greatest common divisor and least common multiple is 24=162^4 = 16 (the number of subsets of the set of the four factors A(x),B(x),C(x),D(x)A(x), B(x), C(x), D(x)).

On the other hand, swapping the two polynomials of the pair reverses the inequality (which we know to be strict) between the degrees: exactly one pair out of every two is such that the degree of p(x)p(x) is greater than that of q(x)q(x). The correct answer is therefore 88.

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