# What is the maximum value of $(a+ b+c)$ if $(a^n + b^n + c^n)$ is divisible by $(a+ b+c)$ where the remainder is 0?

The ‘energy’ of an ordered triple $$(a, b, c)$$ formed by three positive integers $$a$$, $$b$$ and $$c$$ is said to be n if the following $$c$$ $$\ge b\geq a$$, gcd$$(a, b, c) = 1$$, and $$(a^n + b^n + c^n)$$ is divisible (remainder is 0) by $$(a +b+ c)$$. There are some possible ordered triple whose ‘energy’ can be of all values of $$n \ge$$ $$1$$. In this case, for which ordered triple, the value of $$(a+b+c)$$ is maximum?

Second part (of the original problem) Determine all triples $$(a,b,c)$$ that are simultaneously $$2004$$-good and $$2005$$-good, but not $$2007$$-good.

I can't understand the first line of this question. Any 3 consecutive numbers have a gcd of 1. Moreover if $$n=1$$, then $$(a^n + b^n + c^n) = (a +b+ c)$$.

• What I think they are saying is if $a+b+c\mid a^n+b^n+c^n$ for every $n$ and $\gcd(a,b,c) = 1$ then what is the maximum value of $a+b+c$. – kingW3 Jan 11 at 2:04
• Could you please explain if there is any valid solution of this question? – Shromi Jan 11 at 3:01
• @Shromi There is at least one valid "trivial" solution of $\left(a,b,c\right) = \left(1,1,1\right)$, which of course gives that $a + b + c = 3$. I'm not sure if there are any other larger solutions, with my best guess being that there isn't, but I'm not sure offhand how to prove it, although I am thinking about it. – John Omielan Jan 11 at 3:10
• @Lee Thanks for the comment, however, for your for $\left(a, b, c\right) = \left(1, 2, 3\right)$, then $a + b + c = 6$, but $a^2 + b^2 + c^2 = 1 + 4 + 9 = 13$, which is not a multiple of $6$. Note the values must divide for every power of $n$. – John Omielan Jan 11 at 4:08
• @JohnOmielan, yes, I miss that part – Lee Jan 11 at 4:09

The answer is indeed $$6$$. Here is a complete solution.

First, take a prime $$p$$ such that, $$p\mid a+b+c$$. Note that, if $$p$$ divides two of $$a$$ and $$b$$, then it must divide the third, contradicting with $$(a,b,c)=1$$. Thus, $$p$$ either divides none of them, or only one.

1. If $$p\nmid a,b,c$$, then by taking $$n=p-1$$, we have, by Fermat's theorem that $$a^{p-1}\equiv b^{p-1}\equiv c^{p-1}\equiv 1 \pmod{p}$$. Thus, $$p\mid 3$$, hence $$p=3$$.
2. If $$p\mid a$$, and $$p\nmid b,c$$, then we obtain $$p\mid 2$$, by taking $$n=p-1$$.

Therefore, only prime divisors of $$a+b+c$$ are $$2$$ or $$3$$. Now, for $$n=2$$, we get using $$(a+b+c)^2=a^2+b^2+c^2+2(ab+bc+ca)$$ that $$a+b+c\mid 2(ab+bc+ca)$$. Also, for $$n=3$$, using $$a^3+b^3+c^3-3abc=(a+b+c)(a^2+b^2+c^2-ab-bc-ca)$$, we have $$a+b+c\mid 3abc$$. Next, note that, if $$9\mid a+b+c$$, then $$3\mid abc$$. Hence, either $$a$$ or $$b$$ or $$c$$ is divisible by $$3$$. Now, if $$3\mid a$$, then using $$a+b+c\mid 2(ab+bc+ca)$$, we obtain that $$3\mid bc$$, hence $$3\mid b$$ or $$3\mid c$$. However, this, together with $$3\mid a+b+c$$ contradicts with $$(a,b,c)=1$$. Hence, $$9\nmid a+b+c$$.

Similarly, if $$4\mid a+b+c$$, then note that among $$a,b,c$$ exactly one is even, suppose it is $$a$$, that is, $$4\mid a$$. But this gives, $$4\mid 2(ab+bc+ca)$$, yielding $$2\mid (ab+bc+ca)$$, yielding $$2\mid bc$$. However, since $$b$$ and $$c$$ are odd, this is a clear contradiction.

Thus, $$a+b+c=3$$ or $$a+b+c=6$$. In former, we get $$(1,1,1)$$, which is really $$n$$-good for any $$n$$. For the latter, we have $$(3,2,1)$$ or $$(4,1,1)$$. For the former, $$(3,2,1)$$ is not $$n-$$ good for any even $$n$$, using modulo $$3$$. For the latter, it is easy to see that it is $$n$$-good for any $$n$$.

