1
$\begingroup$

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

$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ankesh
    Oct 8 '13 at 6:52
  • 1
    $\begingroup$ What degree will the remainder be? And how can you evaluate the remainder at an appropriate set of points? $\endgroup$
    – copper.hat
    Oct 8 '13 at 6:54
  • $\begingroup$ 0 degree. it will be a constant. $\endgroup$
    – Ankesh
    Oct 8 '13 at 6:55
  • 1
    $\begingroup$ If you are familiar with complex numbers, evaluate at the cube roots of unity $\frac{-1\pm\sqrt{-3}}{2}$. $\endgroup$ Oct 8 '13 at 7:03
  • $\begingroup$ And note that $276 = 0 \mod 3$. $\endgroup$
    – copper.hat
    Oct 8 '13 at 7:06
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Fine. Up Vote $0 $ k. $\endgroup$ Oct 8 '13 at 7:22
2
$\begingroup$

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

$\endgroup$
0
1
$\begingroup$

Hint: Set $y=x^3$ and at first find the remainder for $y^{92}+12$ divided by $y-1$.

$\endgroup$
2
  • $\begingroup$ how the denominator converted to y-1? $\endgroup$
    – Ankesh
    Oct 8 '13 at 7:15
  • $\begingroup$ 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$. $\endgroup$ Oct 8 '13 at 9:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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