Originally Posted by

**Opalg** Since N(2) = 4 and N(1–3i) = 10, we must start by dividing 1–3i by 2, getting $\displaystyle \tfrac12 - \tfrac32i$. We now want the closest Gaussian integer to that quotient. There are four possible choices here, and it doesn't matter which one we take: the real part could be 0 or 1, and the imaginary part could be –i or –2i. Let's take –i as the Gaussian integer closest to the quotient. Then the first step in the Euclidean algorithm will look like this:

$\displaystyle 1-3i = 2(-i) + (1-i)$ ... (–i is the Gaussian quotient, 1–i is the remainder).

For the next step of the algorithm, we must divide 2 by 1–i. But this time the quotient is a Gaussian integer, because 2 = (1–i)(1+i). So the remainder is 0, and the gcd of 2 and 1–3i is the last nonzero remainder, namely 1–i.