Hence, we are done.

Note (Alternative) There is an alternative way of proving that $$a+b+c$$ can only admit $$2$$ or $$3$$ as its prime divisors. To see this, suppose $$p>3$$ divides $$a+b+c$$. Then, $$p\mid 3abc$$ implies $$p\mid abc$$. Using $$(a,b,c)=1$$, we see that exactly one of $$a,b,c$$ is divisible by $$p$$. Suppose, it is $$a$$. Then, $$p\mid ab+bc+ca$$, together with $$p\mid ab+ac$$ implies $$p\mid bc$$, which clearly is a contradiction. From here, one can finish in exact same way as in above proof, i.e., prove $$4,9\nmid a+b+c$$, and finish.

• It's a good answer, except for the minor point that the question says that $c \ge b \ge a$, so you need to reverse the order of your values, e.g., the largest result which works is $\left(a, b, c\right) = \left(1, 1, 4\right)$. – John Omielan Jan 11 at 4:33
• well, that requirement, as you can see from my proof, is completely redundant (and in fact, as far as I remember, does not even exist in the original problem statement). This is an old olympiad problem, circa 2005, from Canadian olympiad, where Bangladeshi's seem to have stolen from. – TBTD Jan 11 at 4:37
• Thanks for the info. I agree the condition is redundant, and I didn't realize it was an old Canadian Olympiad problem. – John Omielan Jan 11 at 4:41
• John, this was one of my favorites back when I was still in high school, around 2010. In fact it has a second part too, if you are interested: – TBTD Jan 11 at 4:42
• Find all triples, $(a,b,c)$ that are $2004$-good and $2005$-good, but not $2007$-good. – TBTD Jan 11 at 4:42

The question is to find the largest sum of $$a, b, c$$, given they're all relatively prime to each other and divide

$$a^n + b^n + c^n \text{ } \forall \text{ } n \ge 1 \tag{1}\label{eq1}$$

Since $$a, b, c \ge 1$$, then $$a + b + c \ge 3$$, so it consists of one or more prime factors. Call one of these prime factors $$d$$. Thus,

$$a + b + c \equiv a^n + b^n + c^n \equiv 0 \pmod d \tag{2}\label{eq2}$$

As this must hold for all $$n \ge 1$$, consider $$n = 3$$ and substitute

$$c \equiv -a - b \pmod d \tag{3}\label{eq3}$$

into the middle part of the congruence in \eqref{eq2} to get

$$a^3 + b^3 + \left(-a - b\right)^3 \equiv 0 \pmod d \tag{4}\label{eq4}$$

This simplifies to

$$-3ab^2 - 3a^2b = -3ab\left(a + b\right) \equiv 0 \pmod d \tag{5}\label{eq5}$$

Thus, $$d$$ must divide $$3$$, $$a$$, $$b$$ and/or $$a + b \equiv -c \pmod d$$. If $$d$$ is not $$3$$, then note that if it must divide just one of $$a$$, $$b$$ and $$-c$$. This is because if it divides any $$2$$, say $$a$$ and $$b$$, it must also divide $$c$$. As the equations are symmetric in $$a, b \text{ and } c$$, WLOG, assume that $$d$$ divides $$a$$, i.e., $$a \equiv 0 \pmod d$$. Thus, $$b + c \equiv 0 \pmod d$$, i.e., $$b \equiv -c \pmod d$$. Now, use $$n = 2$$ in the congruence in the middle part of \eqref{eq2} to get

$$a^2 + b^2 + c^2 \equiv 0 + \left(-c\right) + c^2 \equiv 2c^2 \equiv 0 \pmod d \tag{6}\label{eq6}$$

As $$d$$ doesn't divide $$c$$, this means that $$d$$ must divide $$2$$, i.e., it must be $$2$$. Thus, the only possible prime factors of $$a + b + c$$ are $$3$$, as mentioned earlier, and $$2$$ as shown here.

Based on what I have found here, I believe the maximum value is just the product of those $$2$$ factors, i.e., $$6$$, which can be obtained from

$$\left(a, b, c\right) = \left(1, 1, 4\right) \tag{7}\label{eq7}$$

You can easily verify that $$a^n + b^n + c^n = 1 + 1 + 4^n \equiv 0 \pmod 6$$ for all $$n \ge 1$$ as $$1 + 1 = 2$$, so $$2$$ divides it, and $$4^n \equiv 1^n \equiv 1 \pmod 3$$, so $$3$$ divides it as well. I am posting this partial solution for now so you have something to start from, as I believe I'm on the right track. I need to go for a while, but I will keep thinking about this and, if I determine the rest of the solution, I will add it later.