2
$\begingroup$

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.

$\endgroup$
1
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Marconius
    Aug 24 '15 at 22:28

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.