How to find all possible solutions to $a^2 + b^2 = 2^k$? I'm working on the following problem, this is for an introductory discrete mathematics class.
Find all possible solutions to the equation $a^2 + b^2 = 2^k, k\geq1$ and $a$ and $b$ positive integers.
I've observed that the following are answers:
$2^1 = 1^2 + 1^2$
$2^3 = 2^2 + 2^2$
$2^5 = 4^2 + 4^2$ or $2^5 = 2^4 + 2^4$
From that, there seems to be a pattern such as $2^{k+1}=2^k + 2^k$ for some even $k \geq 0$
I've also been able to observe that $k$ has to be odd. I've tried the following:
$k = 2l + 1$ for some $l$
$2^{2l+1} = a^2 + b^2$
$2^l.2 = a^2 + b^2$ Now, if I set $a=b$
$2.2^l = 2a^2$ <=> $2^l = a^2$
But I don't know how to prove that $a$ has to be equal to $b$
Also, in the case where $k$ is even:
$k=2l$ for some $l$
$2^{2l}$ = $a^2 + b^2$ Again, setting $a=b$
$2^{2l+1} = a^2$
$2^{(2l-1)/2} = a^2$ where $(2l-1)/2$ is not an integer.
But again, I don't know how to go about it when $a \neq b$.
Am I on the right path? Any tips or suggestions on how to go forward?
 A: easier than you think. If $a^2 + b^2$ is divisible by $4,$ then $a,b$ are both even. Easy to prove. Induction says if $a^2 + b^2$ is divisible by $16,$ then $a,b$ are both divisible by $4.$ If if $a^2 + b^2$ is divisible by $64,$ then $a,b$ are both divisible by $8.$ And so on.
Which means that there are just two cases to write up, with $n \geq 0,$
$$ a^2 + b^2 = 4^n,  $$
$$ a^2 + b^2 = 2 \cdot 4^n. $$
In both cases we can write
$$  a = 2^n t, \; \; \;  b = 2^n u  $$ and proceed
A: It seems you have at least detected the pattern of the solutions and are on the right path.
A useful fact about squares is that the square of an even number is (of course) a multiple of $4$, whereas the square of an odd number is $1$ plus a multiple of $8$. To see this note that $(2n+1)^2=4\cdot n\cdot(n+1)+1$ and one of $n$, $n+1$ is even.
So if $k>1$, what can we say about $a$ and $b$?


*

*If exactly one of them is odd, then $a^2+b^2$ is $1$ plus a multiple of $4$, whereas $2^k$ is a multiple of $4$; so this is impossible.

*If both are odd, then $a^2+b^2$ is $2$ plus a multiple of $8$, hence certainly not a multiple of $4$; again, this is impossible.

*Remains the case that $a$ and $b$ are both even. But then $(a/2)^2+(b/2)^2=2^{k-2}$ is a solution for a smaller $k$.


So once we have verified that $a^2+b^2=2^1$ has the only solution (in poisitive integers) $a=b=1$ and $a^2+b^2=2^2$ has no solutions, the above observatoins help us show (by induction) that 


*

*If $k$ is even, then $a^2+b^2=2^k$ has no solution in positive integers

*If $k$ is odd, then the only solution in positive integers is $a=b=2^{(k-1)/2}$

A: Your statement that $2^{k+1} = 2^k + 2^k$ is proven correct by the observation on the right-hand side that for any integer $c$, $c + c = 2c$. My first thought is that $a,b$ must have the same parity for this to ever work.
If both are even, let $a = 2A$ and $b = 2B$, so that $a^2 + b^2 = 4A^2 + 4B^2 = 4(A^2 + B^2)$. This factorization should help you.
If both are odd, let $a = 2k + 1$ and let $b = 2l + 1$, so that 
$$a^2 + b^2 = (2k+1)^2 + (2l+1)^2 = ...$$
Keep going and you should get something interesting with this. Hope that helps!
