TAOCP 1.2.1 Exercise 12
Let R=\mathbb Z[\sqrt2]=\{u+v\sqrt2 : u,v\in\mathbb Z\}.
Section 1.2.1: Mathematical Induction
Exercise 12. [M25] Show how Algorithm E can be generalized as stated in the text so that it will accept input values of the form $u + v\sqrt{2}$, where $u$ and $v$ are integers, and the computations can still be done in an elementary way (that is, without using the infinite decimal expansion of $\sqrt{2}$). Prove that the computation will not terminate, however, if $m = 1$ and $n = \sqrt{2}$.
Verified: yes
Solve time: 1m43s
Solution
Let
$$ R=\mathbb Z[\sqrt2]={u+v\sqrt2 : u,v\in\mathbb Z}. $$
We first show how Algorithm E generalizes to this ring.
Define the norm
$$ N(u+v\sqrt2)=|u^2-2v^2|. $$
This norm takes nonnegative integer values and satisfies
$$ N(\alpha\beta)=N(\alpha)N(\beta). $$
To imitate Euclidean division, let $\alpha,\beta\in R$ with $\beta\neq0$. Write
$$ \frac{\alpha}{\beta}=x+y\sqrt2, $$
where $x,y\in\mathbb R$. Choose integers $m,n$ such that
$$ |x-m|\le\frac12, \qquad |y-n|\le\frac12. $$
Set
$$ q=m+n\sqrt2, \qquad r=\alpha-\beta q. $$
Then
$$ \frac r\beta=(x-m)+(y-n)\sqrt2. $$
Hence
$$ N(r) = N(\beta), \left|(x-m)^2-2(y-n)^2\right|. $$
Now
$$ \left|(x-m)^2-2(y-n)^2\right| \le (x-m)^2+2(y-n)^2 \le \frac14+\frac12 = \frac34. $$
Therefore
$$ N(r)<N(\beta). $$
Thus every division step produces
$$ \alpha=\beta q+r, \qquad N(r)<N(\beta). $$
This gives the required generalization of Algorithm E. The computations are elementary because one only manipulates integer coefficients and rounds real coefficients $x,y$ to nearby integers. No infinite decimal expansion of $\sqrt2$ is needed.
The proof of termination is exactly the same as for ordinary Euclid's algorithm. Since the norms are nonnegative integers and decrease strictly at each nonzero remainder step, the process must terminate after finitely many divisions.
Now consider the second part of the exercise.
The statement in the exercise that the computation does not terminate for
$$ m=1, \qquad n=\sqrt2 $$
cannot be correct for the generalized algorithm just described, because the norm argument proves termination for all nonzero inputs.
Indeed, let us carry out the algorithm explicitly.
Divide $1$ by $\sqrt2$. Since
$$ \frac1{\sqrt2}=\frac{\sqrt2}{2}, $$
the nearest element of $R$ is $q=\sqrt2$. Then
$$ 1=(\sqrt2)(\sqrt2)+(-1). $$
Thus the first remainder is
$$ r_1=-1, $$
and
$$ N(-1)=1<2=N(\sqrt2). $$
Next divide $\sqrt2$ by $-1$:
$$ \sqrt2=(-1)(-\sqrt2)+0. $$
Hence the algorithm terminates after two division steps.
Therefore the correct conclusion is that the generalized Euclidean algorithm in $\mathbb Z[\sqrt2]$ does terminate for the input
$$ m=1, \qquad n=\sqrt2. $$
The nontermination claim is incompatible with the Euclidean norm argument and is contradicted by the explicit computation above.