# Prove: $2^k$ is the sum of two perfect squares

If $k$ is a nonnegative integer, prove that $2^k$ can be represented as a sum of two perfect squares in exactly one way. (For example, the unique representation of $10$ is $3^2+1^2$; we do not count $1^2+3^2$ as different.)

I understand that $2^{2n}=0+2^{2n}$ and $2^{2n+1}=2^{2n}+2^{2n}$. But how can we prove that $2^k$ can be represented as two perfect squares in exactly one way?

## 3 Answers

Use induction.

Note that if $$x^2+y^2=2^k\ (\text{where } k \geq 2)$$

If $x \equiv 1 \pmod 2$, then from $x^2+y^2 \equiv 0 \pmod 2$ we get $y \equiv 1 \pmod 2$.

However, then $$x^2+y^2 \equiv 1+1 \equiv 2 \pmod 4$$ A contradiction.

Thus, $x=2x_{1}, y=2y_{2}$. Thus $x_1^2+y_1^2 =2^{k-2}$.

I do not see anyone mentioning this simple aspect: if we have integers $u,v$ such that $$u^2 + v^2 \equiv 0 \pmod 4,$$ then both $u,v$ must be even.

Which means this: take a number that is divisible by $4.$ Suppose we have $$x^2 + y^2 = n$$ Keep dividing $n$ by $4$ until the result, $n_0,$ is no longer divisible by $4.$ We have $$x^2 + y^2 = 4^k n_0,$$ where $x = 2^k x_0$ and $y = 2^k y_0.$ $$x_0^2 + y_0^2 = n_0.$$

For you, either $n_0 = 1,$ written only as $1^2 + 0^2 = 1,$ or $n_0 = 2,$ written only as $1^2 + 1^2 = 2.$

Suppose $2^{2n+1}$ is the smallest odd power of two that can represented in more than one way as the sum of two squares.

Then $2^{2n+1} =(2^{n}+a)^2+(2^{n}-b)^2$ where $1 \le a < 2^n$ and $1 \le b < 2^n$.

Then

$\begin{array}\\ 2^{2n+1} &=(2^{n}+a)^2+(2^{n}-b)^2 \qquad(0)\\ &=2^{2n}+a2^{n+1}+a^2+2^{2n}-b2^{n+1}+b^2\\ \text{or}\\ (b-a)2^{n+1} &=a^2+b^2 \qquad(1)\\ \text{or}\\ b(2^{n+1}-b) &=a(2^{n+1}+a) \qquad(2)\\ \end{array}$

From $(0)$, $a$ and $b$ must be even, otherwise the right side is $\equiv 2 \bmod 4$.

Suppose $2^k || a$, so that $2^k | a$ and $2^{k+1}\not\mid a$. Then $2^{2k}||a(2^{n+1}+a)$ so $2^{2k}||b(2^{n+1}-b)$.

If $2^j || b$, reasoning as for $a$, $2^{2j} ||b(2^{n+1}-b)$.

Therefore $j=k$, so that $a=2^kc$ and $b = 2^kd$ where $c$ and $d$ are odd.

Substituting in $(2)$, $2^kd(2^{n+1}-2^kd) =2^kc(2^{n+1}+2^kc)$ or $d(2^{n+1-k}-d) =c(2^{n+1-k}+c)$ or $0 =2c2^{n-k}+c^2-2d2^{n-k}+d^2$ or

$\begin{array}\\ 2^{2(n-k)+1} &=2^{2(n-k)}+2c2^{n-k}+c^2+2^{2(n-k)}-2d2^{n-k}+d^2\\ &=(2^{(n-k)}+c)^2+(2^{(n-k)}-d)^2\\ \end{array}$

Therefore, a smaller odd power of $2$ can be represented in more than one way as the sum of two squares.

But this contradicts $2^{2n+1}$ being the smallest such odd power.

Therefore $2^{2n+1}$ can only be represented in one way as the sum of two squares.

This feels good!

This is the first time I have independently constructed a proof by infinite descent.

Maybe I'll try even powers, but this is enough for now.

• There is a very simple approach by descent. I put an answer. – Will Jagy Mar 26 '16 at 1:53