Consider the vectors x, ix, jx, and kx. These are the positive left associates of x, or if you prefer, the action of x on the basis 1,i,j,k. Verify that the four image vectors are orthogonal, hence they span a perfect hypercube in 4 space. The volume of this cube is |x|2. This was discussed in an earlier section.
Since the basis is mapped onto a hypercube, the left multiples of x span a regular lattice in 4 space. The entire space is filled with cubes, just like the base cube, same size, same orientation. This is similar to tiling the plane with a checkerboard, or filling 3 space with cubes, but of course we are working in four dimensions.
Determine which cube contains y and locate the closest vertex to y. In other words, divide y by x and round to the nearest integer quaternion. Subtract this closest vertex, wx for some w, to get a new vector z. Thus z = y-wx.
If x and y are both left multiples of g, say x = sg and y = tg, then z = (t-ws)g, and z is a left multiple of g. Replace y with x and x with z, which has smaller norm. Repeat until z = 0, then set g = x, thus producing the gcd of x and y. Backtrack, and x and y are both left multiples of g. If you're not familiar with the original gcd algorithm, click here.
Let x and y be left multiples of some other quaternion h. Step through the algorithm again, until the last x, which becomes g, hence g is also a left multiple of h. Every right divisor of x and y is a right divisor of g, and g is inddeed the right gcd of x and y. Note that x and y have a left gcd as well, which might be different.
There is a catch however; y might occupy the exact center of a hypercube spanned by the vector x. In this case y is just as far from the 16 vertices as they are from each other. We may replace x with the difference vector z, but its norm doesn't get any smaller. We haven't made any progress. The gcd algorithm is caught in an infinite loop. What can we do?
Add a point to the center of each hypercube in 4 space. This gives the ring of half integer quaternions, as described in the previous section. Now, if y isn't close to one of the 16 vertices, it is certainly near the center. Subtract the closest lattice point, and z is definitely smaller than y. In the half quaternions, x and y have a well defined right gcd, which we will call g. If g consists of half integers, find a left associate with whole integers. Now g is an integer quaternion that spans x and y. At worst we may have to multiply by a half unit to get to x or y.
Like Euclid's original algorithm, g can be expressed as a left linear combination of x and y. After each step, the new element is a linear combination of the previous two. Start with g and back substitute, until you find the linear combination of x and y that spans g. Again, we may have to use half integer coefficients on x or y, to get back to g.
Let g be the right gcd of any two of these generators. It spans, and is spanned by the original two generators, so we can replace them with g. Repeat until the ideal is generated by a single element. Of course we may have to include the half integer units, if g is to span 2x and x×(1+i+j+k) simultaneously. So we almost have a pid.
The half integer quaternions definitely form a pid.