Instead of adjoining the square root of -1, as we did to build the gaussian integers, let's adjoin the square root of -2. Let q be the square root of -2, not to be confused with i, the square root of -1. In the complex plane, q is the point on the imaginary axis approximately 1.414 units up from the origin. Move one unit to the right to find 1+q, one unit to the left to find -1+q, and so on. This extension creates a regular grid, a lattice in the plane, but this time the grid defines rectangles, rather than squares. Each rectangle is almost half again as tall as it is wide.

Recall that the gaussian integers had a norm, the square of the distance from the origin. This norm is still valid, and still commutes with multiplication. This makes sense, since the norm is valid over the entire complex plane.

The norm of x+yq is x2+2y2. Once again it is a positive integer, so an element with a prime norm is necessarily prime. The only elements with a norm of 1 are ±1, hence these are the only units.

Ok, time to try out the gcd algorithm. We have two numbers to compare, two vectors in the complex plane. Let the shorter one be 10. This use to define a large checkerboard in the plane, whose corners were marked by 10 times all the gaussian integers. Well it still makes a regular pattern in the plane, but now the cells are rectangles. Ten times the integers produces multiples of ten along the x axis, and ten times the integers times q produces multiples of 14.14 up the y axis. Ten times every possible x+yq produces a grid in the complex plane.

The longer vector lands somewhere in one of these rectangular cells, and if we're lucky, we can subtract one of the corners and make progress. This produces the remainder when the longer vector is divided by the shorter, and it must contain the factors common to both.

Once again we are smiling, because the remainder is less than the shorter vector. Even if the longer vector lands smack in the middle of a rectangle, it is still closer to a corner than the width of the rectangle, which is the shorter vector. Thus the numbers get smaller with each step.

Most of the time the shorter vector points into one of the four quadrants, rather than along an axis, and the grid seeded by this vector is tilted relative to the axes, but that doesn't cause any trouble. The longer vector is still inside a tilted rectangular cell, and we can subtract one of the four corners, find another, shorter vector, and make progress.

The gcd algorithm works, and once again we have unique factorization.