Square roots of Gaussian integers

In previous post I showed how to compute the square root of a complex number. I gave as an example that computed the square root of 5 + 12i to be 3 + 2i.

(Of course complex numbers have two square roots, but for convenience I'll speak of the output of the algorithm as the square root. The other root is just its negative.)

I chose z = x + iy in my example so that x^2 + y^2 would be a perfect square because this simplified the exposition.That is, I designed the example so that the first step would yield an integer. But I didn't expect that the next two steps in the algorithm would also yield integers. Does that always happen or did I get lucky?

It does not always happen. My example was based on the Pythagorean triple (5, 12, 13). But (50, 120, 130) is also a Pythagorean triple, and the square root of z = 50 + 130i does not have integer real and imaginary parts.

At this point it will help to introduce a little terminology. A Gaussian integer is a complex number with integer real and imaginary parts. We could summarize the discussion above by saying the square root of 5 + 12i is a Gaussian integer but the square root of 50 + 120i is not.

While (5, 12, 13) and (50, 120, 130) are both are Pythagorean triples, only the first is a primitive Pythagorean triple, one in which the first two components are relatively prime. So maybe we should look at primitive Pythagorean triples.

There is a theorem going all the way back to Euclid that primitive Pythagorean triples have the form

(m^2 - n^2, 2mn, m^2 + n^2)

where m and n are relatively prime integers and one of m and n is even.

Using the algorithm in the previous post, we can show that if x and y are the first components of a triple of the form above, then the square root of the Gaussian integer x + iy is also a Gaussian integer. Specifically we have

= m^2 + n^2
u = ((m^2 + n^2 + m^2 - n^2)/2) = m
v = sign(y) ((m^2 + n^2 - m^2 + n^2)/2) = sign(y) n

This means u and v are integers and so the square root of x + iy is the Gaussian integer u + iv.

There is one wrinkle in the discussion above. Our statement of Euclid's theorem left out the assumption that we've ordered the sides of our triangle so that the odd side comes first. Primitive Pythagorean triples could also have the form

(2mn, m^2 - n^2, m^2 + n^2)

and in that case our proof would break down.

Surprisingly, there's an asymmetry between the real and imaginary parts of the number whose square root we want to compute. It matters that x is odd and y is even. For example, (5 + 12i) is a Gaussian integer but (12 + 5i) is not!

So a more careful statement of the theorem above is that if x and y are the first two components of a primitive Pythagorean triple, the square root of x + iy is a Gaussian integer.