Maths Olympiad Prep

Library / /36 of 45

Number theory Difficulty 8.9 Shortlist Prove it United States

For a polynomial P(x)P(x) with integer coefficients, r(2i1)r(2i - 1) (for i=1,2,3,,512i = 1, 2, 3, \dots, 512) is the remainder obtained when P(2i1)P(2i - 1) is divided by 10241024. The sequence
(r(1),r(3),,r(1023)) (r(1), r(3), \dots, r(1023))
is called the remainder sequence of P(x)P(x). A remainder sequence is called complete if it is a permutation of (1,3,5,,1023)(1, 3, 5, \dots, 1023). Prove that there are no more than 2352^{35} different complete remainder sequences.

Solution

Define the polynomials
Q0(x)=b0,Q1(x)=b1(x+1),Q2(x)=b2(x+1)(x+3),Q3(x)=b3(x+1)(x+3)(x+5),Q4(x)=b4(x+1)(x+3)(x+5)(x+7),Q5(x)=b5(x+1)(x+3)(x+5)(x+7)(x+9),Q6(x)=b6(x+1)(x+3)(x+5)(x+7)(x+9)(x+11), \begin{align*} Q_0(x) &= b_0, \\ Q_1(x) &= b_1 (x + 1), \\ Q_2(x) &= b_2 (x + 1)(x + 3), \\ Q_3(x) &= b_3 (x + 1)(x + 3)(x + 5), \\ Q_4(x) &= b_4 (x + 1)(x + 3)(x + 5)(x + 7), \\ Q_5(x) &= b_5 (x + 1)(x + 3)(x + 5)(x + 7)(x + 9), \\ Q_6(x) &= b_6 (x + 1)(x + 3)(x + 5)(x + 7)(x + 9)(x + 11), \end{align*}
where
b0=210,b1=29,,b2=27,b3=26,b4=23,b5=22,b6=20. b_0 = 2^{10}, \quad b_1 = 2^9, \quad \dots, b_2 = 2^7, \quad b_3 = 2^6, \quad b_4 = 2^3, \quad b_5 = 2^2, \quad b_6 = 2^0.
The product of ii consecutive even integers is divisible by 2ii!2^i \cdot i!. Therefore, for i=0,1,2,3,4,5,6i = 0, 1, 2, 3, 4, 5, 6, we obtain that the product of ii consecutive even integers is divisible by 20,21,23,24,27,28,2102^0, 2^1, 2^3, 2^4, 2^7, 2^8, 2^{10}, respectively. This implies that, for any odd integer xx and i=0,,6i = 0, \dots, 6, Qi(x)Q_i(x) is divisible by 2102^{10}.
A polynomial P(x)=a0+a1x+a2x2+a3x3+a4x4+a5x5P(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + a_4x^4 + a_5x^5 with integer coefficients is called reduced if, for i=0,,5i = 0, \dots, 5,
0ai<bi.() 0 \le a_i < b_i. \qquad (\dagger)
Clearly, there are exactly b0b1b5=210+9+7+6+3+2=237b_0b_1\dots b_5 = 2^{10+9+7+6+3+2} = 2^{37} distinct reduced polynomials.
We show that, for every polynomial P(x)P(x) with integer coefficients, there exists a reduced polynomial Pˉ(x)\bar{P}(x) such that P(x)P(x) and Pˉ(x)\bar{P}(x) have the same remainder sequence.
First note that, for i=0,,6i = 0, \dots, 6, and any polynomial R(x)R(x) with integer coefficients P(x)P(x) and P(x)R(x)Qi(x)P(x) - R(x)Q_i(x) have the same remainder sequence. This follows from the fact that Qi(x)Q_i(x) is divisible by 2102^{10}, for any odd integer xx.

If the degree dd of P(x)=a0++adxdP(x) = a_0 + \cdots + a_d x^d is higher than 55 we may replace P(x)P(x) by P(x)adxd6Q6(x)P(x) - a_d x^{d-6} Q_6(x). Indeed, the polynomial P(x)adxd6Q6(x)P(x) - a_d x^{d-6} Q_6(x) has smaller degree than P(x)P(x) and has the same remainder sequence as P(x)P(x). We may continue this until we obtain a polynomial that of degree at most 55 that has the same remainder sequence as P(x)P(x).
We assume now that P(x)P(x) has degree no higher than 55. If P(x)P(x) is reduced we are done. Otherwise, let ii be the highest degree of a coefficient aia_i of xix^i that does not satisfy the range condition ()(\dagger). If qq is the quotient obtained by dividing aia_i by bib_i then P(x)P(x) and P(x)qQi(x)P(x) - qQ_i(x) have the same remainder sequence and the coefficient at degree ii in P(x)qQi(x)P(x) - qQ_i(x) is in the correct range 0,,bi10, \dots, b_i - 1.
We repeat this procedure with the next highest degree that has a coefficient out of range until we reach a reduced polynomial that has the same remainder sequence as P(x)P(x).

We now consider the 2372^{37} reduced polynomials.
Let a=29+1a = 2^9+1 and b=1b = 1. Then P(a)P(b)=(ab)(a1+a2A2+a3A3+a4A4+a5A5)P(a)-P(b) = (a-b)(a_1+a_2A_2+a_3A_3+a_4A_4+a_5A_5), where A2=a+bA_2 = a+b, A3=a2+ab+b2A_3 = a^2+ab+b^2, A4=a3+a2b+ab2+b3A_4 = a^3+a^2b+ab^2+b^3 and A5=a4+a3b+a2b2+ab3+b4A_5 = a^4+a^3b+a^2b^2+ab^3+b^4. Since both aa and bb are odd, A2A_2 and A4A_4 are even, A3A_3 and A5A_5 are odd, and the parity of a1+a2A2+a3A3+a4A4+a5A5a_1+a_2A_2+a_3A_3+a_4A_4+a_5A_5 is the same as the parity of a1+a3+a5a_1+a_3+a_5. Therefore, if a1+a3+a5a_1+a_3+a_5 is even P(a)P(b)P(a)-P(b) is divisible by 2102^{10} and the sequence of remainders of P(x)P(x) is not a permutation.
For an odd integer xx, the parity of P(x)=a0+a1x+a2x2+a3x3+a4x4+a5x5P(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + a_4x^4 + a_5x^5 is the same as the parity of the sum a0+a1++a5a_0 + a_1 + \cdots + a_5. Thus, only polynomials with odd sum of coefficients have odd remainders.
Therefore, there are no more remainder sequences that are permutations of 1,3,,10231, 3, \dots, 1023 than there are reduced polynomials P(x)=a0+a1x+a2x2+a3x3+a4x4+a5x5P(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + a_4x^4 + a_5x^5 for which both a1+a3+a5a_1 + a_3 + a_5 and a0+a1+a2+a3+a4+a5a_0 + a_1 + a_2 + a_3 + a_4 + a_5 are odd.
There are exactly 2362^{36} reduced polynomials for which a1+a3+a5a_1+a_3+a_5 is odd. This can be seen by pairing up every reduced polynomial P(x)P(x) in which a1a_1 is even with the polynomial P(x)+xP(x)+x. Exactly one of the two polynomials in each such pair has odd sum a1+a3+a5a_1+a_3+a_5.
There are exactly 2352^{35} reduced polynomials for which both a1+a3+a5a_1+a_3+a_5 and a0+a1+a2+a3+a4+a5a_0+a_1+a_2+a_3+a_4+a_5 are odd. This can be seen by pairing up every reduced polynomial P(x)P(x) in which a1+a3+a5a_1+a_3+a_5 is odd and a0a_0 is even with the polynomial P(x)+1P(x)+1. Exactly one of the two polynomials in each such pair has odd sum a0+a1+a2+a3+a4+a5a_0+a_1+a_2+a_3+a_4+a_5.

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.