Euclidean Domains, and the Extended Euclidean Algorithm.

Abstract.
We will discuss Euclidean domains together with a constructive proof of the fact that every two elements have a greatest common divisor, which is essentially the Euclidean algorithm.
We will state several (more or less) useful properties of the Extended Euclidean Algorithm, in particular for the case of integers and univariate polynomials over a field.

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

Definition.

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

First, note that we can modify the map $d$ 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, $x = 0$ . 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 $a, b$ , $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 $a x = q (b x) + r$ and $d(r) < d(b x)$ . As $r = (a - q b) x$ , there is an $r' \in R$ with $r = r' x$ . Now $\displaystyle \hat{d}(r') \le \hat{d}(r' x) = \hat{d}(r) \le d(r) < d(b x) = \hat{d}(b),$ and $a = q b + r'$ .
□

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 $(a) = (b)$ , 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 $\displaystyle \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 $1 = q a + r$ with $q, r \in R$ and $\hat{d}(r) < \hat{d}(a) = \hat{d}(1)$ . By 1., we get $r = 0$ . Hence, $1 = q a$ , whence $a \in R^*$ .

As $R$ is an integral domain, $(a) = (b)$ implies $a = b u$ 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 $d$ 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 $d(a b) = d(a) d(b)$ , 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 $K$ be a field and $q > 1$ an arbitrary integer. Then, the polynomials $R := K[x]$ 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 $R$ 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. $a$ 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 $a'$ is another common divisor of $a_1, \dots, a_n$ , we have that $a'$ divides $\sum_{i=1}^n a_i b_i = a$ ; this shows that $a$ is a greatest common divisor of $a_1, \dots, a_n$ .

Now, let us present a constructive proof that every two elements of $R$ 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 $\displaystyle \Matrix{ a_{-1} & a_{-2} \\ x_{-1} & x_{-2} \\ y_{-1} & y_{-2} } := \Matrix{ m & n \\ 0 & 1 \\ 1 & 0 }.$ Then, inductively, define $a_i, x_i, y_i, q_i$ as follows, $i \in \N$ : Given the corresponding values for $i - 1$ and $i - 2$ , 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 $a_i = 0$ for some $i$ , set $N := i$ and stop the process. Otherwise, set $N := \infty$ . Moreover, for $i \ge -1$ define $\displaystyle 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$ , $a_i = x_i n + y_i m$ ;

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 $n$ and $m$ ;

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 $R^*$ );

