The question is:

Find a remainder when $f(x)=(x^5+1)^{100} + (x^5-1)^{100}$ is divided by $x^4+x^2+1$

I first began by decomposing $$x^4+x^2+1=(x^2+x+1)(x^2-x+1)$$ and using $$x^3-1=(x-1)(x^2+x+1)\\x^3+1=(x+1)(x^2-x+1)$$

and could get remainders when divided by each factors. \begin{align} (x^5+1)^{100}&\equiv(x^2+1)^{100}&(\mathrm{mod}\,x^3-1)\\ &\equiv(-x)^{100}&(\mathrm{mod}\,x^2+x+1)\\ &=x^{100}=x\cdot(x^3)^{33}\\ &\equiv x&(\mathrm{mod}\,x^3-1)\\\\ (x^5-1)^{100}&\equiv(x^2-1)^{100}&(\mathrm{mod}\,x^3-1)\\ &=(x+1)^{100}(x-1)^{100}\\ &=(x^2+x+1+x)^{50}\cdot(x^2+x+1-3x)^{50}\\ &\equiv x^{50}\cdot(-3x)^{50}&(\mathrm{mod}\,x^2+x+1)\\ &=3^{50}(x^2)^{50}=3^{50}x\cdot(x^3)^{33}\\ &\equiv 3^{50}x&(\mathrm{mod}\,x^3-1)\\ \end{align} Therefore $$f(x)\equiv (3^{50}+1)x\quad(\mathrm{mod}\,x^2+x+1)\\$$ Similarly, $$f(x)\equiv -(3^{50}+1)x\quad(\mathrm{mod}\,x^2-x+1)\\$$ So \begin{align} f(x) &= (x²+x+1)p(x) + (3^{50}+1)x\\ f(x) &= (x²-x+1)q(x) - (3^{50}+1)x \end{align} As $f(x)$ is an even function, I could derive that $$q(x)=p(-x)$$ And then, my plan was to find a remainder when $p(x)$ is devided by $x²-x+1$ and so on \begin{align} p(x)&=(x²-x+1)A(x)+Cx+D\\ q(x)&=(x²+x+1)B(x)+Ex+F\\ \end{align} So that I could conclude that $$f(x)\equiv (x^2+x+1)(Cx+D)+(3^{50}+1)x\quad(\mathrm{mod}\,x^4+x^2+1)\\$$ Using $p(x)=q(-x)$, I could derive that $A(x)=B(-x)$, $C=-E$, and $D=F$. And further using $f(x)=f(-x)$, I could do \begin{align} p(x)&=e(x)+o(x)\quad(e(x)=e(-x)\,,o(x)=-o(-x))\\ \rightarrow&(x²+x+1)(e(x)+o(x)) + (3^{50}+1)x = (x²-x+1)(e(x)-o(x)) - (3^{50}+1)x\\ \rightarrow&2xe(x)+(x²+1)o(x) + 2(3^{50}+1)x = 0\\ p(x)&=\frac{(-x²+2x-1)o(x)}{2x} - (3^{50}+1) = \frac{(-x²+x-1 + x)o(x)}{2x} - (3^{50}+1)\\ &= \frac{(-x²+x-1)o(x)}{2x} + \frac{o(x)}2 - (3^{50}+1) \end{align} And that was it. I couldn't proceed further.


Therefore, $ $ with $\,n = 3^{50}\!+1$
$$\begin{align} &f(x)\,\equiv\ \ \ n\,\color{#c00}x\quad(\mathrm{mod}\ \ x^2\!+\!x\!+\!1)\\[.2em] &f(x)\,\equiv -n\,\color{#0a0}x\quad(\mathrm{mod}\ \ x^2\!-\!x\!+\!1)\end{align}\qquad\qquad$$

Hint: make the following substitutions $$\begin{align}\color{#c00}x &\equiv -(x^2\!+\!1)\!\pmod{x^2\!+\!x\!+\!1}\\ \color{#0a0}x&\equiv \ \ \ \ \ x^2\!+\!1\,\pmod{x^2\!-\!x\!+\!1} \end{align}$$

which yields that $\, f\equiv -n(x^2\!+\!1)\,$ mod both, so also mod their lcm = product. QED $ $ Good work.

  • 1
    $\begingroup$ The "hence" is by lcm or CCRT = Constant-case CRT as described here. $\endgroup$ – Bill Dubuque Apr 19 at 22:34
  • $\begingroup$ Thank you. That completes the last piece. I appreciate. $\endgroup$ – Kay K. Apr 19 at 22:49

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.