Euclidean Algorithm 
Gaussian integers
The Gaussian integers are complex numbers of the form \(a+bi\)
, with \(a\),
\(b\)
integers. (This set is denoted by \(\mathbb{Z}\left[i\right]\)). Here we don't have any usual order, and what is going to be used to compare two elements is their modulus or (which is equivalent and allows us to work only with integers) the square of their modulus.
For any \(a+bi\), with \(a\), \(b\) integers, let \(v(a+bi)=a^{2}+b^{2}\). We will see that, for every \(z,w\in\mathbb{Z}\left[i\right]\) with \(w\neq0\) there exist \(q,r\) such that: \[\left\{ \begin{array}{c} z=wq+r\\ v(r)<v(w) \end{array}\right.\] (the second condition is the generalization of the condition that the remainder is smaller than the divisor).
Given \(z=a+bi\) and \(w=c+di\), how can we look for \(q=q_{1}+q_{2}i\) and \(r=r_{1}+r_{2}i\) such that \(z=wq+r\) and \(v(r)<v(w)\)?
To look for \(q\) and \(r\) with these conditions is equivalent to looking for \(q=q_{1}+q_{2}i\) and \(r=r_{1}+r_{2}i\) such that \(a+bi=\left(c+di\right)\left(q_{1}+q_{2}i\right)+r_{1}+r_{2}i\), which is the same as: \[\frac{a+bi}{c+di}-\left(q_{1}+q_{2}i\right)=\frac{r_{1}+r_{2}i}{c+di},\] or \[\frac{\left(a+bi\right)\left(c-di\right)}{c^{2}+d^{2}}-\left(q_{1}+q_{2}i\right)=\frac{r_{1}+r_{2}i}{c+di},\]which is moreover the same as: \[\frac{ac+bd}{c^{2}+d^{2}}-q_{1}+\left(\frac{bc-ad}{c^{2}+d^{2}}-q_{2}\right)i=\frac{r_{1}+r_{2}i}{c+di}.\]
We want \(q_{1},q_{2},r_{1},r_{2}\) such that \(v\left(r_{1}+r_{2}i\right)<v\left(c+di\right)\) which is the same as \[\frac{v\left(r_{1}+r_{2}i\right)}{v\left(c+di\right)}<1,\] or we can check with some calculations that, \[\frac{v\left(r_{1}+r_{2}i\right)}{v\left(c+di\right)}=v\left(\frac{r_{1}+r_{2}i}{c+di}\right),\] hence it suffices that \[v\left(\frac{r_{1}+r_{2}i}{c+di}\right)<1.\]
Since \[\begin{array}{ccc} \frac{v\left(r_{1}+r_{2}i\right)}{v\left(c+di\right)} & = & v\left(\frac{ac+bd}{c^{2}+d^{2}}-q_{1}+\left(\frac{bc-ad}{c^{2}+d^{2}}-q_{2}\right)i\right)=\\ & = & \left(\frac{ac+bd}{c^{2}+d^{2}}-q_{1}\right)^{2}+\left(\frac{bc-ad}{c^{2}+d^{2}}-q_{2}\right)^{2} \end{array}\] it suffices that \[\left(\frac{ac+bd}{c^{2}+d^{2}}-q_{1}\right)^{2}+\left(\frac{bc-ad}{c^{2}+d^{2}}-q_{2}\right)^{2}<1.\]
Now, \[\frac{ac+bd}{c^{2}+d^{2}}\] and \[\frac{bc-ad}{c^{2}+d^{2}}\] are rational numbers; for every rational number, there exists an integer at a distance from it which is less or equal to \(\frac{1}{2}\) hence there exist integers \(q_{1}\) and \(q_{2}\) such that \[\left|\frac{ac+bd}{c^{2}+d^{2}}-q_{1}\right|<\frac{1}{2}\] and \[\left|\frac{bc-ad}{c^{2}+d^{2}}-q_{2}\right|<\frac{1}{2}.\]
What happens if we choose \(q_{1}\) and \(q_{2}\) in these conditions and we take \(q=q_{1}+q_{2}i\) and \(r=a+bi-\left(c+di\right)\left(q_{1}+q_{2}i\right)\left(=r_{1}+r_{2}i\right)\)?
We have \[\begin{array}{ccc} v\left(\frac{r_{1}+r_{2}i}{c+di}\right) & = & \left(\frac{ac+bd}{c^{2}+d^{2}}-q_{1}\right)^{2}+\left(\frac{bc-ad}{c^{2}+d^{2}}-q_{2}\right)^{2}\\ & \leq & \left(\frac{1}{2}\right)^{2}+\left(\frac{1}{2}\right)^{2}=\frac{1}{4}+\frac{1}{4}=\frac{1}{2}<1 \end{array}\]
We therefore have a quotient and a remainder in the desired conditions. (The situation is slightly different from that of the integers, because there may exist more then one \(q\) and one \(r\) such that \(z=wq+r\) and \(v(r)<v(w)\). In fact, it is frequent to have more than one choice for \(q_{1}\) and \(q_{2}\) such that \[\left(\frac{ac+bd}{c^{2}+d^{2}}-q_{1}\right)^{2}+\left(\frac{bc-ad}{c^{2}+d^{2}}-q_{2}\right)^{2}<1).\]
Having the division algorithm for the Gaussian integers, we can now use the Euclidean Algorithm to find a greatest common divisor.
We are sure that the algorithm ends after a certain number of steps because \(v\left(r_{1}\right)>v\left(r_{2}\right)>v\left(r_{3}\right)>...>0\), while the remainder is not zero.
The arguments to conclude that what we obtain is a greatest common divisor (greatest in the sense of being a common divisor which is a multiple of any other divisor) are exactly the same we have seen for the case of the integers.