the set of all $(x, y)$ with $a_{N-1} = x n + y m$ is given by $\displaystyle \{ (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, $q_0 = 0$ can only happen if $d(n) < d(m)$ ;

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 $a_i, x_i, y_i$ 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 $K[x]/(f)$ .

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 $i$ . First, for $i = -2, -1$ , the statement is true. Now assume it is true for all $j < i$ ; 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 $x_i$ and $y_i$ .

We show this by induction on $i$ . For $i = -2$ , this is clearly true. Assume it is true for $i$ ; 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 $a$ be a common divisor of $n$ and $m$ . As $a_{N-1} = x_{N-1} n + y_{N-1} m$ , we see that $a$ divides $a_{N-1}$ . We now have to show that $a_{N-1}$ divides both $n$ and $m$ . We show that $a_{N-1}$ divides $a_i$ for all $i \le N$ . It clearly divides $a_{N-1}$ and $a_N = 0$ . 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 $0 = a_N = x_N n + y_N m$ , 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 $x_N$ and $y_N$ 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 $(x, y)$ satisfy $a_{N-1} = x n + y m$ ; then $x' := x - x_{N-1}$ , $y' := y + y_{N-1}$ satisfy $x' n + y' m = 0$ . 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 $x'' = -y''$ ; therefore, $(x, y)$ lies in the set.

We have $n = q_0 m + a_0$ with $d(a_0) < d(m)$ , whence we have $q_0 = 0$ if, and only if, $n = a_0$ . This can only happen if $d(n) < d(m)$ .
For $i > 0$ , we have $d(a_i) < d(a_{i-1}) < d(a_{i-2})$ , whereas $q_i = 0$ 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 $K[x]$ :

In case of $R = \Z$ , one can make $r$ 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 $a = q b + r = q' b + r'$ 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 $R = K[x]$ , the polynomials $q$ and $r$ are unique and satisfy $\deg (a - r) \le \deg a$ : if $a = q b + r = q' b + r'$ with $q, q', r, r' \in K[x]$ and $\deg r, \deg r' < \deg b$ , we have $r - r' = b (q' - q)$ . As $\deg(r - r') < \deg b$ and $\deg (b (q' - q)) = \deg b + \deg (q' - q)$ , we must have $q' - q = 0$ , hence also $r - r' = 0$ . Now if $\deg a < \deg b$ , we have $r = a$ ; 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 $a = q b + r$ , $d(r) < d(b)$ 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 $q_i$ and $a_i$ 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 $a_i$ and $a_{i-2}$ have the same sign for $i = 0, \dots, N - 1$ ;

we have $q_i \ge 0$ for all $i$ if $n$ and $m$ have the same sign, and $q_i \le 0$ for all $i$ if $n$ and $m$ have different signs.

if $n$ and $m$ have the same signs, $(-1)^i x_i \ge 0$ and $(-1)^{i+1} y_i \ge 0$ for $i = -2, \dots, N$ ; if $n$ and $m$ 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 $a_i$ 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 $a_i$ . As $a_i - a_{i-2} = q_i a_{i-1}$ , the claim follows.

If $n$ and $m$ have the same sign, $q_i \ge 0$ for all $i$ . We show the claim by strong induction on $i$ . For $i = -2$ and $i = -1$ , 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 $n$ and $m$ have different signs, $q_i \le 0$ for all $i$ . Again, for $i = -2, -1$ , 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 $i = 0$ , we have $x_{-1} = 0$ , $x_0 = 1$ , whence $\abs{x_0} > 0 = \abs{q_0 x_{-1}} = \abs{x_{-1}}$ . For $i = 1$ , we have $y_0 = -q_0$ , $y_1 = 1 + q_0 q_1$ ; as $q_0 q_1 \ge 0$ , and we only have $q_0 q_1 = 0$ if $q_0 = 0$ or $N = 0$ , 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 $y$ .
Note that $\abs{x_{i+2}} = \abs{q_{i+1} x_i}$ if, and only if, $x_{i-1} = 0$ ; this only happens for $i = 0$ , as for $i > 0$ , $\abs{x_{i-1}} \ge \abs{x_0} = 1$ .

If $n m > 0$ , $\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 $n m < 0$ , we have $x_j \ge 0$ for all $j$ . First consider the case that $i$ is odd. Then $a_i$ 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 $i$ is even. Then $a_i$ 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 $n m > 0$ , $\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 $n m < 0$ , we have $y_j \ge 0$ for all $j$ . First consider the case that $i$ is odd. Then $a_i$ 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 $i$ is even. Then $a_i$ 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 $i = -1$ , we have $\displaystyle \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 $\displaystyle \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, $(-1)^i$ 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 $\displaystyle \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 $a_i$ 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 $R = K[x]$ 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 $i > 0$ ;

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 $i > 0$ , 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 $i = 0$ , we have $x_{-1} = 0$ , $x_0 = 1$ , whence $\displaystyle \deg x_0 > \deg q_0 + \deg x_{-1} \ge \deg x_{-1}.$ For $i = 1$ , we have $y_0 = -q_0$ , $y_1 = 1 + q_0 q_1$ ; if $q_0 = 0$ , 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 $\displaystyle \deg y_1 = \deg q_0 + \deg q_1 = \deg y_0 + \deg q_1 > \deg y_0.$
Now assume that $i > 0$ . 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 $i > 1$ , one obtains the same result for $y$ .

For $i = -1$ , 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 $i = 0$ , we have $\displaystyle \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 $i$ . For $i \ge 1$ , we have $\deg x_i = \deg q_i + \deg x_{i-1}$ ; as $\displaystyle \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 $R = K[x]$ with $d(f) = q^{\deg f}$ for all $f \in R$ , and if the $q_i$ and $a_i$ 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)$ .
□

Tags: Euclidean domain, Extended Euclidean Algorithm, greatest common divisor

This entry was posted on Wednesday, November 18th, 2009 at 02:34 Europe/Berlin and is filed under Algebra. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Euclidean Domains, and the Extended Euclidean Algorithm.

Abstract.

Leave a Reply