Does the product of two numbers with a primitive representation have a primitive representation?

I know the theorem that $n = x^2 + y^2, \, \textrm{gcd}(x, y) = 1 \iff p | n \implies p \equiv 1 \bmod 4$. We call an expression of $n$ in this form primitive.

I'm trying to prove the statement. I've shown that if $p \mid n$ and $p \equiv 3 \bmod 4$ then $n$ has no primitive representation. Now I want to show the reverse direction, i.e. if $p \mid n \implies p \equiv 1 \bmod 4$ then $n = x^2 + y^2, \, \textrm{gcd}(x,y)=1$.

The strategy I'm currently exploring is to show that all primes which are $1 \bmod 4$ and their powers have primitive representations. I can do this. However, next I want to show that the product of two numbers with primitive representations also has a primitive representation. Let $m = a^2 + b^2; n = c^2 + d^2$ be two such numbers with respective primitive representations. Then I know $mn = (ac + bd)^2 + (ad - bc)^2$. I want to see if the terms on the RHS have $\textrm{gcd} = 1$, but I'm having trouble doing this.

Any help on my general approach or with this specific part would be nice. Thank you.

• In case you weren't aware, there's a relevant theorem by Fermat: en.wikipedia.org/wiki/Fermat%27s_theorem_on_sums_of_two_squares – user236182 Feb 12 '16 at 9:37
• Thank you for the link. I'm familiar with this particular theorem and I used one of its proofs to come up with a similar proof for why every prime that is 1 mod 4 has a primitive representation. I was not able to use the theorem directly to show that n has a primitive representation. – user83387 Feb 12 '16 at 9:42
• Those terms need not have gcd $1$; e.g. $10=3^2+1^2, 5=1^2+2^2,3\cdot 1+1\cdot 2 = 5, 3\cdot 2 - 1\cdot 1 = 5.$ So you need to nuance your statement a bit. – John Brevik Feb 12 '16 at 10:32
• Possible duplicate of Sum of two squares $n = a^2 + b^2$ – Dietrich Burde Feb 12 '16 at 15:39
• This is not a duplicate due to the gcd condition. – user83387 Feb 12 '16 at 15:57