Polynomials with no Common Factors

Let $A = b-c, B = c-a, C = a-b$ , so we have:

$F_n = a\cdot A^n + b\cdot B^n + c\cdot C^n.$

Suppose $A, B, C$ are roots of the cubic equation $X^3 - P X^2 + Q X - R = 0$ . This gives us $P = A+B+C = 0$ , $Q = AB+BC+CA$ and $R = ABC$ . Furthermore, since $A, B, C$ satisfy the said cubic equation, we have (since $P=0$ ):

$A^3 - PA^2 + QA - R = 0 \implies a A^{n+1} = - Q(a A^{n-1}) + R(a A^{n-2}).$

Similarly, we have:

$\begin{aligned}b B^{n+1} &= - Q(b B^{n-1}) + R(b B^{n-2})\\ c C^{n+1} &= - Q(c C^{n-1}) + R(c C^{n-2})\end{aligned}$

Adding these two equations and the earlier one, we get:

$F_{n+1} = -Q\cdot F_{n-1} + R\cdot F_{n-2}.$

In particular, since $F_1=0$ , we have:

$F_4 = -QF_2 + RF_1 = -QF_2$

It is easy to check that both $F_2$ and $Q$ are irreducible so it remains to find all polynomials $F_n$ which are divisible by $Q$ or $F_2$ .

$-$

Let's consider $Q$ first. From the recurrence equation $F_{n+1} = -Q F_{n-1} + R F_{n-2}$ we see that $F_{n+3}$ is a multiple of $Q$ if and only if $F_n$ is. Hence, it suffices to look at just $F_1, F_2, F_3$ . Since $F_1$ is the only one out of these three which is divisible by $Q$ , we conclude:

• $F_n$ is divisible by $Q$ if and only if $n \equiv 1 \pmod 3$ .

Next up, we need to find all $n$ for which $F_2 | F_n$ . We claim that $n=1,2,4$ are the only solutions. To do that, we find rational numbers $a, b, c$ satisfying $F_2(a,b,c) = 0$ . That was hard, but after some effort, we found:

$a = -\frac {10} 3, \ b=14, \ c=1$

We claim that $F_n(a,b,c) \ne 0$ for $n\ge 5$ . Indeed, suppose $F_n(a,b,c) = 0$ . Then:

$-\frac {10} 3 13^n + 14\left(\frac {13} 3\right)^n + \left(-\frac{52}3\right)^n = 0.$

After some simplification, we obtain:

$14 + (-4)^n = 10\times 3^{n-1}.$

It is easy to show that this has no integer solution for $n\ge 5$ .

• If $n$ is even, we get: $10 = 14\times 3^{-(n-1)} + 4\times (4/3)^{n-1} \ge 4\times (4/3)^{n-1}$ . So $n \le 4$ .
• If $n$ is even, we get $14 = 10\times 3^{n-1} + 4^n$ ; obviously it fails for $n>1$ .

Conclusion

The only $F_n$ which share a common factor with $F_4$ are those where $n\equiv 1 \pmod 3$ or $n=2$ . Hence the answer is $1000 - 334 - 1 = \fbox{665}$ .

