Does $(x^2+xy+y^2)$ divide $(x+y)^n-x^n-y^n$ if and only if n has no prime factors less than 5 I noticed that for $n$ with prime factors greater than 5, that $xy(x+y)(x^2+xy+y^2)$ always seems to divide $(x+y)^n-x^n-y^n$. The $xy(x+y)$ factors seem fairly obvious, but I can't figure out where the $x^2+xy+y^2$ term comes from. Strangely, if $n$ is congruent to 6 mod 1, then $(x^2+xy+y^2)^2$ seems to divide $(x+y)^n-x^n-y^n$.
Is this true for all $n$ as specified? Is the converse true, i.e. if $x^2+xy+y^2$ divides $(x+y)^n-x^n-y^n$ then $n$ has no prime factors less than 5, and if $(x^2+xy+y^2)^2$ divides $(x+y)^n-x^n-y^n$, then n is congruent to 1 mod 6?
 A: By homogeneity, it’s enough to show that $x^2+x+1$ divides $(x+1)^n-x^n-1$. Because these polynomials are rational and $x^2+x+1$ is irreducible over $\mathbb{Q}$, it’s enough to show that $(j+1)^n-j^n-1=0$, where $j=e^{2i\pi/3}$ is a primitive third root of unity.
Now, $(j+1)^n-j^n-1=(-j^2)^n-j^n-1=-(1+j^n+j^{2n})$. Now, $3$ doesn’t divide $n$ so $j^n \in \{j,j^2\}$ and both of these elements are roots of $X^2+X+1$.
By the same reasoning, $(x^2+xy+y^2)^2|(x+y)^n-x^n-y^n$ iff $x^2+x+1$ divides the derivative $D$ of $(x+1)^n-x^n-1$, iff $D(j)=0$.
But $D(X)=n((X+1)^{n-1}-X^{n-1})$, so $D(j)=0$ iff $(j+1)^{n-1}=j^{n-1}$ iff $(-j^2)^{n-1}=j^{n-1}$ iff ($n$ is odd) $j^{2n-2}=j^{n-1}$ iff $3|n-1$, so iff $6|n-1$.
A: Here is an alternative direct approach, an induction with step six, and the "small cases" of $n$ among $0,1,2,3,4,5$ are easily checked. (We already have a quick, good, compact answer by Aphelli - i just wanted to see if an arguably more elementary proof avoiding complex numbers and derivatives can be worked out. The answer was started long time ago, at some firefox update i was asked if i really want to leave the page...)

We de-homogenize the situation, and replace at all places $y$ by $1$.
Alternatively, divide by $y^n$ and use $X=x/y$.
(It is enough to clear the question(s) for this special value of $y$.)
Let $F$ be the polynomial $X^2 + X + 1$. We will work in the rings $R_1=\Bbb Q[X]/(F)$ of polynomials taken modulo $F$, and in $R_2=\Bbb Q[X]/(F^2)$ of polynomials taken modulo $F^2$.
Notation:  $P(n) = (X+1)^n - X^n - 1$.
Let us show the following:

$P(n)$ is divisible by $F$, iff $n$ is $\pm1$ modulo six.
$P(n)$ is divisible by $F^2$, iff $n$ is $1$ modulo six.

For small values of $n$ the divisibility (with $F$, and in the positive case with $F^2$) is easily checked:
$$
\begin{aligned}
(X+1)^3 &\equiv -1 \equiv X^3 && &&\text{ modulo }F\\[2mm]
P(0) &=1+1-1&&\ne0 &&\text{ modulo }F\\
P(1) &=0&&=\color{blue}{0} &&\text{ modulo }F\\
P(2) &=2x&&\ne0 &&\text{ modulo }F\\
P(3) &=3x^2+3x&&\equiv -3\ne0 &&\text{ modulo }F\\
P(4) &=4x^3+6x^2+4x&&\equiv 2x^2\ne0 &&\text{ modulo }F\\
P(5) &=5(x^4 +2x^3+2x^2+x)&&=\color{blue}{ 0} &&\text{ modulo }F\\
\end{aligned}
$$
The induction with step six is based on
$$
\begin{aligned}
&P(n+6) - P(n)\cdot(X+1)^6 
\\
&\qquad=
(X+1)^{n+6} - X^{n+6} -1\\
&\qquad\ -(X+1)^{n+6} + X^n(X+1)^6 +(X+1)^6\\
&\qquad
=
X^n\underbrace{\Big(\ (X+1)^3+X^3\ \Big)}_{0\text{ modulo }F}\Big(\ (X+1)^3-X^3\ \Big)
+\underbrace{\Big(\ (X+1)^3+1\ \Big)}_{0\text{ modulo }F}\Big(\ (X+1)^3-1\ \Big)
\ .
\end{aligned}
$$
So $P(n+6)$ is zero modulo $F$ iff $P(n)$ is so. This elucidates the divisibility modulo $F$, this happens for $1,5$ plus a multiple of six, as claimed. If this happens, we want to test divisibility modulo $F^2$. So we extract the factor $F$ from getting
$$
\begin{aligned}
&\frac 1F\Big(P(n+6) - P(n)\cdot(X+1)^6\Big) 
\\
&\qquad
=
X^n\cdot\frac 1F\Big(\ (X+1)^3+X^3\ \Big)\cdot\Big(\ (X+1)^3-X^3\ \Big)
+\frac1F\Big(\ (X+1)^3+1\ \Big)\cdot\Big(\ (X+1)^3-1\ \Big)
\\
&\qquad
=
X^n\cdot\Big(\ 2X+1\ \Big)\cdot\Big(\ (X+1)^3-X^3\ \Big)
+\Big(\ X+2\ \Big)\cdot\Big(\ (X+1)^3-1\ \Big)
\\
&\qquad\qquad\text{ and working now modulo $F$}
\\
&\qquad
\equiv
-X^n\cdot2X(X-1) + 2X^2(X-1)
\\
&\qquad
=-2X(X-1)(X^n - X)
\ .
\end{aligned}
$$
We can now conclude with the information modulo $F^2$.

*

*If $n=6k+1$ then $(X^n-X)=X(X^{6k}-1)=X(X^6-1)(\dots)$, which is divisible by $(X^3-1)$, and thus also by $F$. Inductively, $P(6k+1)=P(n)$ is divisible by $F^2$.

*If $n=6k+5$ then $(X^n-X)=X(X^{6k+4}-1)=X(X^{6k+4}-X^4+X^4-1)=X^4(X^6-1)(\dots) + X(X^4-1)\equiv X(X-1)$ modulo $F$, and inductively $P(6k+5)=P(n)$ is modulo $F^2$ equal to $-nF$.

