4
$\begingroup$

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.

Source: Bangladesh Math Olympiad 2017 junior category (Originally from Canada, 2005).

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

$\endgroup$
  • 2
    $\begingroup$ 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$. $\endgroup$ – kingW3 Jan 11 at 2:04
  • $\begingroup$ Could you please explain if there is any valid solution of this question? $\endgroup$ – Shromi Jan 11 at 3:01
  • $\begingroup$ @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. $\endgroup$ – John Omielan Jan 11 at 3:10
  • $\begingroup$ @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$. $\endgroup$ – John Omielan Jan 11 at 4:08
  • $\begingroup$ @JohnOmielan, yes, I miss that part $\endgroup$ – Lee Jan 11 at 4:09
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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)$. $\endgroup$ – John Omielan Jan 11 at 4:33
  • $\begingroup$ 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. $\endgroup$ – TBTD Jan 11 at 4:37
  • $\begingroup$ Thanks for the info. I agree the condition is redundant, and I didn't realize it was an old Canadian Olympiad problem. $\endgroup$ – John Omielan Jan 11 at 4:41
  • $\begingroup$ 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: $\endgroup$ – TBTD Jan 11 at 4:42
  • $\begingroup$ Find all triples, $(a,b,c)$ that are $2004$-good and $2005$-good, but not $2007$-good. $\endgroup$ – TBTD Jan 11 at 4:42
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.