# If $a + b + c \mid a^2 + b^2 + c^2$ then $a + b + c \mid a^n + b^n + c^n$ for infinitely many $n$

Let $a,b,c$ positive integer such that $a + b + c \mid a^2 + b^2 + c^2$.
Show that $a + b + c \mid a^n + b^n + c^n$ for infinitely many positive integer $n$.

(problem composed by Laurentiu Panaitopol)

So far no idea.

#### Solutions Collecting From Web of "If $a + b + c \mid a^2 + b^2 + c^2$ then $a + b + c \mid a^n + b^n + c^n$ for infinitely many $n$"

Claim. $a+b+c\mid a^{2^n}+b^{2^n}+c^{2^n}$ for all $n\geq0$.

Proof. By induction: True for $n=0,1$ $\checkmark$. Suppose it’s true for $0,\ldots,n$. Note that $$a^{2^{n+1}}+b^{2^{n+1}}+c^{2^{n+1}}=(a^{2^n}+b^{2^n}+c^{2^n})^2-2(a^{2^{n-1}}b^{2^{n-1}}+b^{2^{n-1}}c^{2^{n-1}}+c^{2^{n-1}}a^{2^{n-1}})^2+4a^{2^{n-1}}b^{2^{n-1}}c^{2^{n-1}}(a^{2^{n-1}}+b^{2^{n-1}}+c^{2^{n-1}})$$

and that

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

is divisible by $a+b+c$ by the induction hypothesis.

It seems that there’s a partial solution.

Suppose that $\mathrm{gcd}(a,a+b+c)=\mathrm{gcd}(b,a+b+c)=\mathrm{gcd}(c,a+b+c)=1$.
Then for $n=k\cdot \phi(a+b+c)+1 \, (k=1,2, \ldots )$, where $\phi$ is Euler’s function, we have:
$$(a^n+b^n+c^n)-(a^2+b^2+c^2)=a^2 (a^{n-1}-1) + b^2 (b^{n-1}-1) + c^2 (c^{n-1}-1),$$
where all round brackets are divisible by $a+b+c$ according to Euler theorem.
Therefore $(a+b+c) \mid (a^n+b^n+c^n)$ for all these $n$.

There’s one more solution (it isn’t mine). One can even prove that $(a + b + c) \mid (a^n + b^n + c^n)$ for all $n=3k+1$ and $n=3k+2$. It’s enough to prove that
$a + b + c \mid a^n + b^n + c^n$ => $a + b + c \mid a^{n+3} + b^{n+3} + c^{n+3}$.
The proof is here:
https://vk.com/doc104505692_416031961?hash=3acf5149ebfb5338b5&dl=47a3df498ea4bf930e
(unfortunately, it’s in Russian but it’s enough to look at the formulae). One point which may need commenting:
$(ab+bc+ca)(a^{n-2} + b^{n-2} + c^{n-2})$ is always divisible by $(a+b+c)$ (it’s necessary to consider 2 cases: $(a+b+c)$ is odd and $(a+b+c)$ is even).

If $a,b,c,n\in\Bbb Z_{\ge 1}$, $a+b+c\mid a^2+b^2+c^2$, then $$a+b+c\mid a^n+b^n+c^n$$

is true when $n\nmid 3$, but not necessarily when $n\mid 3$.

$$x^2+y^2+z^2+2(xy+yz+zx)=(x+y+z)^2$$

$$\implies x+y+z\mid 2(xy+yz+zx)$$

$$\implies x+y+z\mid (x^k+y^k+z^k)(xy+yz+zx)$$

for all $k\ge 1$ (to see why, check cases when $x+y+z$ is even and when it’s odd).

$$x^{n+3}+y^{n+3}+z^{n+3}=(x^{n+2}+y^{n+2}+z^{n+2})(x+y+z)$$

$$-(x^{n+1}+y^{n+1}+z^{n+1})(xy+yz+zx)+(x^n+y^n+z^n)xyz$$

for all $n\ge 1$. We know $$x+y+z\mid (x^{n+2}+y^{n+2}+z^{n+2})(x+y+z)$$

$$-(x^{n+1}+y^{n+1}+z^{n+1})(xy+yz+zx)$$

Now let $(x,y,z)=(x_1,y_1,z_1)=(1,3,9)$. $$x_1+y_1+z_1\nmid x_1^3+y_1^3+z_1^3$$ $$x_1+y_1+z_1\nmid \left(x_1^3+y_1^3+z_1^3\right)x_1y_1z_1$$ $$\implies x_1+y_1+z_1\nmid x_1^6+y_1^6+z_1^6$$

