# Thread: Polynomial problem

1. ## Polynomial problem

Find all natural numbers n such that

xn +(x+1)n+1 is divisible by (1+x+x2)2.

Any ideas, anyone?

2. ## Re: Polynomial problem

Let $p(x)=x^n+(x+1)^n+1$

and $\alpha =-\frac{1}{2}+i\frac{ \sqrt{3}}{2}$

$\alpha$ is a double root of $p(x)$

Therefore $p(\alpha )=0$ and $p'(\alpha )=0$

3. ## Re: Polynomial problem

Example: x = 3, n = 4

4. ## Re: Polynomial problem

I used www.quickmath.com

I noticed for these n-values (but did not check further) that it is divisible:

4, 16, 28, 40, 52, 64, 76 =

4(1, 4, 7, 10, 13, 16, 19)

It did not work for several values of n in between that I tried.

If it holds up, then n = 4(3t - 2), $\ for \ \ t \ge 1, \ \$ where t is an integer.

Or, n = 12t - 8.

5. ## Re: Polynomial problem

If $x^n+ (x+1)^n+1$ is divisible by $\left(1+x+x^2\right)^2$ then

$n=6k+4$ for $k\geq 0$

Proof: Replace $x=1$ to show that $2^n+2$ must be divisible by $9$

Let $n=6 k+r$ where $0\leq r <6$

This implies $2^r+2$ divisible by $9$ and $r=4$

6. ## Re: Polynomial problem

Originally Posted by Idea

Proof: Replace $x=1$ to show that $2^n+2$ must be divisible by $9$
You've replaced x with only 1. x could be any positive integer (in fact it could conceivably be any negative integer or positive integer),
and it could conceivably equal zero as long as n is never allowed to equal 0.

What about the other x-values?

7. ## Re: Polynomial problem

yes, you could replace x with other integers and get a possibly different set of values for n

8. ## Re: Polynomial problem

Obviously, we need n congruent to 4 (mod 6) by what Idea showed. But, we don't know if n=6k+4 for all k.
So, let's look at residue classes:
$x^4+(x+1)^4+1 = 2(1+x+x^2)^2 + 0$
$x^{10}+(x+1)^{10}+1 = (2x^6+6x^5+27x^4+44x^3+27x^2+6x+2)(1+x+x^2)^2+0$
$x^{16}+(x+1)^{16}+1 = 2 (x^{12} + 6 x^{11} + 45 x^{10} + 170 x^9 + 422 x^8 + 734 x^7 + 885 x^6 + 734 x^5 + 422 x^4 + 170 x^3 + 45 x^2 + 6 x + 1)(1+x+x^2)^2+0$
$x^{22}+(x+1)^{22}+1 = (2 x^{18} + 18 x^{17} + 189 x^{16} + 1104 x^{15} + 4502 x^{14} + 13622 x^{13} + 31466 x^{12} + 56638 x^{11} + 80350 x^{10} + 90252 x^9 + 80350 x^8 + 56638 x^7 + 31466 x^6 + 13622 x^5 + 4502 x^4 + 1104 x^3 + 189 x^2 + 18 x + 2)(1+x+x^2)^2+0$

Seems like Idea is correct. So, let's test Idea's idea further.:

$p(x) = x^{6k+4}+(x+1)^{6k+4}+1$
$p'(x) = (6k+4)x^{6k+3}+(6k+4)(x+1)^{6k+3}$

For $\alpha = \dfrac{-1+i\sqrt{3}}{2}$:
We want
$p(\alpha) = 0, p'(\alpha) = 0$

Now, you can verify $\alpha^4 = \alpha$. $\alpha^6=1$, $(\alpha+1)^6 = 1$, and $(\alpha+1)^4 = -(\alpha+1)$.

So, we have:
$\alpha^{6k+4}+(\alpha+1)^{6k+4}+1 = \left(\alpha^6\right)^k\cdot \alpha^4+\left((\alpha+1)^6\right)^k\cdot (\alpha+1)^4+1 = \alpha -(\alpha+1)+1 = 0$ checks out.

Next, we have:
$(6k+4)\left(\alpha^{6k+3}+(\alpha+1)^{6k+3}\right ) = (6k+4)(1-1) = 0$

So, this shows that $\alpha$ is a double root for any $n=6k+4$.

This should conclude the proof.