1
$\begingroup$

Let $R(x)$ be a remainder upon dividing $x^{44}+x^{33}+x^{22}+x^{11} +1$ by the polynomial $x^4 +x^3 +x^2 +x +1$. Find: $R(1)+2R(2)+3R(3)$. Answer provided is $0$

$\endgroup$

closed as off-topic by user26857, Claude Leibovici, user91500, user1551, user223391 Jul 21 '16 at 4:45

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – user26857, Claude Leibovici, user91500, user1551, Community
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ @JohnHughes I can't think how to deal with such a higher degrees. $\endgroup$ – mnulb Jul 11 '16 at 16:34
  • $\begingroup$ Why would the degree pose a problem? $\endgroup$ – Henrik Jul 17 '16 at 11:45
11
$\begingroup$

Hint \begin{align} & {{x}^{55}}-1=({{x}^{11}}-1)({{x}^{44}}+{{x}^{33}}+{{x}^{22}}+{{x}^{11}}+1) \\ & {{x}^{5}}-1=(x-1)({{x}^{4}}+{{x}^{3}}+{{x}^{2}}+{{x}^{1}}+1) \\ \end{align} $$\frac{{{x}^{44}}+{{x}^{33}}+{{x}^{22}}+{{x}^{11}}+1}{{{x}^{4}}+{{x}^{3}}+{{x}^{2}}+{{x}^{1}}+1}=\frac{{{x}^{55}}-1}{{{x}^{5}}-1}\times \frac{(x-1)}{({{x}^{11}}-1)}$$

$\endgroup$
  • $\begingroup$ Doesn't this mean the OP's expression is $0$? $\endgroup$ – Jack Lam Jul 11 '16 at 16:42
  • $\begingroup$ @BehrouzMaleki, Would you mind adding a few steps more $\endgroup$ – lab bhattacharjee Jul 11 '16 at 16:45
  • 1
    $\begingroup$ ya, please add some more steps, please. $\endgroup$ – mnulb Jul 11 '16 at 16:48
  • 1
    $\begingroup$ Good job, Behrouz! @labbhattacharjee This is the formula for the cyclotomic polynomial $\Phi_{55}(x)$. $\endgroup$ – Jyrki Lahtonen Jul 11 '16 at 19:46
  • $\begingroup$ So Thanks @ Jyrki Lahtonen $\endgroup$ – Behrouz Maleki Jul 11 '16 at 19:49
5
$\begingroup$

$$x^{44}+x^{33}+x^{22}+x^{11}+1=\frac{x^{55}-1}{x^{11}-1}=\frac{(x^5-1)\sum_{k=0}^{10}x^{5k}}{x^{11}-1}\\=\frac{x^5-1}{x-1}\cdot\frac{\sum_{k=0}^{10}x^{5k}}{\sum_{k=0}^{10}x^k}=(x^4+x^3+x^2+x+1)\cdot\color{blue}{\frac{\sum_{k=0}^{10}x^{5k}}{\sum_{k=0}^{10}x^k}}$$

The blue fraction is actually a polynomial because the only eleventh root of $1$ which is also a fifth root of $1$ is $1$ itself. Or, if you prefer, because $\operatorname{gcd}(x^{11}-1,x^5-1)$ is obviously $x-1$.

$\endgroup$
4
$\begingroup$

The thing that makes this easy is $x^4 + x^3 + x^2 + x + 1$ divides $x^5 - 1$. Thus, if $$\begin{align} f(x) &\equiv g(x) & &\pmod{x^5 - 1} \\ g(x) &\equiv h(x) & &\pmod{x^4 + x^3 + x^2 + x + 1} \end{align}$$ then $$ f(x) \equiv h(x) \pmod{x^4 + x^3 + x^2 + x + 1} $$ and it's easy to find a low degree $g(x)$ to use as the intermediate, since $x^5 \equiv 1 \pmod{x^5-1}$.


But even without that, you can use the usual tricks for modular arithmetic; e.g. some of the content of How do I compute $a^b\,\bmod c$ by hand? applies here too.

$\endgroup$
3
$\begingroup$

Hint $\,\ (x\!-\!1)f\, =\, x^{\large 5}-1\,\ $ for $\,\ f =\, x^{\large 4}+x^{\large 3}+\cdots+1,\,\ $ therefore

$\qquad\quad \begin{eqnarray}{\rm mod}\ f\!:\,\ x^{\large \color{#c00}5}\equiv 1\ \Rightarrow\ &&x^{\large 4+\color{#c00}5I}+\!&&x^{\large 3+\color{#c00}5J}+\!&&x^{\large 2+\color{#c00}5K}+\!&&x^{\large 1+\color{#c00}5L}+\!&&x^{\large\color{#c00} 5M}\\ \equiv\,\ &&x^{\large 4}\quad + &&x^{\large 3}\quad + &&x^{\large 2} \quad + &&x\quad\ + &&1\,\equiv\, f\,\equiv\, 0\end{eqnarray}$

$\endgroup$
  • $\begingroup$ Above we used five times that $\ x^{\large A + \color{#c00}5B} = x^{\large A} (x^{\large \color{#c00}5})^{\large B}\equiv x^{\large A}(1^{\large B})\equiv x^{\large A}.\ $ Note that this method requires no knowledge of any special factorization formulas (except $\,(x\!-\!1)f = x^5-1),\,$ so it will work much more generally. $\endgroup$ – Bill Dubuque Jul 11 '16 at 22:42
3
$\begingroup$

Long division of $x^{44}+x^{33}+x^{22}+x^{11}+1$ by $x^4+x^3+x^2+x+1$ gives a quotient of $$ x^{40}-x^{39}+x^{35}-x^{34}+x^{30}-x^{28}+x^{25}-x^{23}+x^{20}-x^{17}+x^{15}-x^{12}+x^{10}-x^{6}+x^{5}-x+1$$ and no remainder. It is not a lot of work: only five lines.

$\endgroup$

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