<s>[INST] 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?
 [/INST] 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}$

</s>