Find sum of all natural numbers $n $ such that $(n^2+n+1)^2$ divides $1+n+n^2+...+n^{2195}$.

Question

Update

Find sum of all $n \in \mathbb{N}$ such that $(n^2+n+1)^2$ divides $n^{2195}+n^{2194}+...+n^2+n+1$.

I have no idea. Can anyone help? At least with a hint. Thanks for the help in advance.

---

Original Question (Before Correction)

Find sum of all natural numbers $n $ such that $n^2+n+1$ divides $1+n+n^2+...+n^{2195}$.

Answer 1

$$n^{2193}+n^{2190}+\cdots+1 = n^{2193}-1+n^{2190}-1+\cdots+1-1+732$$ The left-hand side is the result of dividing by the first factor of $n^2+n+1$. The $n^{3k}-1$ are each multiples of the second factor of $n^2+n+1$, leaving $732$ alone.
$n^2+n+1$ is odd, and odd factors of 732 are $1,3,61,183$.
$$1=0^2+0+1\\3=1^2+1+1\\183=13^2+13+1$$

Answer 2

Here's hint: this sum is equal to $$\frac{n^{2196}-1}{n-1}=\frac{\bigl(n^3\bigr)^{732}-1}{n-1}=\dotsm$$

Answer 3

As Gerry Myerson has stated in the comments, it just might be helpful. The underlying fact is that it's still divisible nevertheless. Watch this.

Say $n^3-1=k$. Then we want to evaluate $(n^{2196}-1) \bmod k$

$n^3=k+1$

$\begin{align} (n^3)^{732}-1 &= (k+1)^{732}-1 \\ &\equiv 1-1 \pmod{k} \\ &\equiv 0 \pmod{k} \end{align}$

So it is divisible for all $n \in \Bbb N$, which by the factoring idea I presented in the comments still holds.

Edit: Let's try out the case I've been presented with: the big polynomial versus $(n^2+n+1)^2$

So the polynomial can be factored into:

$(n^2+n+1)\color{red}{(1+n^3+n^6+n^9+\ldots+n^{2193})}$

So the question now really is how the red factor can be divided by $n^2+n+1$. It's value is:

$\begin{align}S&=1+\color{blue}{n^3+n^6+n^9 \ldots n^{2193}} \\ n^3 S&=\color{blue}{n^3+n^6 \ldots n^{2193}} + n^{2196} \\ n^3 S - S&= n^{2196}-1 \\ S&=\dfrac{n^{2196}-1}{n^3-1} \end{align}$

So what we're checking for is:

$\dfrac{\dfrac{n^{2196}-1}{n^3-1}}{\dfrac{n^3-1}{n-1}}=\dfrac{(n-1)(n^{2196}-1)}{(n^3-1)^2}$

And since:

$n^{2196}-1=(n^3-1)\color{red}{(n^{2193}+n^{2190} \ldots 1)}$

So what we're looking at now is the red sum versus $n^3-1$. Doing the same thing as before with $n^3=k+1$:

$=(n^3)^{731}+(n^3)^{730}+(n^3)^{729} \ldots n^3+1$

$=(k+1)^{731}+(k+1)^{730} \ldots (k+1)+1$

$\equiv 732 \pmod k$

So $(n^3-1)$ must divide $732$ meaning that one of it's factors should be one less than a perfect cube.

Factors of $732$ plus one are:

$\{2,3,5,7,12,62,123,184,245,367,733\}$

None of them are perfect cubes so you can conclude the only solutions are the trivial ones which are $0$ and $1$.