Let's say that an ordered triple of positive integers $(a, b, c)$ is $n$-powerful if $a \leq b \leq c$, $\operatorname{gcd}(a, b, c)=1$, and $a^{n}+b^{n}+c^{n}$ is divisible by $a+b+c$. For example, $(1,2,2)$ is 5 -powerful.

a) Determine all ordered triples (if any) which are $n$-powerful for all $n \geq 1$.

b) Determine all ordered triples (if any) which are 2004-powerful and 2005-powerful, but not 2007-powerful.

[Note that $\operatorname{gcd}(a, b, c)$ is the greatest common divisor of $a, b$ and $c$.]
Let $T_{n}=a^{n}+b^{n}+c^{n}$ and consider the polynomial

$$
P(x)=(x-a)(x-b)(x-c)=x^{3}-(a+b+c) x^{2}+(a b+a c+b c) x-a b c .
$$

Since $P(a)=0$, we get $a^{3}=(a+b+c) a^{2}-(a b+a c+b c) a+a b c$ and multiplying both sides by $a^{n-3}$ we obtain $a^{n}=(a+b+c) a^{n-1}-(a b+a c+b c) a^{n-2}+(a b c) a^{n-3}$. Applying the same reasoning, we can obtain similar expressions for $b^{n}$ and $c^{n}$ and adding the three identities we get that $T_{n}$ satisfies the following 3-term recurrence:

$$
T_{n}=(a+b+c) T_{n-1}-(a b+a c+b c) T_{n-2}+(a b c) T_{n-3} \text {, for all } n \geq 3
$$

From this we see that if $T_{n-2}$ and $T_{n-3}$ are divisible by $a+b+c$, then so is $T_{n}$. This immediately resolves part (b) - there are no ordered triples which are 2004-powerful and 2005-powerful, but not 2007-powerful-and reduces the number of cases to be considered in part (a): since all triples are 1-powerful, the recurrence implies that any ordered triple which is both 2-powerful and 3-powerful is $n$-powerful for all $n \geq 1$.

Putting $n=3$ in the recurrence, we have

$$
a^{3}+b^{3}+c^{3}=(a+b+c)\left(a^{2}+b^{2}+c^{2}\right)-(a b+a c+b c)(a+b+c)+3 a b c
$$

which implies that $(a, b, c)$ is 3-powerful if and only if $3 a b c$ is divisible by $a+b+c$. Since

$$
a^{2}+b^{2}+c^{2}=(a+b+c)^{2}-2(a b+a c+b c),
$$

$(a, b, c)$ is 2-powerful if and only if $2(a b+a c+b c)$ is divisible by $a+b+c$.

Suppose a prime $p \geq 5$ divides $a+b+c$. Then $p$ divides $a b c$. Since $\operatorname{gcd}(a, b, c)=1, p$ divides exactly one of $a, b$ or $c$; but then $p$ doesn't divide $2(a b+a c+b c)$.

Suppose $3^{2}$ divides $a+b+c$. Then 3 divides $a b c$, implying 3 divides exactly one of $a$, $b$ or $c$. But then 3 doesn't divide $2(a b+a c+b c)$.

Suppose $2^{2}$ divides $a+b+c$. Then 4 divides $a b c$. Since $\operatorname{gcd}(a, b, c)=1$, at most one of $a, b$ or $c$ is even, implying one of $a, b, c$ is divisible by 4 and the others are odd. But then $a b+a c+b c$ is odd and 4 doesn't divide $2(a b+a c+b c)$.

So if $(a, b, c)$ is 2- and 3-powerful, then $a+b+c$ is not divisible by 4 or 9 or any prime greater than 3. Since $a+b+c$ is at least $3, a+b+c$ is either 3 or 6. It is now a simple matter to check the possibilities and conclude that the only triples which are $n$-powerful for all $n \geq 1$ are $(1,1,1)$ and $(1,1,4)$.