Euclidean Domains, and the Extended Euclidean Algorithm.

In this post, I want to sum up some handy results concerning the Extended Euclidean Algorithm. For that, let be an Euclidean domain:

Definition.

An Euclidean domain is an integral domain together with a function $d : R \setminus \{ 0 \} \to \N_{>0}$ satisfying, if , that for every $a, b\in R$ , $b \neq 0$ there exist $q, r \in R$ such that and .

First, note that we can modify the map to provide an additional property:

Proposition.

Define $\hat{d} : R \to \N_{\ge 0}$ , $x \mapsto \inf_{y \in R \setminus \{ 0 \}} d(x y)$ . Then $(R, \hat{d})$ is an Euclidean domain satisfying $\hat{d}(a) \le \hat{d}(a b)$ for all $a, b \in R \setminus \{ 0 \}$ .

Proof.

First, $\hat{d}(x) = 0$ if, and only if, . Next, $\hat{d}(a) \le d(a b c)$ for all $c \in R$ , whence $\hat{d}(a) \le \hat{d}(a b)$ .

Now, let , $b \neq 0$ . Let $x \in R \setminus \{ 0 \}$ be such that $d(b x) = \hat{d}(b)$ . Now let $q, r \in R$ be with and . As , there is an $r' \in R$ with . Now

$\hat{d}(r') \le \hat{d}(r' x) = \hat{d}(r) \le d(r) < d(b x) = \hat{d}(b),$

and .

This new map $\hat{d}$ satisfies three nice properties:

Lemma.

We have $\hat{d}(1) \le \hat{d}(a)$ for every $a \in R \setminus \{ 0 \}$ .
For $a \in R \setminus \{ 0 \}$ , we have $\hat{d}(a) = \hat{d}(1)$ if, and only if, $a \in R^*$ .
If , then $\hat{d}(a) = \hat{d}(b)$ .

Proof.

For $a \in R \setminus \{ 0 \}$ , we have $d(1) \le \hat{d}(1 \cdot a) = \hat{d}(a)$ .
First, assume that $a \in R^*$ . Then

$\hat{d}(a) \le \hat{d}(a a^{-1}) = \hat{d}(1) \le \hat{d}(1 \cdot a) = \hat{d}(a),$

whence $\hat{d}(a) = \hat{d}(1)$ .

Now, conversely, assume that $\hat{d}(a) = \hat{d}(1)$ . Write with $q, r \in R$ and $\hat{d}(r) < \hat{d}(a) = \hat{d}(1)$ . By 1., we get . Hence, , whence $a \in R^*$ .
As is an integral domain, implies with $u \in R^*$ . But then

$\hat{d}(a) \le{} & \hat{d}(b u) \le \hat{d}(b u u^{-1}) \ {}={} & \hat{d}(b) \le \hat{d}(a u^{-1}) \le \hat{d}(a u^{-1} u) = \hat{d}(a),$

i.e. $\hat{d}(a) = \hat{d}(b)$ .

From now on, we assume that has the property $d(a) \le d(a b)$ for all $a, b \in R$ , $b \neq 0$ .

There are two important examples of Euclidean domains, both of them satisfying , which in turn implies $d(a b) \ge d(a)$ for $b \neq 0$ :

The integers $R := \Z$ form an Euclidean ring with $d(a) := \abs{a}$ , $a \in \Z$ .
Let be a field and an arbitrary integer. Then, the polynomials form an Euclidean ring with $d(f) := q^{\deg f}$ , $f \in K[x]$ .

