[Brilliant.org] Polynomials with no Common Factors

Okay, I've decided to post the solutions from Brilliant.org as they have proven to provide some fine problems. All the problems are owned by Brilliant.org and I don't deserve any credits for those. I only provide my own versions of the solutions.

The following is the hardest problem on NT & Algebra section last week. 

If you are currently a level 5 NT&Algebra user, you can see a solution in this link, using recursion formula and the reducibility property of a polynomial. There might be unfamiliar terms such as UFD in that solution so you need to have some basic understanding of the terms in the first place.

Anyway, I have a different, longer approach that should be more elementary. Here it goes,

First, let $x = a-b,y=c-a$ so that $b = a-x,c = a+y$ and thus
\begin{align}
\nonumber  F_n(a,x,y) & = a(-x-y)^n+(a-x)y^n+(a+y)x^n \\
& = a(x^n+y^n+(-x-y)^n) + xy(x^{n-1}-y^{n-1}) \label{eq1}
\end{align}
as now I am using the variable $(a,x,y)$ instead of $(a,b,c)$. It will be easier for one to analyze the factors of $F_n$ in this form as you will see very soon.

As we're interested for $F_4$, let $p$ be a root of $p^3 = 1, p \neq 1 \Rightarrow p^2 = -p-1$ and so in general
\[p^n =
\begin{cases}
1 & \mbox{if } n \equiv 0 \mod 3 \\
p & \mbox{if } n \equiv 1 \mod 3 \\
-p-1 & \mbox{if } n \equiv 2 \mod 3
\end{cases}
\]

From $\eqref{eq1}$ above, we obtain

\begin{align*}
F_4(a,x,px) & = a(x^4+p^4x^4+(-1-p)^4x^4)+px^2(x^3-y^3)) \\
& = x^4a(1+p^4+(p^2)^4) \\
& = x^4a(1+p+p^2) = 0
\end{align*}
means that $(y-px)|F_4$ for the two complex roots of $p^2+p+1=0$ and so
\[\prod_{p} (y-px) = x^2 \prod_p \left(\frac{y}{x}-p \right) = x^2\left( \frac{y}{x} \right)^2+\frac{y}{x}+1=  (y^2+yx+x^2)\]
divides $F_4$. Knowing one of its factor, now we can show easily that
\begin{align}
\nonumber  F_4(a,x,y) & = a(x^4+y^4+(-x-y)^4))+xy(x^3-y^3) \\
\nonumber & = 2a(x^2+xy+y^2)^2+xy(x^2+xy+y^2)(x-y) \\
& = (x^2+xy+y^2)(2a(x^2+xy+y^2)+xy(x-y)) \label{eq2}
\end{align}
Clearly, $gcd(x^2+xy+y^2,2a(x^2+xy+y^2)+xy(x-y)) = gcd(x^2+xy+y^2,xy(x-y)) = 1$
since if $f(x,y) = x^2+xy+y^2$, then
\[f(0,y) = y^2, f(x,0) = x^2, f(x,x) = 3x^2\]
are not always zero.

Thus, both factors of $F_4$ are mutually prime and irreducible in $\mathbb{R}[a,x,y]$ from which one can conlude that $F_n$ has some common factors with $F_4$ if and only if $x^2+xy+y^2 | F_n$ where $p$ is as mentioned above) or  $a(x^2+xy+y^2)+xy |F_n$. In other words, the condition is equivalent to $F_n(a,x,px) = 0$ or $F_n \left(\frac{-xy(x-y)}{2(x^2+xy+y^2)},x,y \right) = 0$ (where $x^2+xy+y^2  \neq 0 \Leftrightarrow y \neq px$).

From $\eqref{eq2}$ above, we obtain

\begin{align*}
F_n(a,x,px) & = a(x^n+p^nx^n+(-1-p)^nx^n)+px^2(x^{n-1}-y^{n-1}) \\
& = x^n(a(1+p^n+(p^2)^n)+px(1-p^{n-1}))
\end{align*}
-) If $n \equiv 0 \mod 3$, then
\[F_n(a,x,px) = x^n(a(1+1+1)+px(1-(-1-p)) = x^n(3a+px(p+2)) \neq 0\] for some choice of $x,a$
-) If $n \equiv 1 \mod 3$, then
\[F_n(a,x,px) = x^n(a(1+p+(-p-1))+px(1-1) = 0\]
-) If $n \equiv 2 \mod 3$, then
\[F_n(a,x,px) = x^n(a(1+(-p-1)+p)+px(1-p) = px(1-p) \neq 0\] for some $x \neq 0$

Hence, $F_n(a,x,px) = 0$ for all $a,x$ if and only if $n \equiv 1 \mod 3$.

Also from $\eqref{eq1}$, we have


\begin{align*}
F_n \left(\frac{-xy(x-y)}{2(x^2+xy+y^2)},x,y \right) &= -\frac{xy(x-y)(x^n+y^n+(-x-y)^n)}{2(x^2+xy+y^2)}+xy(x^{n-1}-y^{n-1})
\end{align*}
which is $0$ for $n = 1$, and for $n \geq 2$ equal to
\begin{align*}
\frac{xy(x-y)(2(x^2+xy+y^2)\displaystyle\sum_{k=0}^{n-2}x^ky^{n-2-k}-(x^n+y^n+(-x-y)^n))}{2(x^2+xy+y^2)}
\end{align*} which is $0$ iff all the respective coefficients of
\begin{align*}
g(x,y) &= 2(x^2+xy+y^2)\displaystyle\sum_{k=0}^{n-2}x^ky^{n-2-k} \\
\end{align*}
and
\begin{align*}
h(x,y) &= (x^n+y^n+(-x-y)^n) \\
& = (1+(-1)^n)x^n + \sum_{k=1}^{n-1} (-1)^n \binom{n}{k}x^{n-k}y^k + (1+(-1)^n)y^n
\end{align*}
agree. We can check that $g(x,y) = h(x,y) = 2(x^2+xy+y^2)$ for $n = 2$ and
\[g(x,y) = 2x^n+4x^{n-1}y+3\sum_{k=2}^{n-3}x^{n-k}y^k + 2xy^{n-1}+y^n\]
which  means that $1+(-1)^n = 2 \Leftrightarrow n$ even, and
\[(-1)^n \binom{n}{1} = 4 \Leftrightarrow n = 4\]
One can check that $n = 4$ also works and so
$F_n \left(\frac{-xy(x-y)}{2(x^2+xy+y^2)},x,y \right) = 0$ (where $x^2+xy+y^2  \neq 0 \Leftrightarrow y \neq px$) if and only if $n = 1,2$ or $4$.

The final conclusion is $F_n$ has some common factors with $F_4$ if and only if  $n \equiv 1 \mod 3$ or $n = 2$. There are $(1+\lfloor \frac{1000-1}{3} \rfloor) +1 = 335$ such $n$ which is less than $1000$ and so there are $1000-335 = 665$ possible $n \leq 1000$ such that $F_n$ doesn't have any common factors with $F_4$.