Let $a,b,c$ be integer numbers such that $(a+b+c) \mid (a^{2}+b^{2}+c^{2})$. Show that there exist infinitely many positive integers $n$ such that $(a+b+c) \mid (a^{n}+b^{n}+c^{n})$. Laurentiu Panaitopol
Problem
Source: L. Panaitopol,Romania, TST 1987
Tags: modular arithmetic, induction, function, algebra, polynomial, number theory proposed, number theory
13.08.2005 08:41
Consider the equation $x^3 - (a+b+c) x^2 + (ab + bc + ca) x - abc = 0$. This equation is the characteristic equation of the recurrence relation $a_n = (a+b+c)a_{n-1} - (ab + bc + ca)a_{n-2} + (abc)a_{n-3}$. This is equivalent to $a_n = a_1a_{n-1} - \frac{{a_1}^2-a_2}{2} a_{n-2} + (abc) a_{n-3}$. We note that the formula for $a_n$ is $a_n = a^n + b^n + c^n$. Thus $a_1 = a + b + c, a_2 = a^2 + b^2 + c^2, a_3 = a^3 + b^3 + c^3$. If $\frac{{a_1}^2-a_2}{2} \equiv 0 \pmod{a_1}$, then $a_n \equiv (abc)a_{n-3} \pmod{a_1} \Rightarrow a_i \equiv 0 \pmod{a_1} \forall i \equiv 1$ or $2 \pmod{3}, i \in \mathbb{Z}^+$, since $a_1 \equiv a_2 \equiv 0 \pmod{a_1}$, and we are done. Likewise, if $a_1$ is odd, then ${a_1}^2-a_2 \equiv 0 \pmod{a_1} \Rightarrow \frac{{a_1}^2-a_2}{2} \equiv 0 \pmod{a_1}$ (Note that we are guaranteed that $\frac{{a_1}^2-a_2}{2} \in \mathbb{Z}$ since $\frac{{a_1}^2-a_2}{2} = ab + bc + ca \in \mathbb{Z}$) This means that we once again have the similar case of $a_n \equiv (abc)a_{n-3} \pmod{a_1}$ and we are done. Thus we can assume that $a_1$ is even and that $\frac{{a_1}^2-a_2}{2} \equiv \frac{a_1}{2} \pmod{a_1} \Rightarrow a_n \equiv \frac{a_1}{2}a_{n-2} + (abc)a_{n-3} \pmod{a_1}$. Note that since $a_n = a^n + b^n + c^n$, we have $a_i$ will have the same parity throughout $\forall i \in \mathbb{Z}^+$. Since we have assumed $a_1$ is even, we have $a_i$ is even $\forall i \in \mathbb{Z}^+$. Suppose that $\not\exists$ infinitely many $n$ such that $a_1 \mid a_n$, say $M$ is the largest integer such that $a_1 \mid a_M$. Now consider $a_{M+3}$. We have $a_{M+3} \equiv \frac{a_1}{2}a_{M+1} + (abc)a_{M} \equiv 0 \pmod{a_1}$, since $a_{M+1}$ is even. (Contradiction) $\therefore \exists$ infinitely many $n$ such that $a + b + c \mid a^n + b^n + c^n$.
07.12.2005 12:49
i think n=2^k is a solution
08.12.2005 14:41
ooiler wrote: i think n=2^k is a solution True by induction, but my solution is much stronger, asserting that $\forall \ i \equiv 1$ or $2 \pmod{3}$ we are sure that $a_i \equiv 0 \pmod{a_1}$, and that if we are also given that $a_1 \mid a_3$, then all $a_i$ will be divisible by $a_1$.
05.05.2007 21:36
There is another super-nice proof of problems like this (the proof is from a mathlinks user and imo gold simo_the_wolf): For the fundamental theorem of symmetric functions, you can write $a^{n}+b^{n}+c^{n}$ uniquely as a homogenous polynomial with integer coefficients in the variables: $\sigma_{1}= a+b+c$ $\sigma_{2}= ab+bc+ca$ $\sigma_{3}= abc$. If in each monomial of this polynomial there is a $\sigma_{1}$ or a $\sigma_{2}$, then a+b+c divides it. If there is only a $\sigma_{3}$, then its degree is a multiple of 3. Therefore, for each n non multiple of 3, we have $a+b+c \mid a^{n}+b^{n}+c^{n}$.
06.05.2007 01:26
I'm implicitly using symmetric functions, but thanks for pointing out.