A first, very remarkable property of Euclidean domains is that every ideal is principal; as a consequence of this, they possess a unique factorization of elements into products of primes. Moreover, since they are principal ideal domains, not only do greatest common divisors exist, but they can be written as a linear combination of the elements of whom they are the greatest common divisor! We will soon give a constructive proof for this, but before that note that this can be shown easily as follows: let $a_1, \dots, a_n \in R$ ; then the ideal $(a_1, \dots, a_n)$ generated by them in is prinipcal, i.e. there exists an element $a \in R$ such that $(a_1, \dots, a_n) = (a)$ . Clearly, $a_i \in (a)$ , whence $a \mid a_i$ , i.e. is a common divisor of $a_1, \dots, a_n$ . Moreover, as $a \in (a_1, \dots, a_n)$ , there exist $b_1, \dots, b_n \in R$ with $a = \sum_{i=1}^n a_i b_i$ . Hence, if is another common divisor of $a_1, \dots, a_n$ , we have that divides $\sum_{i=1}^n a_i b_i = a$ ; this shows that is a greatest common divisor of $a_1, \dots, a_n$ .

Now, let us present a constructive proof that every two elements of possess a greatest common divisor. The idea goes back to Euclid.

Theorem (The Euclidean Algorithm).

Let $n, m \in R \setminus \{ 0 \}$ be two non-zero elements. Define

$\Matrix{ a_{-1} & a_{-2} \\ x_{-1} & x_{-2} \\ y_{-1} & y_{-2} } := \Matrix{ m & n \\ 0 & 1 \\ 1 & 0 }.$

Then, inductively, define as follows, $i \in \N$ : Given the corresponding values for and , there exist $a_i, q_i \in R$ such that $a_{i-2} = q_i a_{i-1} + a_i$ and $d(a_i) < d(a_{i-1})$ . Moreover, set $x_i := x_{i-2} - q_i x_{i-1}$ and $y_i := y_{i-2} - q_i y_{i-1}$ .

In case for some , set and stop the process. Otherwise, set $N := \infty$ . Moreover, for $i \ge -1$ define

$M_i := \Matrix{ a_i & a_{i-1} \\ x_i & x_{i-1} \\ y_i & y_{i-1} } \quad \text{and} \quad Q_i := \Matrix{ -q_i & 1 \\ 1 & 0 }.$

We then have the following properties:

$N < \infty$ , i.e. the process terminates;
for $i \le N$ , ;
for $0 \le i \le N$ , $M_i = M_{i-1} Q_i$ ;
for $-2 \le i < N$ , $x_i y_{i+1} - x_{i+1} y_i = (-1)^i$ ;
we have that $a_{N-1}$ is a greatest common divisor for and ;
we have $x_N \sim \frac{m}{a_{i-1}}$ and $y_N \sim \frac{n}{a_{i-1}}$ , where $\sim$ means equal up to units (i.e. elements of );
the set of all with $a_{N-1} = x n + y m$ is given by

$\{ (x_{N-1} + \tfrac{m}{a_{N-1}} a, y_{N-1} - \tfrac{n}{a_{N-1}} a) \mid a \in R \};$
for $i = 1, \dots, N$ , we have $q_i \neq 0$ ; moreover, can only happen if ;
for $i = -1, \dots, N$ , we have $a_{i-1} x_i - x_{i-1} a_i = (-1)^i m$ and $a_{i-1} y_i - y_{i-1} a_i = (-1)^{i-1} n$ .

This process of computing the is also known as the Extended Euclidean Algorithm (EEA). It is used, for example, to find explicit solutions to the Chinese Remainder Theorem, as well as inverting elements in $\Z/n\Z$ or .

Proof.

Note that $d(a_i) < d(a_{i-1})$ for $i \ge 0$ ; therefore, as $d(a_i) \in \N$ , we obtain a strictly decreasing sequence of natural numbers, which eventually has to stop. Hence, $N < \infty$ .
We show this by strong induction on . First, for , the statement is true. Now assume it is true for all ; using induction, we obtain

