2

Problem:

Show that $x^3+x^2+x+1 \mid x^{4m+3}+x^{4n+2}+x^{4q+1}+x^{4s}$ in $\Bbb Z[x]$ for all $m,n,q,s$ nonnegative integers

So my algebra sucks.

I'm reviewing some algebra and found this problem. I was able to play with it and get a trivial solution that I'm sure is missing the point of the problem.

My (dumb) solution:

We prove by induction.

For $m=n=q=s=0$ we have that $x^3+x^2+x+1 \mid x^3+x^2+x+1$.

Now assume $x^{4m+3}+x^{4n+2}+x^{4q+1}+x^{4s}=p(x)(x^3+x^2+x+1)$.

Then: $$(p(x)+x^{4m+3}(x-1))(x^3+x^2+x+1)=x^{4(m+1)+3}+x^{4n+2}+x^{4q+1}+x^{4s}$$ $$(p(x)+x^{4n+2}(x-1))(x^3+x^2+x+1)=x^{4m+3}+x^{4(n+1)+2}+x^{4q+1}+x^{4s}$$ $$(p(x)+x^{4q+1}(x-1))(x^3+x^2+x+1)=x^{4m+3}+x^{4n+2}+x^{4(q+1)+1}+x^{4s}$$ $$(p(x)+x^{4s}(x-1))(x^3+x^2+x+1)=x^{4m+3}+x^{4n+2}+x^{4q+1}+x^{4(s+1)}$$

However this is very unenlightening. What is the point of the problem? Is there more enlightening solution?

Community
  • 1
  • 1
    Outline of another approach: observe that $x^{4m+3} \equiv x^3 \pmod{x^4 - 1}$, and similarly for the other terms. Then use that $x^3 + x^2 + x + 1 \mid x^4 - 1$. – Daniel Schepler Dec 18 '17 at 22:49
  • Will's way is nice. I would have done it as follows. That cubic is a factor of $x^4-1$. The remainder of $x^{4m+3}$ modulo $x^4-1$ is $x^3$ (do you see why?). Similarly for the other terms. Conclusion: the remainder of that high degree polynomial modulo $x^4-1$ is $x^3+x^2+x+1$. The claim follows. See here for Bill Dubuque's explanation of a similar result about divisibility by $x^2+x+1$. – Jyrki Lahtonen Dec 18 '17 at 22:51
  • @JyrkiLahtonen $x^4-1\equiv 0$ so $x^4 \equiv 1$ so $x^{4m}\equiv 1$ so $x^{4m+3}\equiv x^3$ (all mod $x^4-1$). I follow this solution (and it's perhaps similar in spirit to mine, just a little simpler thank you). –  Dec 18 '17 at 23:06

2 Answers2

3

$i,-1,-i$ are all roots of your polynomial. It is divisible by $(x-i)(x+1)(x+i)=x^3 + x^2 + x + 1.$ I suppose I should add that it is so divisible in $\mathbb Q [x],$ while Gauss theorem on content says it is then divisible in $\mathbb Z [x] \; .$

Will Jagy
  • 139,541
-1

The algebraic answer by @Will Jagy is excellent (of course). I'll add a naive solution by induction, especially that induction was mentioned in the OP post.

Let's do induction over $\ E\ := m+n+q+s,\ $ where $\ m\ n\ q\ s\ $ are arbitrary non-negative integers (see the OP post). The theorem holds for $\ E=0.\ $ Now, assume that $\ E>0.\ $ Then there exists a non-negative integer $\ t\ $ and $\ r\in\{0\ 1\ 2\ 3\}\ $ such that $\ x^{4\cdot(t+1)+r}\ $ is one of the four summands of $\ g(x)\ :=\ x^{4\cdot m+3} + x^{4\cdot n+2} + x^{4\cdot q+1} + x^{4\cdot s}. $ Define polynomial $\ f\ $ obtained by replacing the said summand by monomial $\ x^{4\cdot t+r}.\ $ Then

$$ g(x) - f(x) = (x^4-1)\cdot x^{4\cdot t+r} $$

Thus, polynomial $\ x^3+x^2+x^1+1\ $ divides $\ g-f,\ $ and it divides $\ f\ $ by induction, hence it divides $\ g.\ $ END of (inductive) proof

EDIT Actually, I've virtually rewritten the OP's solution. I think that it is as good as any. I'll keep this version here too since it may be clearer this way when you have both of these renditions.
Wlod AA
  • 2,124