A Six Degree Polynomial

The coefficients of a 6th degree polynomial P(x) are integers and its roots are 6 different prime numbers. There exist two integers A and B such that P(A) = 65536 and P(B) = 45441. P(75) < 0. Find the 6 roots. [Explain how you got your answer. -KD]

Source: Reader Philippe Fondanaiche.

Solutions were received from Dane Brooke, Jozef Hanenberg, Hareendra Yalamanchili, and Graeme McRae. Some solutions are included below.

From Jozef Hanenberg:

Solution: P(X) = (X-73)(X-89)(X-97)(X-103)(X-107)(X-109) where P(105)=65536 and P(106)=45441. Also P(75)<0 is satisfied.

Explanation: Let the six roots be p1, p2, p3, p4, p5 and p6. We can factorize the polynomial:
P(X) = c(X-p1)(X-p2)...(X-p6), where c is the coefficient of X^6.

Note that 65536 = 2^16 and 45441 = 3^5 x 11 x 17. Substituting A and B we find

i) c(A-p1)(A-p2)(A-p3)(A-p4)(A-p5)(A-p6) = 2^16 and

ii) c(B-p1)(B-p2)(B-p3)(B-p4)(B-p5)(B-p6) = 3^5 x 11 x 17.

Because all factors of 3^5 x 11 x 17 are odd and at least 5 of the primes are odd, we find that B must be even. If 2 would be one of the primes (let's say p1) then B-p1 would be even, which can't be true; therefore all primes are odd. Because of ii) c must be odd, and because of i) c must therefore be +1 or -1. From i) it follows also that A must be odd and the six numbers A-p1, ...., A-p6 are all of the form +2^m or -2^m, where m is at least 1. They are all different and their product is +2^16 or -2^16.

This leaves the next possibillities for the six numbers A-p1,...,A-p6: 

 
    2        -2        4       -4        8(-8)        128(-128)
    2        -2        4        -4        16(-16)    64(-64)
    2        -2        4        -4        32            -32
    2        -2        4(-4)    8        -8           64(-64)
    2        -2        4(-4)    8(-8)    16(-16)    32(-32)
    2        -2        8        -8        16            -16
    2(-2)    4        -4        8        -8            32(-32)
The six numbers B-p1,......,B-p6 all belong to the set of divisors of 3^5 x 11 x 17. There are 48 of these divisors (where we count for instance 3 and -3 as two different divisors). Write these divisors in a sequence and look at the differences: 
 
divisors......-81    -51    -33    -27    -17    -11    -9    -3    -1    1    3    9    11    17    27    33    51    81......
difference       30       18     6      10     6       2      6    2     2     2    6    2    6      10    6      18    30
(we have only given the relevant part of the sequence)

Note that the five differences between the six numbers A-p1,...A-p6 must be the same as the five differences between the six numbers B-p1,....,B-p6. After some tedious matching you will find that there only two possible cases: 

 
I)     A-p1 = -32    A-p2 = -16    A-p3 = -8    A-p4 = -2    A-p5 = 2    A-p6 = 4
       B-p1 = -33    B-p2 = -17    B-p3 = -9    B-p4 = -3    B-p5 = 1    B-p6 = 3
The six primes are (in decreasing order) A+32, A+16, A+8, A+2, A-2 and A-4. Further B =A-1. and 
II)    A-p1 = -4        A-p2 = -2    A-p3 = 2    A-p4 = 8    A-p5 = 16    A-p6 = 32
       B-p1 = -3        B-p2 = -1    B-p3 = 3    B-p4 = 9    B-p5 = 17    B-p6 = 33
The six primes are (in decreasing order) A+4, A+2, A-2, A-8, A-16 and A-32. Further B =A+1.

Take the product and look at i) and ii) above and you find that c=1. Therefore P(X) = (X-p1)(X-p2).....(X-p6).

Because P(75) < 0, the smallest prime must be smaller than 75 and the largest one must be larger then 75. It follows that in case I) 43 < A < 79 and in case II) 71 < A < 107. These conditions limit the possibillities considerably. In fact only the solution given above remains.

From Hareendra Yalamanchili:
P(x)=k*(x-a)(x-b)(x-c)(x-d)(x-e)(x-f). The roots are all integers, so k is an integer. The gcd of P(A) and P(B) is 1, so k is either 1 or -1. P(A)=2^16=+-(A-a)(A-b)(A-c)(A-d)(A-e)(A-f), so A must be odd, and each of the (A-?) is a power of 2. 45441=11*17*243 = (B-a)*...*(B-f) and B is even.

Noticing that 11*3-17 = 16, suggests that two of the factors for each are
33, 17 and
32, 16
Then the remaining 4 factors for P(B) must have a product of
81=9*3*-1*-3
33,17,9,3,-1,-3
32,16,8,2,-2,-4

So a=B-33, b=B-17, c=B-9, d=B-3, e=B+1, and f=B+3

If B+3 is divisible by 3, then so is B-3. If B+1 is divisible by 3, then so is B-17. Since in both of these cases, we would have 2 primes divisible by 3, B-1 must be divisible by 3. If B-1=6n+3(B is even), then we have 6 primes 6n-29, 6n-13, 6n-5, 6n+1, 6n+5, 6n+7.
P(75)<0 so 6n+7>75, and 6n-29<75. Checking the possibilities gives 109, 107, 103, 97, 89, and 73.

From Graeme McRae:

I noticed that 65536 has 2^16 as its prime factorization, so its factors are all powers of 2.

Then I factorized 45441 as 3^5 * 11 * 17

Now I want to express 65536 as the product of 6 different integers a, b, c, d, e, and f. And I want to express 45441 as a product of 6 integers a+k, b+k, c+k, d+k, e+k, and f+k.

Seeing right away that 3 and 17, both factors of 45441 are one more than powers of 2, It occurred to me that k might equal 1. If so, then I asked myself, can 45441 be expressed as the product of six different integers, each one more than a power of 2?

At least one of the six numbers must be negative, because the product of a+k, b+k, c+k, d+k, e+k, and f+k is smaller than the product of a, b, c, d, e, and f. A little experimenting, and I soon realized the six numbers are -4, -2, 2, 8, 16, and 32.

Now to find the prime roots, I just started looking for an integer m such that a+m, b+m, c+m, d+m, e+m, and f+m are all prime. Soon I hit on m=15, making the prime roots 11, 13, 17, 23, 31, 47, so the polynomial is

P(x)=(x-11)(x-13)(x-17)(x-23)(x-31)(x-47)

Is this it? No, because P(75)>0. So I'll have to look for a bigger m -- one that makes an odd number of roots larger than 75. Bad luck. I checked every such m, and none of them give me six prime roots.

Fourth and long. Time to punt.

Let's negate each of my a, b, c, d, e, and f, and start over.

Now these six variables are -32, -16, -8, -2, 2, and 4. An m that makes a+m etc. prime and P(75)<0 is 105.

So the polynomial is P(x) = (x-73)(x-89)(x-97)(x-103)(x-107)(x-109) and P(75) is indeed less than zero.

Mail to Ken