ATRACTOR

O algoritmo de Euclides é baseado no algoritmo de divisão para inteiros positivos: para quaisquer inteiros positivos \(a,b\) (com \(b\neq0\)) existe um quociente \(q\) e um resto \(r\), com \(0\leq r<b\), tais que \(a=bq+r\).

Há outras situações em que temos algoritmos de divisão semelhantes. O objectivo é sempre dividir um dividendo \((a)\) por um divisor não nulo \((b)\), obtendo, quando \(a\) é múltiplo de \(b\), apenas um quociente \(q\) \((a=bq)\) e, quando não é, um quociente \(q\) e um resto \(r\) \((a=bq+r).\) Não impondo nenhuma condição sobre \(q\) e \(r\), o problema é trivial: basta escolher um \(q\) qualquer e depois é só tomar \(a-bq\) para \(r\). A questão é que não se quer um \(q\) e um \(r\) quaisquer: quer-se um quociente que seja "o melhor possível", isto é, que dê origem a um resto "menor" do que o divisor. No entanto, para que isto faça sentido, é preciso começar por decidir em cada caso como é que se vão comparar o divisor e o resto, isto é, quando é que se vai dizer que o resto é "menor" do que o divisor.

Exemplos:

1 - Polinómios

2 - Inteiros de Gauss \(\mathbb{Z}\left[i\right]\)

3 -\(\mathbb{Z}\left[\sqrt{2}\right]\) (é aconselhável ver primeiro o caso dos inteiros de Gauss)

4 - \(\mathbb{Z}\left[i\sqrt{5}\right]\)(é aconselhável ver primeiro o caso dos inteiros de Gauss)