Remainders Are Fun 2

Algebra Level 4

Find the remainder when the polynomial $\displaystyle \large \sum_{n = 1}^{672} x^{3n}$ is divided by the polynomial $\displaystyle \large\sum_{n = 0}^2 x^n \ ?$

For more problems like this, try answering this set .

The answer is 672.

1 solution

Christian Daang
Feb 21, 2017

By Remainder Theorem ,
$\displaystyle \large \begin{aligned} \sum_{n = 0}^2 x^n = 0 \Longleftrightarrow (x - 1) \left( \sum_{n = 0}^2 x^n \right ) = 0 \Longleftrightarrow x^3 = 1 \\ \text{Since} \ (x^3 - 1) \mod \left( \sum_{n = 0}^2 x^n \right ) \equiv 0 \implies x^3 \mod \left( \sum_{n = 0}^2 x^n \right ) \equiv 1 \ \text{and hence,} \ x^{3n} \mod \left( \sum_{n = 0}^2 x^n \right ) \equiv 1 \\ \implies \sum_{n = 1}^{672} x^{3n} \mod \left( \sum_{n = 0}^2 x^n \right ) & \equiv \sum_{n = 1}^{672} 1 \mod \left( \sum_{n = 0}^2 x^n \right ) \\ & \equiv 672 \mod \left( \sum_{n = 0}^2 x^n \right ) \\ & = \boxed{672} \end{aligned}$

While the answer is correct, the solution makes a lot of errors with modular arithmetic.

I have no idea what your solution is expressing. To calculate $\pmod {x^2 + x + 1}$ , you seem to be sayig that we can calculate $\pmod{ x^3 }$ . Specifically, the only evidence that you seem to have for $x^{3n} \equiv 1 \mod { x^2 + x + 1 }$ , is to say that $x^{3n} \equiv 0 \pmod{x^3}$ .

Calvin Lin Staff - 4 years, 3 months ago

Sir, I already edited my solution. :D

Christian Daang - 4 years, 3 months ago

Looks better. I would advice you to write $1 + x + x^2$ instead of that summation sign. This makes it unnecessarily harder to read, as one then has to actively track what the summation is until.

Calvin Lin Staff - 4 years, 3 months ago

Remainders Are Fun 2

The answer is 672.

1 solution

0 pending reports