Divisible by?

Algebra Level 3

p ( x ) = x 7 + a x 5 + b x 3 + c x p(x) = x^7 + ax^5 + bx^3 + cx

Given that all of this polynomial's 7 roots are real and three of them are r = 1 , 2 , r = 1,2, and 3 , 3, what is the greatest integer k k such that p ( n ) p(n) is divisible by k k for all integers n ? n?


The answer is 5040.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

6 solutions

Henry U
Nov 17, 2018

Since p ( x ) p(x) has no constant term, x = 0 x=0 is another root. Also, note that all terms have x x to an odd power which means that the polynomial is an odd function. Therefore, we see that r = 1 , 2 , 3 r=-1,-2,-3 are the three remaining roots.

As p ( x ) p(x) has roots r = 3 , 2 , 1 , 0 , 1 , 2 , 3 r=-3,-2,-1,0,1,2,3 , we can write it as p ( x ) = d ( x + 3 ) ( x + 2 ) ( x + 1 ) x ( x 1 ) ( x 2 ) ( x 3 ) p(x)=d(x+3)(x+2)(x+1)x(x-1)(x-2)(x-3) . We can determine d d by multiplying this exspression out and get that d d is the coefficient of x 7 x^7 which is given as 1 1 .

What we got so far, is that p ( x ) = ( x + 3 ) ( x + 2 ) ( x + 1 ) x ( x 1 ) ( x 2 ) ( x 3 ) p(x) = (x+3)(x+2)(x+1)x(x-1)(x-2)(x-3) , so p ( x ) p(x) is the product of 7 consecutive integers. This product will always contain three multiples of 2, one of them will be a multiple of 4. Also, there will always be 2 multiples of 3, 1 multiple of 5 and 1 multiple of 7 in the product.

It is therefore always divisible by 2 4 3 2 5 1 7 1 = 5040 2^4 \cdot 3^2 \cdot 5^1 \cdot 7^1 = \boxed{5040} .

A typo in your boxed answer.

Jeremy Galvagni - 2 years, 6 months ago

Log in to reply

Oh, I'm sorry. Thanks for noting!

Henry U - 2 years, 6 months ago

Good solution

Swapan Nayak - 2 years, 6 months ago

Not sure I follow the leap you've made quite a leap to conclude the remaining solutions. Factorising the polynomial as x (x^2 - r)(x^2-s)(x^2-t) might be what you're getting at and yields the same result.

Malcolm Rich - 2 years, 6 months ago

Log in to reply

The polynomial is an odd function , this means that it has rotational symmetry with respect to tbe origin. This means that all negative roots are mirror images of the positive roots.

Henry U - 2 years, 6 months ago

Log in to reply

It's strange. I now realise that you mean p(x) only has odd powers of x which implies that p(-x) = -p(x).

From there the solution is clear.

Malcolm Rich - 2 years, 6 months ago

Very enjoyable problem and solution! I believe it needs an additional step to confirm that there is no valid k k beyond 5040. I found this less trivial than I expected, so please point out if I've overcomplicated things. My approach:

If k > 5040 k > 5040 , k k has a factor q q that is not a factor of 5040. First, suppose q q is prime, so q > 7 q > 7 . Choose n n such that q q divides n + 3 n + 3 ; then q q divides p ( n + i ) p(n + i) for i [ 0 , 6 ] i \in [0,6] . Now since q q is prime, q q divides p ( n + 7 ) = ( n + 4 ) ( n + 5 ) ( n + 6 ) ( n + 7 ) ( n + 8 ) ( n + 9 ) ( n + 10 ) p(n+7) = (n+4)(n+5)(n+6)(n+7)(n+8)(n+9)(n + 10) only if q q divides one of ( n + 4 ) , ( n + 5 ) , ( n + 6 ) , ( n + 7 ) , ( n + 8 ) , ( n + 9 ) , ( n + 10 ) (n+4), (n+5), (n+6), (n+7), (n+8), (n+9), (n + 10) . We can guarantee this is not the case when q > 7 q > 7 , as the next integer q q divides after n + 3 n + 3 is n + 3 + q n + 3 + q .

If q q is not prime, the above is not valid, since we can not guarantee an unbroken string of q q integers that do not share a factor with q q . If it is not possible to choose a prime factor of k k that is not a factor of 5040, then all factors of k k are products of 2, 3, 5 and 7 and among the factors of k k is q { 2 5 , 3 3 , 5 2 , 7 2 } q \in \{2^5, 3^3, 5^2, 7^2 \} . Therefore it suffices to find an n n for each of q { 32 , 27 , 25 , 49 } q \in \{32, 27, 25, 49 \} such that q q does not divide p ( n ) p(n) . The case p ( 4 ) = 5040 p(4) = 5040 provides the necessary counterexample for all of these.

Chris Pettitt - 2 years, 6 months ago

Log in to reply

I realised that since p ( 4 ) p (4) is the solution itself, it serves as a counterexample not only for q { 32 , 27 , 25 , 49 } q \in \{32, 27, 25, 49 \} , but for any q q that is not a factor of 5040, making the separate case for prime q q unnecessary.

