ATRACTOR

The Euclidean algorithm is based on the division algorithm for positive integers: for any two positive integers \(a,b\) (with \(b\neq0\)) there exist a quotient \(q\) and a remainder \(r\), with \(0\leq r<b\), such that \(a=bq+r\).

There are other situations where we have similar division algorithms. The goal is always to divide a dividend \((a)\) by a non-null divisor \((b)\), obtaining, when \(a\) is a multiple of \(b\), only a quotient \(q\) \((a=bq)\) and, when it is not, a quotient \(q\) and a remainder \(r\) \((a=bq+r).\) Imposing no condition on \(q\) and \(r\), the problem is trivial: it suffices to choose any \(q\) and then we can just take \(r\) as \(a-bq\). The question is that we don't want any \(q\) and \(r\): we want "the best possible" quotient which means that it should lead to a remainder which is "smaller" than the divisor. In order for this to make sense, we need to start by deciding in each case how we will compare the divisor and the remainder, in other terms when we will say that the remainder is "smaller" than the divisor.

Examples:

1 - Polynomials

2 - Gaussian integers \(\mathbb{Z}\left[i\right]\)

3 - \(\mathbb{Z}\left[\sqrt{2}\right]\) (it is advisable to see the case of Gaussian integers first)

4 - \(\mathbb{Z}\left[i\sqrt{5}\right]\)(it is advisable to see the case of Gaussian integers first)