Let’s say that an ordered triple of positive integers (a, b, c) is n-powerful if:
- $a \le b \le c$,
- $gcd(a, b, c) = 1$ and
- $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.
Let $P_i = a^i + b^i + c^i$
Hint for part 2: Apply Newton's Identities.
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)$.