Since $x_1+y_1+z_1$ is coprime to $x_1,y_1,z_1$, we get $$x_1+y_1+z_1\nmid (x_1^6+y_1^6+z_1^6)x_1y_1z_1,$$

and so $x_1+y_1+z_1\nmid x_1^9+y_1^9+z_1^9$, etc.

Therefore $x+y+z$ cannot generally (for all $x,y,z\in\mathbb Z_{\ge 1}$) divide $x^{3m}+y^{3m}+z^{3m}$ for any given $m\ge 1$.

However, we easily get $x+y+z$ always divides $x^n+y^n+z^n$ for $n$ not divisible by $3$,

because $x+y+z\mid (x+y+z)xyz$ and $x+y+z\mid \left(x^2+y^2+z^2\right)xyz$,

because $x+y+z\mid x^2+y^2+z^2$ (given), so $x+y+z\mid x^4+y^4+z^4, x^5+y^5+z^5$,

so $x+y+z\mid \left(x^4+y^4+z^3\right)xyz, \left(x^5+y^5+z^5\right)xyz$,

so $x+y+z\mid x^7+y^7+z^7, x^8+y^8+z^8$, etc.

Here’s a more intuitive way to get the idea of considering powers of $2$.
Added (below): in the same way we can prove that any $n=6k\pm1$ works.

Note that $a+b+c\mid(a+b+c)^2-(a^2+b^2+c^2)=2(ab+bc+ca)$. By The Fundamental Theorem of Symmetric Polynomials (FTSP), $a^n+b^n+c^n$ is an integer polynomial in $a+b+c$, $ab+bc+ca$ and $abc$. If $3\nmid n$, no term has degree divisible by $3$ so each term has at least one factor $a+b+c$ or $ab+bc+ca$. If we can find infinitely many $n$ such that the terms without a factor $a+b+c$ have a coefficient that is divisible by $2$, then we are done because $a+b+c\mid2(ab+bc+ca)$. This suggests taking a look to the polynomial $a^n+b^n+c^n$ over $\Bbb F_2$. Note that over $\Bbb F_2$, $a^{2^n}+b^{2^n}+c^{2^n}=(a+b)^{2^n}+c^{2^n}=(a+b+c)^{2^n}$ is divisible by $(a+b+c)$. Because the polynomial given by FTSP over $\Bbb F_2$ is the reduction modulo $2$ of that polynomial over $\mathbb Z$ (this is a consequence of the uniqueness given by the FTSP), this shows that the coefficients of those terms that have no factor $a+b+c$ is divisible by $2$, and we are done because $3\nmid2^n$. (In fact all coefficients except that of $(a+b+c)^{2^n}$ are divisible by $2$.)

Ievgen’s answer inspired me to generalise the above approach to $n=6k\pm1$. Consider again $a^n+b^n+c^n$ as an integer polynomial in $abc,ab+bc+ca,a+b+c$ (which we can do by FTSP). Because $3\nmid n$, no term has the form $(abc)^k$. It remains to handle the terms of the form $m\cdot(ab+bc+ca)^k(abc)^l$. If $a+b+c$ is odd, then $a+b+c\mid ab+bc+ca$ and we’re done. If $a+b+c$ is even, at least one of $a,b,c$ is even so $2\mid abc$, and hence $a+b+c\mid m\cdot(ab+bc+ca)^k(abc)^l$. (Note that $l>0$ because $n$ is odd.)

For any positive integer x this is true: $x \leqslant x^2$ (From $1 \leqslant x$ for any positive ineger x ). So $a + b + c \leqslant a^2 + b^2 + c^2$. But for 2 positive integers $x$, $y$ $x$ is divisible by $y$ only if $x \geqslant y$. So $a + b + c \geqslant a^2 + b^2 + c^2$ if $a + b + c \mid a^2 + b^2 + c^2$.
From these 2 inequalities:
$a + b + c = a^2 + b^2 + c^2$

So $a + b – a^2 – b^2 = c^2 – c$

Evaluation for the right part $c^2 – c \geqslant 0$ (because $x \leqslant x^2$ for any positive integer x).
Evaluation for the left part $a + b – a^2 – b^2 \leqslant 0$ (adding 2 inequalities $a – a^2 \leqslant 0$ and $b – b^2 \leqslant 0$)

So the left part is $\leqslant 0$ and the right part $\geqslant 0$. But they are equal so $a + b – a^2 – b^2 = c^2 – c = 0$ and $c^2 = c$. c is positive so we can divide both part of the last equation by c and get $c = 1$.

Similarly $b = 1$ and $a = 1$. So $a + b + c = 3$ and $a^n + b^n + c^n = 3$ for any positive $n$. 3 is divisible by 3 so $a + b + c \mid a^n + b^n + c^n$ for infinitely many positive integer n.