Observe that $F_0 = a+b+c$ , $F_1 = 0$ , $F_2 = \sum a(b-c)^2 = a^2(b+c)+a(b^2+c^2-6bc)+bc(b+c)$ , and considering $F_n$ as a linear recurrence in $a-b,b-c,c-a$ , we get $F_n = U F_{n-2} + V F_{n-3}$ for $n\ge3$ , where $U = -\sum (a-b)(b-c) = \frac{1}{2}\sum (a-b)^2$ and $V = \prod (a-b)$ . In particular, $F_4 = UF_2$ . It's also easy to check that $U,F_2$ are irreducible in $\mathbb{R}[a,b,c]$ (although $U$ factors as $\frac12(a+b\omega+c\omega^2)(a+b\omega^2+c\omega)$ , where $\omega = e^{2\pi i/3}$ , in $\mathbb{C}$ ), e.g. by noting that any nontrivial factorization of either into two polynomials would have to have both polynomials linear in each variable; for $F_2$ , this would imply $\deg{F_2} \le 1+1$ , and for $U$ , this would require $e^{2\pi i/3} \in \mathbb{R}$ . But $\mathbb{R}[a,b,c]$ is a UFD, so $F_n,F_4$ share a factor iff $U\mid F_n$ or $F_2\mid F_n$ (or both). First we prove that $U\mid F_n$ iff $n\equiv1\pmod{3}$ . Taking our recurrence for $\{F_n\}$ mod $U$ , we get $F_n \equiv VF_{n-3} \pmod{U}$ . Yet $\gcd(U,V) = 1$ and $F_1=0$ is the only one among $F_0,F_1,F_2$ divisible by $U$ , so the result follows by induction. Next, we show that $F_2\mid F_n$ iff $n\in\{1,2,4\}$ . The "if" direction is clear; now suppose for contradiction that $F_2\mid F_n$ for some $n\ge3$ not equal to $4$ . Then for reals $x,y,z$ , $F_n(x,y,z) = \sum x(y-z)^n = 0$ whenever $F_2(x,y,z) = \sum x(y-z)^2 = 0$ . For convenience, we fix $z=1$ and $y>9000$ , and take $x$ to be the smaller root (from the quadratic formula) $\frac{-(y^2-6y+1) - \sqrt{(y^2-6y+1)^2 - 4y(y+1)^2}}{2(y+1)}$ $= -\frac{y^2-6y+1+(y-1)\sqrt{y^2-14y+1}}{2(y+1)}$ of $F_2(x,y,1)$ (a standard way to factor out the $y-1$ is to write $y^2-6y+1$ as $(y+1)^2 - 8y$ ). We will derive a contradiction by taking $y$ sufficiently large. Using $\frac{1}{y+1} = \frac{1}{y}+O(y^{-2})$ and the binomial expansion $\sqrt{1-\frac{14y-1}{y^2}} = 1 - \frac{1}{2}\frac{14y-1}{y^2} + O(y^{-2})$ , we obtain $\frac{1-x}{y-1} = \frac{y-3+\sqrt{y^2-14y+1}}{2(y+1)}$ $= 1-\frac{12+O(y^{-1})}{2(y+1)} = 1-6y^{-1} + O(y^{-2})$ whence $1-x = y-1-6+6y^{-1}+O(y^{-1})$ and $\frac{x-y}{y-1} = -1-\frac{1-x}{y-1} = -2+O(y^{-1})$ . Since $n$ is constant, this means $$0 = x + y\left(\frac{1-x}{y-1}\right)^n + \left(\frac{x-y}{y-1}\right)^n $$ is $$(8-y+O(y^{-1})) + y(1-6ny^{-1} + O(y^{-2})) + (-2)^n+O(y^{-1}),$$ which is in turn $8-6n + (-2)^n + O(y^{-1}).$ But $8-6n+(-2)^n$ is an integer, so this can only hold for $y$ large if $(-2)^n = 6n-8 \implies n\in\{1,2,4\}$ , contradiction. To finish up, our answer is just the number of positive integers $n\le 1000$ not congruent to $1\pmod{3}$ and not equal to $2$ , i.e. $1000-334-1=665$ .

Let $j= b-c$ , $k=c-a$ . Note that $f (a,b,c) \mid F_n (a,b,c) \iff f(a,j,k) \mid F_n(a,j,k)$ , where $f(x,y,z)$ is any polynomial over three variables. We shall continue our analysis with $a,j,k$ instead. Plugging these values in the expansion of $F_n(a,b,c)$ , it can be shown that $F_n(a,j,k)= a(j^n + k^n + (-1)^n(j+k)^n) + jk (j^{n-1} - k^{n-1} )$ Let's try to factorize $F_4(a,j,k)$ . Note that $F_n (a,j,k) = a(j^4+k^4+(j+k)^4) + jk (j^3 - k^3)$ It can be shown that $j^4+k^4+(j+k)^4 = 2(j^2+jk+k^2)^2$ . We also know that $j^3-k^3= (j-k)(j^2+jk+k^2)$ . It is now obvious that $j^2+jk+k^2$ is a factor of $F_4(a,j,k)$ . We can now show that $F_4 (a,j,k) = (j^2+jk+k^2)(2a(j^2+jk+k^2) + jk(j-k))$ Note that $2a(j^2+jk+k^2) + jk(j-k) \equiv jk(j-k) \pmod {j^2+jk+k^2}$ It then follows that $\begin{array} {l l }& \gcd (j^2+jk+k^2, 2a(j^2+jk+k^2) + jk(j-k) )\\ = & \gcd (j^2+jk+k^2, jk(j-k) ) \end{array}$ For some $k \neq 0$ , let's consider the equation $jk(j-k) = 0$ in $j$ . Note that the roots of this equation are $j=0$ and $j=k$ . However, plugging these values in the polynomial $j^2+jk+k^2$ , we get $k^2$ and $3k^2$ respectively, none of which are zero. Hence, $\gcd (j^2+jk+k^2, jk(j-k) ) = 1$ $\implies \gcd (j^2+jk+k^2, 2a(j^2+jk+k^2) + jk(j-k))= 1$ We thus conclude the two factors of $F_4(a,j,k)$ are co-prime. Thus, $F_n (a,j,k)$ will share some common factors with $F_4 (a,j,k)$ iff $j^2+jk+k^2 \mid F_n (a,j,k)$ or $2a(j^2+jk+k^2) + jk(j-k)) \mid F_n (a,b,c)$ .
Let $\omega$ denote the complex cube root of unity, so $\omega^2 + \omega + 1= 0$ . If we consider the equation $j^2+jk+k^2=0$ as an equation in $k$ , we get $k= j\omega$ and $j \omega^2$ as roots. Again, if we consider the equation $2a(j^2+jk+k^2) + jk(j-k)=0$ as an equation in $a$ , we get $a= \frac{-jk(j+k)}{2(j^2+jk+k^2)}$ as a root. By the remainder factor theorem, the above condition will be satisfied iff $F_n(a, j, j \omega ) = 0$ $\text{or}$ $F_n\left (\frac{-jk(j+k)}{2(j^2+jk+k^2)}, j, k \right )= 0$ Let's try to investigate the first case. Plugging the values in the expansion of $F_n(a,j,k)$ and using the fact that $\omega^2= -\omega - 1$ , we can show that $F_n (a, j, j\omega ) = j^n (a(1 + \omega^n + \omega^{2n} ) + j \omega (1-\omega^{n-1}) )$ Now, if $n \equiv 0 \pmod3$ , using $\omega^n= 1$ , we can show that $F_n (a, j, j \omega ) = j^n (3a + \omega j (\omega + 2 ) ) \neq 0$ If $n \equiv 1 \pmod3$ , using $\omega^n = \omega$ , we can show that $F_n (a, j, j\omega ) = j^n (1 + \omega - (1 + \omega ) ) = 0$ If $n \equiv 2 \pmod3$ , using $\omega^n = \omega^2 = -1-\omega$ , we can show that $F_n (a, j, j\omega ) = \omega j (1 - \omega ) \neq 0$ We thus conclude $F_n(a,j,j \omega ) = 0$ if and only if $n \equiv 1 \pmod3$ . There are $334$ such numbers from $1$ to $1000$ .

