Proof of polynomial divisibility without using complex numbers?

Question

My question is the same as polynomial of degree n and its divisor except I want a solution that does not make use of complex numbers

Problem: Find all positive integers $n$ such that $x^2+x+1\mid (x+1)^n+x^n+1$

Using wolframalpha, I can see that a number of solutions work, such as $2,4,7$. I tried substituting various values of $x$ in and then working in specific mod cases, but this doesn't really seem to work because it only gives possible values, not 'actual' values. Polynomial long division here is also quite unwieldy...

Answer 1

Since $$(x+1)^6\equiv 1\mod (x^2+x+1)$$ and $$x^6\equiv 1\mod (x^2+x+1)$$ the exponent $n$ can be reduced modulo $6$. Inspection gives the solutions $2$ and $4$ in the interval $[1,6]$, hence the condition is satisfied if and only if $n\equiv \pm2\mod 6$. So exactly the even exponents $n$ not divisible by $3$ do the job.

Answer 2

You can use a form of polynomial modular arithmetic here, working modulo $x^2+x+1$

We have $x^2+x+1\equiv 0$ so that $x+1\equiv -x^2$

also $x^3+x^2+x\equiv 0$ so that $x^3\equiv -x^2-x\equiv 1$

So $p_n(x)=(x+1)^n+x^n+1\equiv (-1)^nx^{2n}+x^n+1$

Now since $x^3\equiv 1$ and you have a $(-1)^n$ there you can work modulo $6$, because extra multiples of $6$ in the powers change nothing.

We have $$p_0(x)\equiv 3$$ $$p_1(x)\equiv -x^2+x+1\equiv 2x+2$$$$p_2(x)\equiv x^4+x^2+1\equiv x+x^2+1\equiv 0$$$$p_3(x)\equiv -x^6+x^3+1\equiv 1$$$$p_4(x)\equiv x^8+x^4+1\equiv x^2+x+1\equiv 0$$$$p_5(x)=-x^{10}+x^5+1\equiv-x+x^2+1\equiv-2x$$

So the division works for $n\equiv 2,4 \bmod 6$ and you have the remainders on polynomial division for the other residue classes.

---

Note that because $x^2+x+1$ is an irreducible polynomial, this method is algebraically equivalent to replacing $x$ by a root of the equation $x^2+x+1$, but the computations all take place in a polynomial ring which isn't identified with any particular known ring or field.

Answer 3

First I will prove that: $$n \in \{2,4\} \pmod{6}$$ is a necessary condition:

Just substitute x for the value 2 so that the equation results:

$$7 | 3 ^ n + 2 ^ n + 1$$

$$3 ^ n + 2 ^ n + 1 \equiv 0 \pmod{7}$$

whose all solutions are: $$n \in \{2,4\} \pmod{6}$$

Now I am going to prove that these two conditions are sufficient:

As mentioned above: $$ P = x^2+x+1 $$ $$(x + 1) ^ 6 \equiv 1 \pmod{P}$$

$$x ^ 6 = 1 \pmod{P}$$

If $n \equiv 2 \pmod {6}$:

$$(x + 1) ^ {6a+2} + x ^ {6a+2} + 1 \pmod{P}$$ $$(x + 1) ^ {6a} (x ^ 2 + 2x + 1) + x ^ {6a} x ^ 2 + 1 \pmod{P}$$ $$(P + x) + x ^ 2 + 1 \pmod{P}$$ $$P + x + x ^ 2 +1 \pmod{P}$$ $$2P \pmod{P}$$ $$ 0 \pmod{P} $$

With which is a sufficient condition.

If $n \equiv 4 \pmod {6}$:

$$(x + 1) ^ {6a+4} + x ^ {6a+4} + 1 \pmod{P}$$ $$(x + 1) ^ {6a} (x ^ 4 + 4x ^ 3 + 6x ^ 2 + 4x + 1) + x ^ {6a} x ^ 4 + 1 \pmod{P}$$ $$(x ^ 4 + 4x ^ 3 + 6x ^ 2 + 4x + 1) + x ^ 4 + 1 \pmod{P}$$ $$2x^4 +4x^3+6x ^ 2 + 4x + 2 \pmod{P}$$ $$2(x^2+x+1)^2 \pmod{P}$$ $$ 0 \pmod{P} $$

With which is a sufficient condition.

It is proved that the condition is necessary and sufficient.