## Raised to the same power

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?

[SOLVED]

#### 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.

### Credit

This puzzle is taken from: