# Ordered triples of n-powerful integers

Let’s say that an ordered triple of positive integers (a, b, c) is n-powerful if:

1. $a \le b \le c$,
2. $gcd(a, b, c) = 1$ and
3. $a^n + b^n + c^n$ is divisible by $a + b + c$.

For example, $(1, 2, 2)$ is 5-powerful.

a) Determine all ordered triples (if any) which are n-powerful for all $n \ge 1$.

b) Determine all ordered triples (if any) which are 2004-powerful and 2005-powerful, but not 2007-powerful.

This question is taken from the 2005 Canada National Olympiad.

I have established some results, but these are not of (much) direct relevance to the questions asked.

Let:

• $P^n$ be the set of all n-powerful triples
• $s=a+b+c$
• $\mathbb{P}$ be the set of all primes
• $p$ be an odd prime

By the binomial theorem, \begin{align} a^n+b^n+c^n&=a^n+b^n+\Big(s-(a+b)\Big)^n \\ &\equiv a^n+b^n+(-1)^n(a+b)^n\pmod{s} \tag{1} \end{align}

## Part (a)

Possibly the simplest solution is $\boxed{n=s\in\mathbb{P}_{>2}}$. Any triple satisfying this and the gcd condition is n-powerful, e.g. $(1,4,6)\in P^{11}$.

Suppose we have $4\mid s,n\text{ even}$

Then $a^n\equiv 0,1\pmod{4},b^n\equiv 0,1\pmod{4},\text{ and }(a+b)^n\equiv 0,1\pmod{4}$ so for n-power (1) requires that $a,b$ are both even, so that $gcd(a,b,c)>1$. So then $(a,b,c)$ is not n-powerful.

Therefore $$\boxed{n\text{ even}\implies 4\nmid s}$$

For $n \ge 3,1\le a\le b$ we have \begin{align} (a+b)^n &\ge a^n+b^n + na^{n-1}b + nab^{n-1}\\ &\ge a^n+b^n+6ab \\ &> a^n+b^n+(a+2b) \end{align} For $n=2$, the RHS (1) exceeds $(a+2b)$. The requirement $1\le a \le b \le c$ implies only that $1\le a \le b \land s \ge a+2b$. So as long as $a,b$ are chosen such $1\le a \le b$ and $gcd(a,b)=1$ then we can find at least one $s$ satisfying (1) with $s\ge a+2b$, giving the triple $(a,b,s-a-b)$.

Suppose now that $n=ks$ with $k$ a positive integer and $s$ an odd prime.

Then we have by Fermat's Little Theorem:

\begin{align} a^n \equiv (a^s)^k \equiv a^k\pmod{s} \tag{2}\\ b^n\equiv b^k\pmod{s} \tag{3} \end{align}

In addition, since $s$ is prime, we have \begin{align} (a+b)^n=\Big((a+b)^s\Big)^k&\equiv(a^s+b^s)^k\pmod{s}&\left(s\mid\binom{s}{j}\text{ for }1\le j\le s-1\right) \\ &\equiv(a+b)^k\pmod{s}&(\text{by Fermat's Little}) \end{align} Trivially, $$(-1)^n=(-1)^k$$

So then (1) reduces to:

$$a^n+b^n+c^n\equiv a^k+b^k+(-1)^k(a+b)^k\pmod{s} \tag{4}$$

which is of the same form as (1).

This gives a recipe for generating higher-power n-powerful triples from lower-power ones. For example,

• $1^2+2^2+4^2 \equiv 0\pmod7 \mapsto 1^{14}+2^{14}+4^{14}\equiv1+4+16\equiv0\pmod7$
• i.e. $(1,2,4)\in P^2 \mapsto (1,2,4)\in P^{14}$

I cannot see how to take these ideas further.

## Part (b)

If $(a,b,c)$ is both 2004-powerful and 2005-powerful then we require simultaneously that:

\begin{align} a^{2004}+b^{2004}+(a+b)^{2004}&\equiv0\pmod{s} \\ a^{2005}+b^{2005}-(a+b)^{2005}&\equiv0\pmod{s} \end{align}

We can clear the $(a+b)^n$ term by multiplying the first equation through by $(a+b)$ and adding to the second equation to get:

$$(a+b)(a^{2004}+b^{2004})+a^{2005}+b^{2005}\equiv0\pmod{s}$$

but this seems to lead nowhere.

• Aug 21 '15 at 18:24

Let $P_i = a^i + b^i + c^i$
Show that $P_{2007} = A P_{2004} + B P _{2005} + C (a+b+c)$ where $A,B,C$ are constants to be determined.
Not sure about part 1 as yet, but there are solution sets of $(1,1,1)$ and $(1,1,4)$.
• Thanks Calvin. So for part 2, it depends on whether $A, B$ are integers. If so, it is impossible for $(a+b+c)\mid P_{2004}$ and $(a+b+c)\mid P_{2005}$ without also having $(a+b+c)\mid P_{2007}$. Oh, and that really is a brilliant website. Aug 24 '15 at 22:28