# 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.

• I've done a little experimentation. It seems like every solution works for $n$ positive and not a multiple of 3. $(1,1,1)$ and $(1,1,4)$ work for all positve n. Here are some working $(a,b,c)$ triples: $(1,1,1)$, $(1,1,4)$, $(1,2,4)$, $(1,2,11)$, $(1,3,9)$, $(1,3,22)$, $(1,4,9)$, $(1,4,16)$, $(1,4,37)$, $(1,5,25)$, $(1,5,56)$, $(1,6,36)$, $(1,6,79)$, $(1,7,11)$, $(1,7,30)$, $(1,7,49)$, $(1,8,64)$, $(1,9,16)$, $(1,9,81)$, $(1,10,26)$, $(1,10,63)$, $(1,10,100)$, $(1,11,26)$, $(1,13,47)$, $(1,16,22)$, $(1,16,25)$, $(1,16,61)$, $(1,16,74)$, $(1,18,30)$, $(1,18,79)$. – NovaDenizen Aug 29 '15 at 19:02
• @NovaDenizen Thanks, but it's quite a small step towards solving – user261263 Aug 29 '15 at 19:57

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.

• Surprisingly simple, congratulations! – user261263 Aug 30 '15 at 14:30
• We can easily get $a+b+c\mid a^n+b^n+c^n$ for all $n\nmid 3$, but not always when $n\mid 3$. See my answer. – user236182 Sep 8 '15 at 13:38

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$.

• Here's how to finish your proof. Clearly if $p\mid a,b,c$ the problem reduces to a smaller triple so we can assume $\gcd(a,b,c)=1$. Now suppose for example $p\mid\gcd(a,b+c)$. Then $p\mid a^2+b^2+c^2=a^2+(b+c)^2-2bc$ so $p\mid2bc$. If $p$ is odd, we have $p\mid b,c$ so $p=2^k$. For $k>1$ we would have $2\mid b,c$. This means at most one of $\gcd(a,b+c)$, $\gcd(b,a+c)$, $\gcd(c,a+b)$ is $2$ and the others are $1$. Suppose wlog that $b,c$ are odd and $a$ is even. Then $a+b+c\mid a^2+b^2+c^2\equiv2\pmod4$, meaning that $v_2(a+b+c)=1$. Now use your argument with $n=k\cdot\varphi(\frac{a+b+c}2)+1$. – punctured dusk Aug 30 '15 at 11:03
• By the way, with that assumption you made we don't even need $a+b+c\mid a^2+b^2+c^2$; we can just use the same strategy for $a^n+b^n+c^n-(a+b+c)$. – punctured dusk Aug 30 '15 at 11:08
• What did you mean by $v_2$ in the formula $v_2(a+b+c)=1$? – Ievgen Aug 30 '15 at 11:29
• As for the note "Clearly if p∣a,b,c the problem reduces to a smaller triple" - it's true if $$\mathrm{gcd}(p, k+l+m)=1,$$ where $a=pk, b=pl, c =pm$, but not too obvious if $\mathrm{gcd}(p, k+l+m)>1$. – Ievgen Aug 30 '15 at 11:54
• Your partial solution might be something to build on, so +1! – user261263 Aug 30 '15 at 12:07

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).

• Very interesting! – user261263 Aug 31 '15 at 19:10

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.

• I think you need to check your second inequality. You have mistakenly deduced that $a+b+c \geq a^{2}+b^2+c^2$, this does not follow logically from your arguments. – Morgan Rodgers Aug 26 '15 at 7:32
• If $a+b+c$ is divisible by $a^2+b^2+c^2$ and $a + b + c$ is positive integer than $a+b+c \geq a^{2}+b^2+c^2$. Seems logical to me. – user5261423 Aug 27 '15 at 9:36
• $a+b+c \mid a^{2}+b^{2}+c^{2}$ means $a^{2}+b^{2}+c^{2}$ is divisible by $a+b+c$, not the other way around. – Morgan Rodgers Aug 27 '15 at 9:49