Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How to find the remainder for :

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

divided by :

$$x^3-x$$

share|cite|improve this question
up vote 3 down vote accepted

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$.

share|cite|improve this answer
    
could the first method always be applied in cases of synthetic division? – AlanH Mar 25 '13 at 6:20
1  
@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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.