Show that any non-negative rational integer may be written as the sum of two squares if it is of the form.... 
Show that any non-negative rational integer may be written as the sum of two squares if it is of the form $$2^ip_1^{k_1}p_2^{k_2}\cdots p_m^{k_m}q_1^{2j_1}q_2^{2j_2}\cdots q_n^{2j_n}$$ where the $p_1,p_2,\dots,p_m$ are all primes congruent to $1\bmod 4$, the $q_1,q_2,\dots,q_n$ are all primes congruent to $3\bmod 4$ and $i,k_1,k_2,\dots,k_m,j_1,j_2,\dots,j_n$ are all non-negative integers.

I am completely blank on how to form a solution, so help would be much appreciated.
 A: first of all a rather trivial point: a square is a sum of two squares (of which usually one will need to be $0^2$)
now you need a lemma: if $a$ is a sum of two squares and $b$ is a sum of two squares, then the product $ab$ is also a sum of two squares. 
this is easy to see in terms of the multiplication of two Gaussian integers:
$$
(a^2+b^2)(c^2+d^2)=|a+ib|^2|c+id|^2=|(a+ib)(c+id)|^2=|(ac-bd)+i(ad+bc)|^2=(ac-bd)^2+(ad+bc)^2
$$
since $2=1^2+1^2$ the lemma implies any power of two is a sum of two squares. 
a well-known theorem tells us that any prime of the form $4n+1$ is the sum of two squares, so the lemma implies that any product of such primes $p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m}$ is a sum of two squares.
finally to multiply a sum of two squares by a square (of the form $q_1^{2j_1}q_2^{2j_2}\cdots q_n^{2j_n}$) is again a sum of two squares.
the proof of the theorem about primes of the form $4n+1$ is a fairly easy consequence of two basic results: Wilson's theorem and the fact that the Gaussian integers are a Euclidean ring and therefore are a  Unique Factorization Domain. Wilson's theorem is a simple exercise in modular arithmetic. To demonstrate a division algorithm for the Gaussian integers is a little more technical but of an elementary nature. 
A: By the Brahmagupta–Fibonacci identity, the product of two sums of two squares is a sum of two squares, so it suffices to prove that $2$, each $p_i$, and each $q_i^2$ is a sum of two squares. Obviously $q_i^2=q_i^2+0^2$ is a sum of two squares, and $2=1^2+1^2$.
Thus we are reduced to the case of proving that if $p\equiv 1\pmod4$ is a prime number, then $p$ is a sum of two squares. This is not a simple theorem; an exposition can be found at Theorem 4 here.

Although the original theorem doesn't say it, the statement is a bit complicated if the only goal is the forward direction. In fact, the stated form covers all numbers that are sums of two squares. To see this, given $n$ which is a sum of two squares, take its prime factorization and partition the primes into $2$, $p_i\equiv1$, and $q_i\equiv3\pmod 4$. Then we need only prove that the exponent of each $q_i$ is even, and we may assume additionally that all smaller sums of two squares are of the given form.
If $q_i\mid n=a^2+b^2$, then in $\Bbb Z[i]$ we have $q_i\mid(a-bi)(a+bi)$, so $q_i\mid a-bi$ or $q_i\mid a+bi$, and in both cases $q_i\mid a$ and $q_i\mid b$. Then $q_i^2\mid a^2+b^2=n$, so $$n/q_i^2=2^ip_1^{k_1}\cdots p_m^{k_m}q_1^{j_1}\cdots q_i^{2j_i}\cdots q_n^{2j_n},$$ and then $$n=2^ip_1^{k_1}\cdots p_m^{k_m}q_1^{2j_1}\cdots q_i^{2(j_i+1)}\cdots q_n^{2j_n}.$$
