Find remainder when $F(x)$ is divided by $P(x)$

Find the remainder when $F(x)=x^{276}+12$ is divided by $P(x)=x^2+x+1$?

• i tried making the P(x) as x^3-1 by multiplying the numerator as well as denominator by x-1 so that i can put x=1 in new F(x) to get remainder but that is not the answer as it will be reduced to zero if i multiplied by factor. Oct 8 '13 at 6:52
• What degree will the remainder be? And how can you evaluate the remainder at an appropriate set of points? Oct 8 '13 at 6:54
• 0 degree. it will be a constant. Oct 8 '13 at 6:55
• If you are familiar with complex numbers, evaluate at the cube roots of unity $\frac{-1\pm\sqrt{-3}}{2}$. Oct 8 '13 at 7:03
• And note that $276 = 0 \mod 3$. Oct 8 '13 at 7:06

You have $F(x) = (x^2+x+1) q(x) + r(x) = \frac{x^3-1}{x-1} q(x) + r(x)$, with $\partial r <2$. Let $x$ be a cube root of $1$ different from $1$, then $F(x) = r(x)$, and since $276 = 0 \mod 3$, we have $x^{276} = 1$, and so $F(x) = 13$ at both 'non one' roots.
Hence $r(x) = 13$.
• Fine. Up Vote $0$ k. Oct 8 '13 at 7:22
You should use the fact that remainder of a sum is the sum of remainders and the remainder of the product is the remainder of the product of remainders. In other words, the operations in the quotient ring are well defined. Or with congruences: $$\begin{array}{rrcr} &x^3&\equiv&1 \pmod{x^2+x+1}\\ \implies&(x^3)^{92}&\equiv&1^{92}\pmod{x^2+x+1}\\ \implies&x^{276}&\equiv&1\pmod{x^2+x+1}. \end{array}$$ If the language of congruences is not clear to you, then first prove that $x^3-1$ divides $(x^3)^{92}-1$.
Hint: Set $y=x^3$ and at first find the remainder for $y^{92}+12$ divided by $y-1$.
• It is not converted. We get the remainder $1^{92}+12$ (little Bézout's theorem), so $x^{276}+12=g(x)(x^3-1)+13$. Oct 8 '13 at 9:13