Two monic polynomials (that is, with leading coefficient equal to 1) with integer coefficients and are such that their greatest common divisor is , their least common multiple is and the degree of is less than or equal to the degree of . In how many ways can be chosen?
Pick one
Solution
The answer is . Let us consider the four factors of the least common multiple , , and . In order for the least common multiple of and to be , 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 ).
Let us first ignore the condition on the degree of the two polynomials. Once we have decided which of the four factors appear in , it is determined: it is the least common multiple between the product of the chosen factors and ; likewise, is also determined: it is the least common multiple between the factors not chosen and .
Note that and cannot have the same degree, since their product turns out to be , which has degree , hence odd. We conclude that the number of ordered pairs of polynomials with the given greatest common divisor and least common multiple is (the number of subsets of the set of the four factors ).
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 is greater than that of . The correct answer is therefore .