$x_i n + y_i m ={} & (x_{i-2} - q_i x_{i-1}) n + (y_{i-2} - q_i y_{i-1}) m \\ & (x_{i-2} n + y_{i-2} m) - q_i (x_{i-1} n + y_{i-1} m) \\ {}={} & a_{i-2} - q_i a_{i-1} = a_i.$
This follows from $a_i = a_{i-2} - a_{i-1} q_i$ and the definitions of and .
We show this by induction on . For , this is clearly true. Assume it is true for ; then

$& x_{i+1} y_{i+2} - x_{i+2} y_{i+1} \\ {}={} & x_{i+1} (y_i - q_{i+2} y_{i+1}) - (x_i - q_{i+2} x_{i+1}) y_{i+1} \\ {}={} & -(x_i y_{i+1} - x_{i+1} y_i) = -(-1)^i = (-1)^{i+1}.$
Let be a common divisor of and . As $a_{N-1} = x_{N-1} n + y_{N-1} m$ , we see that divides $a_{N-1}$ . We now have to show that $a_{N-1}$ divides both and . We show that $a_{N-1}$ divides for all $i \le N$ . It clearly divides $a_{N-1}$ and . Hence, $a_i = q_{i+2} a_{i+1} + a_{i+2}$ is divisible by $a_{N-1}$ for $i = N-2, N-3, \dots, 0, -1, -2$ ; as $a_{-1} = m$ and $a_{n-2} = n$ , the claim is proven.
We have , whence $x_N \frac{n}{a_{N-1}} = -y_N \frac{m}{a_{N-1}}$ . Now $\frac{n}{a_{N-1}}$ and $\frac{m}{a_{N-1}}$ are coprime by (5), and and are coprime by (4), whence we must have $x_N \sim \frac{m}{a_{N-1}}$ and $y_N \sim \frac{n}{a_{N-1}}$ .
Clearly, every element in the set is a solution of $a_{N-1} = x n + y m$ , as $\tfrac{m}{a_{N-1}} n + (-\tfrac{n}{a_{N-1}}) m = 0$ . Now let satisfy $a_{N-1} = x n + y m$ ; then $x' := x - x_{N-1}$ , $y' := y + y_{N-1}$ satisfy . Dividing by $a_{N-1}$ , we get $x' \frac{n}{a_{N-1}} = -y' \frac{m}{a_{N-1}}$ . By (5), we get that $\frac{m}{a_{N-1}} \mid x'$ and $\frac{n}{a_{N-1}} \mid y'$ ; write $x' = \frac{m}{a_{N-1}} x''$ and $y' = \frac{n}{a_{N-1}} y''$ with $x'', y'' \in R$ . This gives $x'' \frac{m}{a_{N-1}} \frac{n}{a_{N-1}} = -y'' \frac{n}{a_{N-1}} \frac{m}{a_{N-1}}$ , and cancelling shows ; therefore, lies in the set.
We have with , whence we have if, and only if, . This can only happen if .

For , we have $d(a_i) < d(a_{i-1}) < d(a_{i-2})$ , whereas would imply $a_i = a_{i-2}$ .
We have

$a_{i-1} x_i ={} & x_{i-1} x_i n + y_{i-1} x_i m \\ {}={} & x_{i-1} x_i n + (y_i x_{i-1} + (-1)^i) m \\ {}={} & x_{i-1} (x_i n + y_i m) + (-1)^i m \\ {}={} & x_{i-1} a_i + (-1)^i m$

and

$a_{i-1} y_i ={} & x_{i-1} y_i n + y_{i-1} y_i m \ {}={} & (y_{i-1} x_i + (-1)^{i-1}) n + y_{i-1} y_i m \ {}={} & y_{i-1} (x_i n + y_i m) + (-1)^{i-1} n \\ {}={} & y_{i-1} a_i + (-1)^{i-1} n.$

We note two special properties of Euclidean division for $\Z$ and :

