Define the polynomials
Q0(x)Q1(x)Q2(x)Q3(x)Q4(x)Q5(x)Q6(x)=b0,=b1(x+1),=b2(x+1)(x+3),=b3(x+1)(x+3)(x+5),=b4(x+1)(x+3)(x+5)(x+7),=b5(x+1)(x+3)(x+5)(x+7)(x+9),=b6(x+1)(x+3)(x+5)(x+7)(x+9)(x+11),
where
b0=210,b1=29,…,b2=27,b3=26,b4=23,b5=22,b6=20.
The product of i consecutive even integers is divisible by 2i⋅i!. Therefore, for i=0,1,2,3,4,5,6, we obtain that the product of i consecutive even integers is divisible by 20,21,23,24,27,28,210, respectively. This implies that, for any odd integer x and i=0,…,6, Qi(x) is divisible by 210.
A polynomial P(x)=a0+a1x+a2x2+a3x3+a4x4+a5x5 with integer coefficients is called reduced if, for i=0,…,5,
0≤ai<bi.(†)
Clearly, there are exactly b0b1…b5=210+9+7+6+3+2=237 distinct reduced polynomials.
We show that, for every polynomial P(x) with integer coefficients, there exists a reduced polynomial Pˉ(x) such that P(x) and Pˉ(x) have the same remainder sequence.
First note that, for i=0,…,6, and any polynomial R(x) with integer coefficients P(x) and P(x)−R(x)Qi(x) have the same remainder sequence. This follows from the fact that Qi(x) is divisible by 210, for any odd integer x.
If the degree d of P(x)=a0+⋯+adxd is higher than 5 we may replace P(x) by P(x)−adxd−6Q6(x). Indeed, the polynomial P(x)−adxd−6Q6(x) has smaller degree than P(x) and has the same remainder sequence as P(x). We may continue this until we obtain a polynomial that of degree at most 5 that has the same remainder sequence as P(x).
We assume now that P(x) has degree no higher than 5. If P(x) is reduced we are done. Otherwise, let i be the highest degree of a coefficient ai of xi that does not satisfy the range condition (†). If q is the quotient obtained by dividing ai by bi then P(x) and P(x)−qQi(x) have the same remainder sequence and the coefficient at degree i in P(x)−qQi(x) is in the correct range 0,…,bi−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).
We now consider the 237 reduced polynomials.
Let a=29+1 and b=1. Then P(a)−P(b)=(a−b)(a1+a2A2+a3A3+a4A4+a5A5), where A2=a+b, A3=a2+ab+b2, A4=a3+a2b+ab2+b3 and A5=a4+a3b+a2b2+ab3+b4. Since both a and b are odd, A2 and A4 are even, A3 and A5 are odd, and the parity of a1+a2A2+a3A3+a4A4+a5A5 is the same as the parity of a1+a3+a5. Therefore, if a1+a3+a5 is even P(a)−P(b) is divisible by 210 and the sequence of remainders of P(x) is not a permutation.
For an odd integer x, the parity of P(x)=a0+a1x+a2x2+a3x3+a4x4+a5x5 is the same as the parity of the sum a0+a1+⋯+a5. Thus, only polynomials with odd sum of coefficients have odd remainders.
Therefore, there are no more remainder sequences that are permutations of 1,3,…,1023 than there are reduced polynomials P(x)=a0+a1x+a2x2+a3x3+a4x4+a5x5 for which both a1+a3+a5 and a0+a1+a2+a3+a4+a5 are odd.
There are exactly 236 reduced polynomials for which a1+a3+a5 is odd. This can be seen by pairing up every reduced polynomial P(x) in which a1 is even with the polynomial P(x)+x. Exactly one of the two polynomials in each such pair has odd sum a1+a3+a5.
There are exactly 235 reduced polynomials for which both a1+a3+a5 and a0+a1+a2+a3+a4+a5 are odd. This can be seen by pairing up every reduced polynomial P(x) in which a1+a3+a5 is odd and a0 is even with the polynomial P(x)+1. Exactly one of the two polynomials in each such pair has odd sum a0+a1+a2+a3+a4+a5.