Let's investigate the second case, when $F_n\left (\frac{-jk(j+k)}{2(j^2+jk+k^2)}, j, k \right )= 0$ . Plugging these values in the expansion of $F_n(a, j, k)$ , it can be shown that $\begin{array} {l l } & F_n\left (\frac{-jk(j+k)}{2(j^2+jk+k^2)} \right ) \\ = & \frac{jk(k-j)(j^n+k^n+(-1)^n(j+k)^n)}{2(j^2+jk+k^2)} + jk (j^{n-1} + k^{n-1}) \end{array}$ For $n=1$ and $n=2$ , we can manually evaluate $F_n(a,j,k)$ and show that it is equal to $0$ in both cases. For $n>2$ , we write down the binomial expansions of the powers. Note that
$\begin{array} {l l} & \frac{jk(k-j)(j^n+k^n+(-1)^n(j+k)^n)}{2(j^2+jk+k^2)} + jk (j^{n-1} + k^{n-1}) \\ = & -jk\frac{(j-k)(2(j^2+jk+k^2)\sum \limits_{i=0}^{n-2}j^ik^{n-2-i} - (j^n + k^n + (-1)^n(j+k)^n) }{2(j^2+jk+k^2)} \end{array}$ This has to be equal to $0$ , so we must have $\begin{array} { l l} & (2(j^2+jk+k^2)\sum \limits_{i=0}^{n-2}j^ik^{n-2-i} \\ & = j^n + k^n + (-1)^n(j+k))^n \\ \implies & (2(j^2+jk+k^2)\sum \limits_{i=0}^{n-2}j^ik^{n-2-i} \\ & =(1+(-1)^n)j^n + (1+(-1)^n)k^n + (-1)^n\sum \limits_{i=1}^{n-1} \binom{n}{i}j^{n-i}k^i \end{array}$ where the last step follows from writing the binomial expansion of $(j+k)^n$ . Comparing coefficients of $j^n$ and $k^n$ , we obtain $1 + (-1)^n = 2 \implies 2 \mid n$ . Again, comparing the coefficients of $jk$ , we obtain $(-1)^n \binom{n}{1}= 4 \implies n=4$ . Of course, $n=4$ is a trivial solution. Also note that $n=4$ is included in the count of the first case. Other than that, there are $2$ values of $n$ satisfying the conditions; $n=1$ and $n=2$ . But since $1 \equiv 1 \pmod3$ , this is also included in the count of the first case. Thus the second case produces $1$ more distinct solution. The total number of such $n$ between $1$ and $1000$ is $334+1=335$ . Our desired answer will then be $1000-335= \boxed{665}$ .