Sum of two odd squares What is the characterization of numbers expressible as a sum of two odd squares? I showed that it must be congruent to $2$ mod $4$, but obviously this is insufficient since not all numbers $2$ mod $4$ can be written this way.
 A: Analyzing this question, I came to the startling discovery:
If we define $S(X)$ as "X is the sum of two squares", then, for any integer $X$,
$$
S(X) \iff S(2X)
$$
We'll get back to that later.  For this question, we have $X = a^2 + b^2$, where $a$ and $b$ are odd integers.
Let
$$
c = {a + b\over 2}\\
d = {a - b\over 2}
$$
Since $a$ and $b$ are both odd, $c$ and $d$ must both be integers.  (We don't care if $d$ is negative, because $d^2 = (-d)^2 = |d|^2$.)  Furthermore, since $a = c + d$, one of $c, d$ must be odd, and the other even.
Now to calculate:
$$
\begin{align}
c^2 + d^2 &= \left({a+b\over 2}\right)^2 + \left({a-b\over 2}\right)^2\\
&= {1\over 4}(a^2 + 2ab + b^2 + a^2 - 2ab + b^2)\\
&= {1\over 2}(a^2 + b^2)
\end{align}
$$
So, if $X = a^2 + b^2$ with both $a, b$ odd, then $X = 2(c^2 + d^2)$ with one of $c,d$ odd and the other even.
If $c$ is odd, then $c = 2i+1$ and
$$c^2 = 4i^2 + 4i + 1 = 4i(i+1) + 1 \equiv 1 \mod 4$$
If $d$ is even, then $d = 2j$ and 
$$d^2 = 4j^2 \equiv 0 \mod 4
$$
So 
$$X = 2 (c^2 + d^2) \equiv 2 \mod 8$$
Thus, the answer to your question: if $X$ is the sum of two odd squares, then $X \equiv 2 \mod 8$.
To continue with the proof of my original conjecture:
Whenever $X = a^2 + b^2$, we can let $e = a + b$, $f = a-b$, and
$$
e^2 + f^2 = (a^2 + 2ab + b^2) + (a^2 - 2b + b^2) = 2(a^2 + b^2) = 2X
$$
Thus, we have shown $S(x)\implies S(2X)$.
If $S(2X)$, then $2X$ (being even) must the the sum of two odd squares or two even squares:
$2X = e^2 + f^2$.  We can do as above:
$$
a = {e+f\over 2}\\
b = {e-f\over 2}
$$
And we have $X = a^2 + b^2$.  Since $e, f$ are both odd or both even, $a, b$ must both be integers.
Thus, $S(2X) \implies S(X)$ for any integer $X$.
As shown above, if $X$ is an odd number that is the sum of two squares, then we must have $X \equiv 1 \mod 4$.  Thus, if $X \equiv 3 \mod 4$, then $X$ cannot be the sum of two squares.  Combine this with the above:
$$
\neg S(X) \implies \exists i,j \mid X = (4i+3)\cdot 2^j
$$
Any integer that is not the sum of two squares is of the form $(4i+3)\cdot 2^j$.
