Polynomial Division

[xcrunner448]

1. The problem statement, all variables and given/known data

This question was on a test in a math contest I was recently in, and I cannot seem to figure out how to get the answer:

Let f(x)=x7+x6+x5+x4+x3+x2+x+1. If k is a positive integer such that 53 < k < 115, find the sum of all distinct k such that the numerical remainder when the polynomial f(xk) is divided by the polynomial f(x) must be 8.


3. The attempt at a solution

I really have no idea where to begin on this one. Obviously, attempting polynomial long division would not work here, so there has to be some other way of determining the remainder, and I am at a loss as to what that would be. Any suggestions would be greatly appreciated.

[QuarkCharmer]

Seems like you could figure this out using something called the Remainder Theorem.

[xcrunner448]

Doesn't that say that when you divide a polynomial f(x) by (x-a) the remainder is f(a)? I don't see how that helps here.

[LCKurtz]

I don't right off know if it's relevant, but maybe you can somehow use the fact that

f(x) = \frac{x^8-1}{x-1}

[Mentallic]

Maybe I've forgotten a little something about polynomial division, but would someone please clarify this trouble I'm having with this problem?

It says when f(xk) is divided by f(x) leaving a numerical remainder of 8. How could we possibly get a numerical remainder of 8?

For example, if we have f(x)=x2-1 and g(x)=x-1 then f(x)/g(x)=x+1 and our numerical remainder is... 1?

[LCKurtz]

Maybe I've forgotten a little something about polynomial division, but would someone please clarify this trouble I'm having with this problem?

It says when f(xk) is divided by f(x) leaving a numerical remainder of 8. How could we possibly get a numerical remainder of 8?

For example, if we have f(x)=x2-1 and g(x)=x-1 then f(x)/g(x)=x+1 and our numerical remainder is... 1?

Good question. I was wondering the same thing and figured I just didn't know....

[Mentallic]

Good question. I was wondering the same thing and figured I just didn't know....

This question has reached a whole new level of hard :biggrin:

[Dick]

This question has reached a whole new level of hard :biggrin:

How you get a remainder of 8 isn't the hard part. k=0 gives a remainder of 8. k=1 gives a remainder of 0. Both of those are obvious. It starts getting harder at k=2. The remainder is a sixth degree polynomial in x (hence not 8). I suggest looking at small values of k and trying to figure out what the pattern might be. I know what the pattern is, but I haven't figured out an easy way to explain it yet.

[Mentallic]

How you get a remainder of 8 isn't the hard part. k=0 gives a remainder of 8. k=1 gives a remainder of 0. Both of those are obvious. It starts getting harder at k=2. The remainder is a sixth degree polynomial in x (hence not 8). I suggest looking at small values of k and trying to figure out what the pattern might be. I know what the pattern is, but I haven't figured out an easy way to explain it yet.

k=1 gives a remainder of 0 how? for k=1, f(xk)=f(x)=x7+x6+...x+1

Maybe this a push in the right direction? I see 8's involved so I'm feeling hopeful - knowing full well the 8's have little to do with a remainder of 8, regardless...

f(x)=\frac{x^8-1}{x-1}

f(x^k)=\frac{x^{8k}-1}{x^k-1}

\frac{f(x^k)}{f(x)}=\frac{(x^{8k}-1)(x-1)}{(x^k-1)(x^8-1)}

Now expanding back out, but rather with the opposite factors, that is, the \frac{x^{8k}-1}{x^8-1} will give

\frac{f(x^k)}{f(x)}=\frac{x^{8(k-1)}+x^{8(k-2)}+...+x^8+1}{x^{k-1}+x^{k-2}+...+x+1}

But then again I'm just playing with numbers and have little to no clue where I'm going with any of this. I need a clearer understanding of what the remainder of 8 is.

EDIT: oh I totally forgot about dividing f(xk) with f(x) when thinking about the k=1 remainder. So the remainder when k=1 would be 1 0.

[Dick]

k=1 gives a remainder of 0 how? for k=1, f(xk)=f(x)=x7+x6+...x+1


EDIT: oh I totally forgot about dividing f(xk) with f(x) when thinking about the k=1 remainder. So the remainder when k=1 would be 1.

If k=0, f(x^0)=0*f(x)+8. Quotient 0. Remainder 8. If k=1, f(x^1)=1*f(x)+0. Quotient 1. Remainder 0.

[Mentallic]

If k=0, f(x^0)=0*f(x)+8. Quotient 0. Remainder 8. If k=1, f(x^1)=1*f(x)+0. Quotient 1. Remainder 0.

Oh right, I've been speaking of the quotient this whole time...

[Dick]

Here's a hint. Try and show f(x^k)-f(x^(k+8)) is divisible by f(x). That simplifies the problem a bit.

[Dick]

So nobody is interested in being a math contest champ anymore? In the end, it turns out you can do it pretty easily.

[Mentallic]

So nobody is interested in being a math contest champ anymore? In the end, it turns out you can do it pretty easily.

Would you care to do the honours?

[Dick]

Would you care to do the honours?

It's more fun if you figure out some of it on your own. I already give you one clue in post 12. Here are some more. You can also show f(x^k)-f(x^(8-k)) is divisible by f(x). That really cuts down the list of possible remainders. Finally to actually test whether a remainder is 8 write the factored form f(x^k)=q(x)*f(x)+r(x). If a is root of f(x) and you put x equal to a you had better get f(a^k)=8 if the remainder is 8. Factor f(x) to find roots. If you put all of that together you should be able to do it without spending the couple of hours on it that I did.

[Mentallic]

It's more fun if you figure out some of it on your own.
Oh don't get me wrong, I've spent a considerable number of hours on this problem in total, and it didn't seem like I was getting anywhere fast with your hint from #12 so I admitted defeat.

I already give you one clue in post 12. Here are some more. You can also show f(x^k)-f(x^(8-k)) is divisible by f(x). That really cuts down the list of possible remainders. Finally to actually test whether a remainder is 8 write the factored form f(x^k)=q(x)*f(x)+r(x). If a is root of f(x) and you put x equal to a you had better get f(a^k)=8 if the remainder is 8. Factor f(x) to find roots. If you put all of that together you should be able to do it without spending the couple of hours on it that I did.

I'll give it another shot and see how it goes.

[Dick]

You've figured out if f(x^k)-f(x^(k+8)) is divisible by f(x) then f(x^k) and f(x^(k+8)) have the same remainder when divided by f(x), right? That means you only need to figure out whether the remainder is 8 for k=0,1,...7.