Problem:
Let P(x) be a polynomial with rational coefficients such that when P(x) is divided by the polynomial x2+x+1, the remainder is x+2, and when P(x) is divided by the polynomial x2+1, the remainder is 2x+1. There is a unique polynomial of least degree with these two properties. What is the sum of the squares of the coefficients of that polynomial?
Answer Choices:
A. 10
B. 13
C. 19
D. 20
E. 23
Solution:
Write P(x)=Q(x)(x2+x+1)+(x+2) for some polynomial Q(x) with rational coefficients. It follows that x2+1 divides
P(x)−(2x+1)=Q(x)(x2+1)+xQ(x)−x+1
Thus xQ(x)−x+1 is a multiple of x2+1. Hence the degree of Q(x) is at least 1 . Assume that Q(x)=ax+b and that xQ(x)−x+1=c(x2+1) for some rational numbers a,b, and c. Then c=1 and a=b=1. Therefore the polynomial of least degree is
P(x)=(x+1)(x2+x+1)+(x+2)=x3+2x2+3x+3
The requested sum of squares is 12+22+32+32=(E)23.
OR
Divide (x2+x+1)(x2+1) into P(x) to obtain a quotient polynomial Q(x) and a remainder R(x). Thus
P(x)=Q(x)(x2+x+1)(x2+1)+R(x)
When R(x) is divided by x2+x+1 it gives the same remainder, x+2, as does P(x), and when R(x) is divided by x2+1 it gives the same remainder, 2x+1, as does P(x). But R(x) has degree at most 3 , so the polynomial of least degree having the desired properties has degree at most 3 . Let P(x)=a3x3+a2x2+a1x+a0 where the values of the coefficients ai are to be determined. Polynomial division yields
P(x)=(a3x+a2−a3)(x2+x+1)+(a1−a2)x+a0−a2+a3=(a3x+a2)(x2+1)+(a1−a3)x+a0−a2
For P(x) to have the desired properties, the ai must be chosen so that
a1−a2=1a0−a2+a3=2a1−a3=2a0−a2=1.
To solve this system, first subtract the fourth equation from the second to see that a3=1. Then insert this information into the third equation to see that a1=3. Insert this value of a1 in the first equation to see that a2=2. Finally, insert this value of a2 into the fourth equation to see that a0=3. Thus P(x)=x3+2x2+3x+3, as above.
Let P(x) be any polynomial that yields the required remainders. By polynomial division, there exist polynomials Q(x) and R(x) such that
P(x)=Q(x)(x2+x+1)(x2+1)+R(x)
where R(x) has degree less than or equal to 3 . The polynomial R(x) also yields the two required remainders, and a polynomial that yields the required remainders and has degree less than or equal to 3 is unique. Indeed, if there were two of them, say R1(x) and R2(x), then put S(x)= R1(x)−R2(x). Both x2+x+1 and x2+1 evenly divide S(x). Because the two divisors are relatively prime, their product (which has degree 4) divides S(x). Because S(x) has degree less than or equal to 3 , this is possible only if S(x) is identically zero.\
Because P(x) yields the desired remainder when divided by x2+x+1, which is to say that there is a polynomial Q1(x) such that
P(x)=Q1(x)(x2+x+1)+x+2(1)
It suffices to find all Q1(x) such that there exists a polynomial Q2(x) such that
Q1(x)(x2+x+1)+x+2=Q2(x)(x2+1)+2x+1
that is,
Q1(x)(x2+x+1)=Q2(x)(x2+1)+x−1(2)
A brief application of the Extended Euclidean Algorithm yields
−x(x2+x+1)+(x+1)(x2+1)=1
Multiply both sides of this by x−1, and rearrange, to see that
(−x2+x)(x2+x+1)=(1−x2)(x2+1)+x−1
Subtract the respective sides of this from equation (2) to see that
(Q1(x)+x2−x)(x2+x+1)=(Q2(x)+x2−1)(x2+1)
Because x2+x+1 and x2+1 are relatively prime, it follows that x2+1 divides the first factor on the left-hand side above. That is, there is a polynomial K(x) such that Q1(x)=−x2+x+K(x)(x2+1). For Q1(x) of this form, the polynomial P(x) will have the desired remainder when divided by x2+1. Substitute this formula for Q1(x) into (1) to see that
P(x)=(−x2+x+K(x)(x2+1))(x2+x+1)+x+2=−x4+2x+2+K(x)(x2+x+1)(x2+1)
The desired polynomial of least degree occurs when K(x)=1 - that is, when P(x)=x3+2x2+ 3x+3, as above. As a quick check,
x3+2x2+3x+3=(x+1)(x2+x+1)+x+2=(x+2)(x2+1)+2x+1
Note: The calculation completed in the third solution generalizes to give an analogue for polynomials of the Chinese Remainder Theorem.
The problems on this page are the property of the MAA's American Mathematics Competitions