Algoritmo de Euclides 
Os inteiros de Gauss
Os inteiros de Gauss são
os números complexos da forma \(a+bi\)
, com \(a\),
\(b\)
inteiros. (Este conjunto representa-se por \(\mathbb{Z}\left[i\right]\)). Aqui não temos nenhuma relação de ordem habitual,
e o que vai ser usado para comparar dois elementos é o seu módulo
ou (o que é equivalente e permite trabalhar só com números
inteiros) o quadrado do seu módulo.
Para qualquer \(a+bi\), com \(a\), \(b\) inteiros, seja \(v(a+bi)=a^{2}+b^{2}\). Vamos ver que, para qualquer \(z,w\in\mathbb{Z}\left[i\right]\) com \(w\neq0\) existem \(q,r\) tais que: \[\left\{ \begin{array}{c} z=wq+r\\ v(r)<v(w) \end{array}\right.\] (a segunda condição é a generalização da condição de o resto ser menor do que o divisor).
Dados \(z=a+bi\) e \(w=c+di\), como podemos procurar \(q=q_{1}+q_{2}i\) e \(r=r_{1}+r_{2}i\) tais que \(z=wq+r\) e \(v(r)<v(w)\)?
Procurar \(q\) e \(r\) nestas condições equivale a procurar \(q=q_{1}+q_{2}i\) e \(r=r_{1}+r_{2}i\) tais que \(a+bi=\left(c+di\right)\left(q_{1}+q_{2}i\right)+r_{1}+r_{2}i\), o que é o mesmo que: \[\frac{a+bi}{c+di}-\left(q_{1}+q_{2}i\right)=\frac{r_{1}+r_{2}i}{c+di},\] ou ainda \[\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},\] o que ainda é o mesmo que: \[\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}.\]
Queremos \(q_{1},q_{2},r_{1},r_{2}\) tais que \(v\left(r_{1}+r_{2}i\right)<v\left(c+di\right)\) o que é o mesmo que \[\frac{v\left(r_{1}+r_{2}i\right)}{v\left(c+di\right)}<1,\] ou pode-se verificar com algumas contas que, \[\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),\] portanto basta que \[v\left(\frac{r_{1}+r_{2}i}{c+di}\right)<1.\]
Como \[\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}\] basta que \[\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.\]
Ora, \[\frac{ac+bd}{c^{2}+d^{2}}\] e \[\frac{bc-ad}{c^{2}+d^{2}}\] são números racionais; para qualquer número racional, existe um número inteiro a uma distância menor ou igual que \(\frac{1}{2}\) dele, portanto existem \(q_{1}\) e \(q_{2}\) inteiros tais que \[\left|\frac{ac+bd}{c^{2}+d^{2}}-q_{1}\right|<\frac{1}{2}\] e \[\left|\frac{bc-ad}{c^{2}+d^{2}}-q_{2}\right|<\frac{1}{2}.\]
O que acontece se escolhermos \(q_{1}\) e \(q_{2}\) nessas condições e tomarmos \(q=q_{1}+q_{2}i\) e \(r=a+bi-\left(c+di\right)\left(q_{1}+q_{2}i\right)\left(=r_{1}+r_{2}i\right)\)?
Temos \[\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}\]
Temos então um quociente e um resto nas condições desejadas. (A situação é ligeiramente diferente da dos números inteiros, porque podem existir mais do que um \(q\) e um \(r\) tais que \(z=wq+r\) e \(v(r)<v(w)\). De facto, é frequente haver mais do que uma escolha de \(q_{1}\) e \(q_{2}\) tais que \[\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).\]
Tendo o algoritmo da divisão para os inteiros de Gauss, podemos agora usar o Algoritmo de Euclides para achar um máximo divisor comum.
Temos a certeza que o algoritmo acaba ao fim de um certo número de passos porque \(v\left(r_{1}\right)>v\left(r_{2}\right)>v\left(r_{3}\right)>...>0\), enquanto o resto não é zero.
Os argumentos para concluir que o que se obtém é um máximo divisor comum (máximo no sentido de ser um divisor comum que é múltiplo de todos os outros divisores) são exactamente os mesmos que foram vistos no caso dos números inteiros.
