The question is find the remainder when $x^{60}-1$ is divided by $x^3-2$.
My intuition is that this expression can be written as $a^n-\frac{b^m}{a}-b$. However, I tried a bunch of ways and I haven't been able to factor the numerator into that form.
This is from an olympiad problem book on Higher Algebra.
Answer
We can use the remainder theorem. The outcome of dividing the polynomial $p(x)$ by another polynomial $d(x)$ is essentially an equation $$p(x)=q(x)d(x)+r(x)$$where the degree of $r(x)$ is less than the degree of $d(x)$.
Suppose $d(a)=0$. It follows that $p(a)=r(a)$. So one can reconstruct $r(x)$ by evaluating $p(x)$ at the roots of $d(x)=0$ (with an additional twist if there are multiple roots).
Here, setting $y=x^3$ we can simplify considerably by using $p(y)=y^{20}-1$, $d(y)=y-2$ and then degree $(r)\lt 1$ so $r$ must be a scalar.
We obtain $r=p(2)=2^{20}-1$
I mentioned reconstructing a remainder which is not a scalar above, because not everyone realises the remainder theorem can be used in this way, and these kinds of remainder questions have occurred in competition problem sets.
No comments:
Post a Comment