# Finding the remainder

How to find the remainder for :

$$x^{81}+x^{49}+x^{25}+x^{9}+x$$

divided by :

$$x^3-x$$

-

Modular arithmetic is your friend here. You are seeking a polynomial $f(x)$ of degree less than $3$ such that

$$x^{81}+x^{49}+x^{25}+x^{9}+x \equiv f(x) \pmod{x^3 - x}$$

By applying the identity

$$x^3 \equiv x \pmod{x^3 - x}$$

it becomes a nearly trivial matter to simplify any polynomial. For example,

$$x^8 = x^3 \cdot x^5 \equiv x \cdot x^5 = x^6 = \cdots \equiv x^2 \pmod{x^3 - x}$$

A variation that is sometimes useful is to use the Chinese Remainder Theorem. Factoring the modulus into linear terms using the complex numbers gives

$$x^3 - x= x(x-1)(x+1)$$

(ah, we were able to get away with just integers). If you can find

$$x^{81}+x^{49}+x^{25}+x^{9}+x \equiv a \pmod{x}$$ $$x^{81}+x^{49}+x^{25}+x^{9}+x \equiv b \pmod{x - 1}$$ $$x^{81}+x^{49}+x^{25}+x^{9}+x \equiv c \pmod{x + 1}$$

you could use the Chinese Remainder theorem to piece together these simplifications to get a value modulo $x^3-x$.

-
could the first method always be applied in cases of synthetic division? –  AlanH Mar 25 '13 at 6:20
@AlanH: The use of modular arithmetic? Yes. The observation that makes the problem very easy? No; that's limited specifically to binomials. Sometimes other special forms come up that are easy as well. Arguably, the problem is already in one of those special forms even if the modulus had more terms, since you could use square-and-multiply tricks to perform modular exponentiation relatively quickly. –  Hurkyl Mar 25 '13 at 6:25

Both have a factor of $x$, yes? So $$\frac{x^{81}+x^{49}+x^{25}+x^9+x}{x^3-x}=\frac{x^{80}+x^{48}+x^{24}+x^8+1}{x^2-1}.$$ Now make the substitution $u=x^2$ to get $$\frac{u^{40}+u^{24}+u^{12}+u^4+1}{u-1},$$ and use remainder theorem.

-

the remainder should the the form of $ax^{2}+bx+c$. so, $x^{81}+x^{49}+x^{25}+x^{9}+x=Q(x)(x^3-x)+ax^2+bx+c$ and insert x=0,1,-1 so that you can find a,b,c.

-