ATRACTOR

\(\mathbb{Z}\left[\sqrt{2}\right]\) is the set of numbers of the form \(a+b\sqrt{2}\), where \(a\) and \(b\) are integers. Here we have the usual order relation between real numbers, but this will not be the one we use to compare the remainder with the divisor in divisions. What will be used, for a number \(a+b\sqrt{2}\), is \(\left|a^{2}-2b^{2}\right|\).

For any \(a+b\sqrt{2}\), with \(a,b\) integers, let \(v\left(a+b\sqrt{2}\right)=\left|a^{2}-2b^{2}\right|\). We will see that for every \(x,y\in\mathbb{Z}\left[\sqrt{2}\right],\) with \(y\neq0\) , there exist \(q,r\in\mathbb{Z}\left[\sqrt{2}\right]\) such that \[\left\{ \begin{array}{c} x=yq+r\\ v(r)<v(y) \end{array}\right.\] (the second condition is the generalization of the condition that the remainder is smaller than the divisor; it is important to remember that this has nothing to do with the remainder being smaller than the divisor for the usual order: for example \(\sqrt{2}<1+\sqrt{2}\) but \(v\left(\sqrt{2}\right)=2>1=v\left(1+\sqrt{2}\right)\)) .

Given \(x=a+b\sqrt{2}\) and \(y=c+d\sqrt{2}\), how can we find \(q=q_{1}+q_{2}\sqrt{2}\) and \(r=r_{1}+r_{2}\sqrt{2}\) such that \(z=wq+r\) and \(v(r)<v(w)\)?

Looking for \(q\) and \(r\) with these conditions is equivalent to looking for \(q_{1}+q_{2}\sqrt{2}\) and \(r_{1}+r_{2}\sqrt{2}\) such that \(a+b\sqrt{2}=\left(c+d\sqrt{2}\right)\left(q_{1}+q_{2}\sqrt{2}\right)+r_{1}+r_{2}\sqrt{2}\), which is the same as: \[\frac{a+b\sqrt{2}}{c+d\sqrt{2}}-\left(q_{1}+q_{2}\sqrt{2}\right)=\frac{r_{1}+r_{2}\sqrt{2}}{c+d\sqrt{2}},\] or \[\frac{\left(a+b\sqrt{2}\right)\left(c-d\sqrt{2}\right)}{c^{2}-2d^{2}}-\left(q_{1}+q_{2}\sqrt{2}\right)=\frac{r_{1}+r_{2}\sqrt{2}}{c+d\sqrt{2}},\] which is the same as: \[\frac{ac-2bd}{c^{2}-2d^{2}}-q_{1}+\left(\frac{bc-ad}{c^{2}-2d^{2}}-q_{2}\right)\sqrt{2}=\frac{r_{1}+r_{2}\sqrt{2}}{c+d\sqrt{2}}.\]

We want \(q_{1},q_{2},r_{1},r_{2}\) such that \(v\left(r_{1}+r_{2}\sqrt{2}\right)<v\left(c+d\sqrt{2}\right)\) which is the same as \[\frac{v\left(r_{1}+r_{2}\sqrt{2}\right)}{v\left(c+d\sqrt{2}\right)}<1\]

One can check with some calculations that \[\frac{v\left(r_{1}+r_{2}\sqrt{2}\right)}{v\left(c+d\sqrt{2}\right)}=v\left(\frac{r_{1}+r_{2}\sqrt{2}}{c+d\sqrt{2}}\right),\] hence it suffices that \[v\left(\frac{r_{1}+r_{2}\sqrt{2}}{c+d\sqrt{2}}\right)<1.\]

Since \[\begin{array}{ccc} v\left(\frac{r_{1}+r_{2}\sqrt{2}}{c+d\sqrt{2}}\right) & = & v\left(\frac{ac-2bd}{c^{2}-2d^{2}}-q_{1}+\left(\frac{bc-ad}{c^{2}-2d^{2}}-q_{2}\right)\sqrt{2}\right)=\\ & = & \left(\frac{ac-2bd}{c^{2}-2d^{2}}-q_{1}\right)^{2}-2\left(\frac{bc-ad}{c^{2}-2d^{2}}-q_{2}\right)^{2} \end{array}\] it suffices that \[\left(\frac{ac-2bd}{c^{2}-2d^{2}}-q_{1}\right)^{2}+\left(\frac{bc-ad}{c^{2}-2d^{2}}-q_{2}\right)^{2}<1.\]

Now, \[\frac{ac-2bd}{c^{2}-2d^{2}}\] and \[\frac{bc-ad}{c^{2}-2d^{2}}\] are rational numbers; for every rational number there exists an integer at a distance from it which is less than or equal to \(\frac{1}{2}\), hence there exist integers \(q_{1}\) and \(q_{2}\) such that \[\left|\frac{ac-2bd}{c^{2}-2d^{2}}-q_{1}\right|<\frac{1}{2}\] and \[\left|\frac{bc-ad}{c^{2}-2d^{2}}-q_{2}\right|<\frac{1}{2}.\]

What happens if we choose \(q_{1}\) and \(q_{2}\) with these conditions and we take \(q=q_{1}+q_{2}\sqrt{2}\) and \(r=a+b\sqrt{2}-\left(c+d\sqrt{2}\right)\left(q_{1}+q_{2}\sqrt{2}\right)\left(=r_{1}+r_{2}\sqrt{2}\right)\)?

We have \[\begin{array}{ccc} v\left(\frac{r_{1}+r_{2}\sqrt{2}}{c+d\sqrt{2}}\right) & = & \left(\frac{ac-2bd}{c^{2}-2d^{2}}-q_{1}\right)^{2}+\left(\frac{bc-ad}{c^{2}-2d^{2}}-q_{2}\right)^{2}\\ & \leq & \left(\frac{1}{2}\right)^{2}+2.\left(\frac{1}{2}\right)^{2}=\frac{1}{4}+\frac{2}{4}=\frac{3}{4}<1 \end{array}\]

Example (division algorithm)

Having the division algorithm in \(\mathbb{Z}\left[\sqrt{2}\right]\), 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\), until 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 all other divisors) are exactly the same we have seen for the case of integers.

Example \((gcd)\)