Find the numerical remainder?

Question

Let f(x)=x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1. What is the numerical remainder when the polynomial f(x^16) is divided by the polynomial f(x).

Answer 1

This is a very nice problem.

Of course you can use brute force, and do the full long division on f(x^16)
http://en.wikipedia.org/wiki/Polynomial_long_division

But, fortunately (actually, by design), there is a short cut - if we can factor f(x^16), then we don't have to do all the hard work.

Consider any polynomials g(x) and h(x) and suppose that h(x) factors so that:

h(x) = u(x)(v(x)

then h(x)/g(x) = (u(x)v(x))/g(x) = u(x)(v(x)/g(x))

now suppose we divide g(x) into v(x) getting q(x) and r(x):
h(x)/g(x) = u(x)((g(x)q(x) + r(x))/g(x) = u(x)q(x) + (u(x)r(x))/g(x))

Similarly, we can divide u(x) by g(x) to get t(x) and w(x) so
h(x)/g(x) = u(x)q(x) + ((t(x)g(x) + w(x))r(x))/g(x) = u(x)q(x) + t(x)r(x) + (w(x)r(x))/g(x)

So if we are only concerned about the remainder, we only have to worry about the remainders when dividing each factor.

So now let's factor f(x^16). Recall two facts:

1 + x + x^2 + ... + x^n = (x^(n+1) - 1)/(x-1)
a^2 - b^2 = (a + b)(a - b)

so:
f(x) = 1 + x + ... + x^7 = (x^8 - 1)/(x-1) so
f(x) = (x^4 + 1)(x^4 - 1)/(x-1) = (x^4 + 1)(x^2 + 1)(x + 1)(x - 1)/(x - 1) or
f(x) = (x^4 + 1)(x^2 + 1)(x + 1)

thus

f(x^16) = (x^64 + 1)(x^32 + 1)(x^16 + 1)

so we've factored f(x^16) into three simple factors.

Furthermore, if you try dividing x^16 + 1 by f(x) you will see a pattern that you can apply to the other two divisions.