Take the 2-minute tour ×
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.

How to find the remainder for :

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

divided by :

$$x^3-x$$

share|improve this question
    
Since you are new, I want to give some advice about the site: To get the best possible answers, you should explain what your thoughts on the problem are so far. That way, people won't tell you things you already know, and they can write answers at an appropriate level; also, people tend to be more willing to help you if you show that you've tried the problem yourself. If this is homework, please add the [homework] tag; people will still help, so don't worry. –  Stahl Mar 27 '13 at 23:20

3 Answers 3

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