Two given positive integers are raised to the same power and added. The power to which they are raised is an integer greater than 1. The sum is a power of 2. What is the maximum possible difference between the two given integers?

Sunday, April 8, 2012

Please email your solutions to puzzles@cotpi.com.

### 2 comments

### Credit

This puzzle is taken from:

- Hobson, Nick. "Solution to puzzle 142: Sum of two nth powers." Nick's Mathematical Miscellany. 29 Oct. 2006. 15 Apr. 2012 <http://www.qbyte.org/puzzles/p142s.html>.

## Hagen von Eitzen solved this puzzle:

The maximum possible difference is zero as follows from the theorem below. \(\newcommand{\N}{\mathbb{N}}\).

Theorem.Let \(a, b \in \N\), \(n, k \in \N_0\) such that \(a^n + b^n = 2^k\). Then \(n<2\) or \(a=b\).Proof.Assume otherwise and let \((a, b, n, k)\) be a counterexample with minimal value of \(a\). Then at least one of \(a\) and \(b\) is greater than \(1\), and \(a^n + b^n \ge 2^n + 1\), hence \(k \gt n\) and especially \(k \ge 3\). It follows that \(a^n\) and \(b^n\) have the same parity. Since \(n > 0\), this implies that \(a\) and \(b\) also have the same parity.Assume that both \(a\) and \(b\) are even. Then \( \left( \frac{a}{2} \right)^n + \left( \frac{b}{2} \right)^n = 2^{k - n}\), i.e. \(\left( \frac{a}{2}, \frac{b}{2}, n, k - n \right)\) would be a smaller counterexample. We conclude that both \(a\) and \(b\) are odd.

Assume that \(n\) is even. Then \(a^n\) and \(b^n\) are squares of odd numbers, hence \(a^n\equiv b^n\equiv 1\pmod 8\) and their sum is \(a^n+b^n\equiv 2\pmod 8\). On the other hand, \(k\ge3\) implies \(2^k\equiv 0 \pmod 8\) — a contradiciton. Therefore \(n\) must be odd.

The odd residue classes modulo \({2^k}\) form a group under multiplication. Since the odd number \(n\) is relatively prime to the group order \(\phi\left(2^k\right)=2^{k-1}\), the homomorphism of taking \(n\)th powers has trivial kernel. This means that it is an injective map, i.e. \((-a)^n = -a^n\equiv b^n \pmod{2^k}\) implies \(-a\equiv b\pmod{2^k}\). It follows that \(a+b\) is a positive multiple of \(2^k\). Since \(n>1\) and at least one of \(a,b\) is greater than 1, we finally arrive at the contradiction \( 2^k = a^n + b^n > a + b \ge 2^k \).

## quasi solved this puzzle:

Zero.

Theorem.If \(x^n + y^n = 2^k\) where \(x, y, n\) and \(k\) are positive integers, and \(n \gt 1\), then \(x = y\).Proof.If \(k = 1\), \(x^n + y^n = 2 \implies x^n = y^n = 1 \implies x = y = 1 \implies n = 0\), a contradiction to the assumption that \(n \gt 1\). If \(k = 2\), \(x^n + y^n = 4 \implies n = 1\), a contradiction again.Assuming there is a counterexample, choose one with \(k\) as small as possible. Necessarily, \(k \ge 3\). Then \(x^n + y^n = 2^k\) imples that \(x\) and \(y\) have the same parity. But if \(x\) and \(y\) are both even, we get

\begin{align*} \left( \frac{x}{2} \right)^n + \left( \frac{y}{2} \right)^n = 2^{k - n}. \end{align*}

Since \(\frac{x}{2}\) and \(\frac{y}{2}\) are positive integers, \(k - n\) must also be a positive integer, but then the above equation would give a counterexample with a smaller power of \(2\), contrary to choice of \(k\). Thus, \(x\) and \(y\) are both odd.

Suppose first that \(n\) is even. Since \(k \ge 3\), we have

\begin{align*} x^n + y^n \equiv 0 \pmod{8} \end{align*}

which is impossible since \(x^n\) and \(y^n\) would be odd squares, and odd squares are congruent to \(1 \pmod{8}\). Hence \(n\) is odd.

Factoring \(x^n + y^n\), we get \(ab = 2^k\) where \(a = x + y\) and \(b = x^{n-1} + x^{n-2} y + \dots + x y^{n-2} + y^{n-1}\). Note that \(b\) is the sum of \(n\) terms, each of which is odd. Since \(n\) is odd, \(b\) is odd. But \(b\) is a factor of \(2^k\), hence \(b = 1\). But then \(x^n + y^n = ab = a = x + y\). Now \(x\) and \(y\) are not both \(1\) because \(k \ge 3\). Without loss of generality, assume \(y > 1\). But then \(x \le x^n\) and \(y \lt y^n\), which yields \(x + y \lt x^n + y^n\), a contradiction. Hence there can't be a counterexample.