In case of $R = \Z$ , one can make unique by specifying $r \le 0$ or $r \ge 0$ . I.e., for every $a, b \in \Z$ , $b \neq 0$ there exists unique elements $q, r, q', r' \in \Z$ such that and $-\abs{b} < r' \le r < \abs{b}$ . Note, that in case $r' \neq r$ we have that either $\abs{a - r} \le \abs{a}$ or $\abs{a - r'} \le \abs{a}$ .
In case of , the polynomials and are unique and satisfy $\deg (a - r) \le \deg a$ : if with $q, q', r, r' \in K[x]$ and $\deg r, \deg r' < \deg b$ , we have . As $\deg(r - r') < \deg b$ and $\deg (b (q' - q)) = \deg b + \deg (q' - q)$ , we must have , hence also . Now if $\deg a < \deg b$ , we have ; otherwise, $\deg r < \deg b \le \deg a$ , whence $\deg(a - r) = \deg a$ .

Hence, in both cases, for every $a, b \in R$ with $b \neq 0$ , there exist unique $q, r \in R$ with , and $d(a - r) = d(q b) \le d(a)$ .

In the following, we prove several properties for the Extended Euclidean Algorithm for both cases. We begin with the integer case.

Proposition.

Assume that $n, m \neq 0$ , that $R = \Z$ and that $d(z) = \abs{z}$ for all $z \in \Z$ . Moreover, assume that and are chosen as above, i.e. such that $\abs{a_{i-2} - a_i} \le \abs{a_{i-2}}$ for $i = 0, \dots, N$ . Then:

we have that and $a_{i-2}$ have the same sign for $i = 0, \dots, N - 1$ ;
we have $q_i \ge 0$ for all if and have the same sign, and $q_i \le 0$ for all if and have different signs.
if and have the same signs, $(-1)^i x_i \ge 0$ and $(-1)^{i+1} y_i \ge 0$ for $i = -2, \dots, N$ ; if and have different signs, $x_i \ge 0$ and $y_i \ge 0$ for $i = -2, \dots, N$ ;
we have $\abs{x_i} = \abs{q_i x_{i-1}} + \abs{x_{i-2}} > \abs{q_i x_{i-1}} \ge \abs{x_{i-1}}$ for $i = 0, \dots, N$ , and $\abs{y_i} = \abs{q_i y_{i-1}} + \abs{y_{i-2}} > \abs{q_i y_{i-1}} \ge \abs{y_{i-1}}$ for $i = 1, \dots, N$ ;
if $i, j \in \{ -2, \dots, N \}$ with $i \not\equiv j \pmod{2}$ , we have $(-1)^j \frac{a_i x_j}{m} \ge 0$ and $(-1)^i \frac{a_i y_j}{n} \ge 0$ ;
we have $\abs{x_i} \le \frac{\abs{m}}{\abs{a_{i-1}}}$ and $d(y_i) \le \frac{\abs{n}}{\abs{a_{i-1}}}$ for $i = -1, 0, \dots, N$ ;
for $i = 1, \dots, N$ , we have $\abs{a_i} < \frac{1}{2} \abs{a_{i-2}}$ ; therefore, $\abs{a_{2i}} \le 2^{-i} \abs{n}$ and $\abs{a_{2i+1}} \le 2^{-i} \abs{m}$ .

Proof.

By construction, $a_{i-2} = q_i a_{i-1} + a_i$ with $\abs{a_i} < \abs{a_{i-1}}$ . As we required $d(a_{i-2} - a_i) \le d(a_{i-2})$ , we must have that and $a_{i-2}$ have the same sign if $a_i \neq 0$ .
Note that by our choice, $\abs{a_i} \le \abs{a_{i-2}}$ and both are either $\le 0$ or $\ge 0$ , i.e. $a_i - a_{i-2}$ has the same sign as . As $a_i - a_{i-2} = q_i a_{i-1}$ , the claim follows.
If and have the same sign, $q_i \ge 0$ for all . We show the claim by strong induction on . For and , the claim follows from the definition. For $i \ge 0$ ,

$(-1)^i x_i ={} & (-1)^i x_{i-2} - (-1)^i q_i x_{i-1} \\ {}={} & (-1)^{i-2} x_{i-2} + q_i (-1)^{i-1} x_{i-1};$

as all terms on the right hand side are $\ge 0$ , we get $(-1)^i x_i \ge 0$ . The same argument shows that $(-1)^{i+1} y_i \ge 0$ .

If and have different signs, $q_i \le 0$ for all . Again, for , the claim is clear. If $i \ge 0$ , $x_i = x_{i-2} - q_i x_{i-1} = x_{i-2} + (-q_i) x_{i-1} \ge 0$ by strong induction, and similarly $y_i \ge 0$ .
For , we have $x_{-1} = 0$ , , whence $\abs{x_0} > 0 = \abs{q_0 x_{-1}} = \abs{x_{-1}}$ . For , we have , ; as $q_0 q_1 \ge 0$ , and we only have if or , we get $\abs{y_1} > \abs{y_0}$ .

For $i \ge 0$ resp. $i \ge 1$ , we proceed by induction. We have $x_{i+1} = x_{i-1} - q_{i+1} x_i$ , and $x_{i-1}$ and $q_{i+1} x_i$ have different signs; hence, $\abs{x_{i+2}} = \abs{q_i x_{i-1}} + \abs{x_{i-2}} \ge \abs{q_{i+1} x_i} \ge \abs{x_i}$ as $q_{i+1} \neq 0$ . Similarly, one gets the result for .

Note that $\abs{x_{i+2}} = \abs{q_{i+1} x_i}$ if, and only if, $x_{i-1} = 0$ ; this only happens for , as for , $\abs{x_{i-1}} \ge \abs{x_0} = 1$ .
If , $\frac{a_i}{m} \ge 0$ and $(-1)^j x_j \ge 0$ , whence $(-1)^j \frac{a_i x_j}{m} \ge 0$ .

If , we have $x_j \ge 0$ for all . First consider the case that is odd. Then has the same sign as $a_{-1} = m$ , whence $\frac{a_i}{m} \ge 0$ . Hence, $(-1)^j \frac{a_i x_j}{m} \ge 0$ . Next, consider the case that is even. Then has the same sign as $a_{-2} = n$ , whence $\frac{a_i}{m} \le 0$ . Hence, $(-1)^j \frac{a_i x_j}{m} \ge 0$ .

If , $\frac{a_i}{n} \ge 0$ and $(-1)^j y_j \le 0$ , whence $(-1)^i \frac{a_i y_j}{n} \ge 0$ for $i = -1, \dots, N$ .

If , we have $y_j \ge 0$ for all . First consider the case that is odd. Then has the same sign as $a_{-1} = m$ , whence $\frac{a_i}{n} \le 0$ . Hence, $(-1)^i \frac{a_i y_j}{n} \ge 0$ . Next, consider the case that is even. Then has the same sign as $a_{-2} = n$ , whence $\frac{a_i}{n} \ge 0$ . Hence, $(-1)^i \frac{a_i y_j}{n} \ge 0$ .
We show the claim by induction. For , we have

$\abs{x_{-1}} = 0 < \frac{\abs{m}}{\abs{n}} = \frac{\abs{m}}{\abs{a_{-2}}} \text{ and } \abs{y_{-1}} = 1 \le 1 = \frac{\abs{n}}{\abs{a_{-2}}}.$

For $i \ge 0$ , we have by the induction hypothesis and by $a_i < a_{i-2}$

$\abs{\frac{a_i x_{i-1}}{m}} <{} & \abs{\frac{a_{i-2} x_{i-1}}{m}} \le 1 \\ \text{and} \quad \abs{\frac{a_i y_{i-1}}{m}} <{} & \abs{\frac{a_{i-2} y_{i-1}}{m}} \le 1.$

Now $(-1)^{i+1} \frac{a_i x_{i-1}}{m} \ge 0$ , whence $\frac{a_i x_{i-1}}{m}$ and $(-1)^{i+1}$ have the same sign. As $(-1)^{i+1} \frac{a_i x_{i-1}}{m} \le 1$ , we get

$\abs{\frac{a_i x_{i-1}}{m} + (-1)^i} = \abs{\frac{a_i x_{i-1}}{m} - (-1)^{i+1}} \le 1.$

Using $a_i x_{i-1} + (-1)^i m = a_{i-1} x_i$ , we obtain $\abs{a_{i-1} x_i} \le \abs{m}$ , which gives $\abs{x_i} \le \frac{\abs{m}}{\abs{a_{i-1}}}$ .

Next, $(-1)^i \frac{a_i y_{i-1}}{n} \ge 0$ . Hence, and $\frac{a_i y_{i-1}}{n}$ have the same sign. As $(-1)^i \frac{a_i y_{i-1}}{n} \le 1$ , we get

$\abs{\frac{a_i y_{i-1}}{n} + (-1)^{i-1}} = \abs{\frac{a_i y_{i-1}}{n} - (-1)^i} \le 1.$

Using $a_i y_{i-1} + (-1)^{i-1} n = a_{i-1} y_i$ , we obtain $\abs{a_{i01} y_i} \le \abs{n}$ , which gives the claim.
Note that for $i \ge 1$ , we have $\abs{a_{i-1}} > \abs{a_i}$ . Hence, in case $\abs{a_{i-1}} \le \frac{1}{2} \abs{a_{i-2}}$ , we are done. Therefore, assume that $\abs{a_{i-1}} > \frac{1}{2} \abs{a_{i-2}}$ . Now we required $\abs{q_i a_{i-1}} \le \abs{a_{i-2}}$ , whence $\frac{1}{2} \abs{q_i a_{i-2}} < \abs{a_{i-2}}$ ; but this implies $\abs{q_i} < 2$ , i.e. $\abs{q_i} \le 1$ . As $q_i \neq 0$ , we have $q_i = \pm 1$ .

Now $a_i = a_{i-2} - q_i a_{i-1}$ and both and $a_{i-2}$ have the same sign, whence $\abs{a_i} \le \abs{a_{i-2}} - \abs{a_{i-1}} < \frac{1}{2} \abs{a_{i-2}}$ .

Proposition.

Assume that $n, m \neq 0$ , that and that $d(f) = q^{\deg f}$ for all $f \in R$ . Then:

we have $\deg a_{i-2} = \deg q_i + \deg a_{i-1}$ and $\deg q_i > 0$ for ;
we have $\deg x_0 > \deg q_0 + \deg x_{-1} \ge \deg x_{-1}$ , and

$\deg x_i ={} & \deg q_i + \deg x_{i-1} > \deg x_{i-1} \\ \text{and} \quad \deg y_i ={} & \deg q_i + \deg y_{i-1} \ge \deg y_{i-1}$

for $i = 1, \dots, N$ ; hence, we have $\deg x_i > \deg x_{i-1}$ for $i \ge 0$ and $\deg y_i > \deg y_{i-1}$ for $i \ge 1$ ;
we have $\deg x_i \le \deg m - \deg a_{i-1}$ and $\deg y_i \le \deg n - \deg a_{i-1}$ for $i = -1, 0, \dots, N$ .

Proof.

For , we have $\deg a_i < \deg a_{i-1} < \deg a_{i-2}$ ; as $a_i = a_{i-2} - q_i a_{i-1}$ , we must have $\deg a_{i-2} = \deg q_i + \deg a_{i-1}$ ; this shows $\deg q_i > 0$ .
For , we have $x_{-1} = 0$ , , whence

$\deg x_0 > \deg q_0 + \deg x_{-1} \ge \deg x_{-1}.$

For , we have , ; if , we have $\deg y_1 > \deg q_1 + \deg y_0 \ge \deg y_0$ . Now assume $q_0 \neq 0$ ; as $\deg q_1 > 0$ , we see that

$\deg y_1 = \deg q_0 + \deg q_1 = \deg y_0 + \deg q_1 > \deg y_0.$

Now assume that . As $x_i = x_{i-2} - q_i x_{i-1}$ , and we have $\deg x_{i-1} > \deg x_{i-2}$ by induction, we get $\deg (q_i x_{i-1}) > \deg x_{i-2}$ and, therefore, $\deg x_i = \deg q_i + \deg x_{i-1}$ . As $\deg q_i > 0$ , the claim follows. If , one obtains the same result for .
For , we have

$\deg x_{i-1} ={} & -\infty < \deg m - \deg n = \deg m - \deg a_{-2} \\ \text{and} \quad \deg y_{-1} ={} & 0 \le 0 = \deg n - \deg a_{-2}.$

For , we have

$\deg x_i = 0 \le \deg m - \deg m = \deg m - \deg a_{-1}$

and

$\deg y_i ={} & \deg q_0 = \deg(q_0 m) - \deg m \ {}={} & \deg(n - a_0) - \deg m \\ {}\le{} & \deg n - \deg m = \deg n - \deg a_{-1}.$

We now continue by induction on . For $i \ge 1$ , we have $\deg x_i = \deg q_i + \deg x_{i-1}$ ; as

$\deg q_i = \deg (a_{i-2} - a_i) - \deg a_{i-1} \le \deg a_{i-2} - \deg a_{i-1}$

and – by induction – $\deg x_{i-1} \le \deg m - \deg a_{i-2}$ we obtain

$\deg x_i \le{} & (\deg a_{i-2} - \deg a_{i-1}) + (\deg m - \deg a_{i-2}) \\ {}={} & \deg m - \deg a_{i-1}.$

Similarly, we obtain $\deg y_i \le \deg n - \deg a_{i-1}$ .

Hence, we obtain:

Corollary.

If $R = \Z$ with $d(z) = \abs{z}$ for all $z \in \Z$ , or with $d(f) = q^{\deg f}$ for all $f \in R$ , and if the and are chosen such that $\abs{a_i - a_{i-2}} \le \abs{a_{i-2}}$ for $i \ge 0$ , we have the following:

for $i = 0, \dots, N$ , we have $d(x_i) > d(x_{i-1})$ ; for $i = 1, \dots, N$ , we have $d(y_i) > d(y_{-1})$ ;
we have $d(x_i) \le \frac{d(m)}{d(a_{i-1})}$ and $d(y_i) \le \frac{d(n)}{d(a_{i-1})}$ for $i = -1, 0, \dots, N$ ; in particular, we have $d(x_{N-1}) < \frac{d(m)}{d(a_{N-1})} \le d(m)$ and $d(y_{N-1}) < \frac{d(n)}{d(a_{N-1})} \le d(n)$ .

Proof.

We are left to show the last statement of 2. For that, note that $d(x_{N-1}) \le \frac{d(m)}{d(a_{N-2})} < \frac{d(m)}{d(a_{N-1})} \le d(m)$ and, analogously, $d(y_{N-1}) < \frac{d(n)}{d(a_{N-1})} \le d(n)$ .

Felix' Math Place

Focussed on, but not limited to Computational Number Theory

Euclidean Domains, and the Extended Euclidean Algorithm.

Comments.

About Me.

About This Blog.

Overview Pages.

Recent Posts.

Archives.

Impressum.

Data Protection.

Felix' Math Place

Focussed on, but not limited to Computational Number Theory

Euclidean Domains, and the Extended Euclidean Algorithm.

Comments.

About Me.

About This Blog.

Overview Pages.

Categories.

Recent Posts.

Archives.

Tags.

Impressum.

Data Protection.