Chris Pettitt - 2 years, 6 months ago

What about when n in p(n) is -3,-2,-1,0,1,2,3

Mantra 93763 - 2 years ago

Log in to reply

Then, p ( n ) p(n) will just be 0 which is divisible by any arbitrarily large number.

Henry U - 1 year, 11 months ago
Hdjdms Shsnd
Nov 26, 2018

Factor out x, then you can see that the rest is a function of x^2, so for any nonzero root, the negative of that must also be a root. Therefore the roots are -3,-2,-1,0,1,2,3, and we can factor the polynomial as 7! (x+3 choose 7). For x=4, this is equal to 7! and it will always be divisible by 7! so the answer is 7! =5040

The method of factoring into ( x + 3 7 ) \binom {x+3}7 is really elegant!

Henry U - 2 years, 6 months ago
Rocco Dalto
Nov 26, 2018

p ( x ) = x ( x 6 + a x 4 + b x 2 + c ) = x ( x 1 ) ( x 2 ( ( x 3 ) q ( x ) = ( x 3 6 x 2 + 11 x 6 ) q ( x ) p(x) = x(x^6 + ax^4 + bx^2 + c) = x(x - 1)(x - 2((x - 3)q(x) = (x^3 - 6x^2 + 11x - 6)q(x)

Dividing we obtain the quotient q ( x ) = x 3 + 6 x 2 + ( a + 25 ) x + 6 ( a + 15 ) q(x) = x^3 + 6x^2 + (a + 25)x + 6(a + 15) and the remainder 25 a + b + 301 ) x 2 + ( 60 a 840 ) x + ( 36 a + c + 540 ) 25a + b + 301)x^2 + (-60a - 840)x + (36a + c + 540)

The problem has all real roots \implies the remainder must be zero 25 a + b + 301 = 0 , 60 a 840 = 0 \implies 25a + b + 301 = 0, \:\ -60a - 840 = 0 and 36 a + c + 540 = 0 a = 14 , b = 49 36a + c + 540 = 0 \implies a = -14, \:\ b = 49 and c = 36 c = -36

q ( x ) = x 3 + 6 x 2 + 11 x + 6 = ( x + 1 ) ( x + 2 ) ( x + 3 ) p ( n ) = ( n + 3 ) ( n + 2 ) ( n + 1 ) n ( n 1 ) ( n 2 ) ( n 3 ) \implies q(x) = x^3 + 6x^2 + 11x + 6 = (x + 1)(x + 2)(x + 3) \implies p(n) = (n + 3)(n + 2)(n + 1)n(n - 1)(n - 2)(n - 3)

Using n = 4 p ( n ) = 7 ! = 2 4 3 2 5 7 k = 5040 n = 4 \implies p(n) = 7! = 2^4 * 3^2 * 5 * 7 \implies k = \boxed{5040}

How do you go from $p(4) = 7!$ to $k=7!$ ?

Andrea Di Biagio - 2 years, 6 months ago
Vinod Kumar
Nov 27, 2018

First set polynomial as

p(x)=x(x-1)(x+1)(x-2)(x+2(x-3)(x+3),

gives

p(x) = (x^7) - 14(x^5) + 49(x^3) - 36(x)

Then, p(1), p(2), p(3)=0 and p(4)=5040, p(5)=40320, etc

Further, GCD=5040 for all p(4) and beyond.

Answer=5040

Malcolm Rich
Nov 29, 2018

For a longer solution let's first solve for a,b and c. And let's consider the 6th order polynomial by first dividing it by x

We know that x=1 is a root so the polynomial must divide by (x-1). Dividing the polynomial by (x-1) yields 1+a+b+c =0

Doing the same with (x-2) and (x-3) yield two further equations:

64+16a+4b+c=0 and 729+81a+9b+c=0.

Solving the simultaneous equations yields (a,b,c) = (-14,49,-36)

Now divide our 6th order polynomial by (x-1),(x-2) and (x-3) to leave x^3+6x^2+11x+6 = (x+1)(x^2+5x+6) = (x+1)(x+2)(x+3)

And so the original polynomial factorises as the product of 7 consecutive integers which must include factors of 16(3 even numbers including one multiple of 4),9(2 multiples of 3),5 and 7.

I did it the same way, but it's a lot more work than just noticing the function is odd.

Zac Mann - 2 years, 6 months ago
K T
Nov 27, 2018

Since p is an odd function, the roots must be -3,-2,-1,0,1,2,3, so p ( n ) = ( n + 3 ) ( n + 2 ) ( n + 1 ) ( n ) ( n 1 ) ( n 2 ) ( n 3 ) p(n)= (n+3)(n+2)(n+1)(n)(n-1)(n-2)(n-3) For any integer n this is the product of 7 consecutive integers, so there must be at least three multiples of 2, of which at least one multiple of 4, two multiples of 3, one multiple of 5 and one multiple of 7 among its factors, and hence

2 4 × 3 2 × 5 × 7 = 5040 2^4×3^2×5×7=5040 must divide it.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...