# 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 satisfying, if , that for every , there exist such that and .

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

Proposition.

Define , . Then is an Euclidean domain satisfying for all .

Proof.

First, if, and only if, . Next, for all , whence .

Now, let , . Let be such that . Now let be with and . As , there is an with . Now

and .

This new map satisfies three nice properties:

Lemma.
1. We have for every .
2. For , we have if, and only if, .
3. If , then .
Proof.
1. For , we have .
2. First, assume that . Then

whence .

Now, conversely, assume that . Write with and . By 1., we get . Hence, , whence .

3. As is an integral domain, implies with . But then

i.e. .

From now on, we assume that has the property for all , .

There are two important examples of Euclidean domains, both of them satisfying , which in turn implies for :

1. The integers form an Euclidean ring with , .
2. Let be a field and an arbitrary integer. Then, the polynomials form an Euclidean ring with , .

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 ; then the ideal generated by them in is prinipcal, i.e. there exists an element such that . Clearly, , whence , i.e. is a common divisor of . Moreover, as , there exist with . Hence, if is another common divisor of , we have that divides ; this shows that is a greatest common divisor of .

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 be two non-zero elements. Define

Then, inductively, define as follows, : Given the corresponding values for and , there exist such that and . Moreover, set and .

In case for some , set and stop the process. Otherwise, set . Moreover, for define

We then have the following properties:

1. , i.e. the process terminates;
2. for , ;
3. for , ;
4. for , ;
5. we have that is a greatest common divisor for and ;
6. we have and , where means equal up to units (i.e. elements of );
7. the set of all with is given by

8. for , we have ; moreover, can only happen if ;
9. for , we have and .

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 or .

Proof.
1. Note that for ; therefore, as , we obtain a strictly decreasing sequence of natural numbers, which eventually has to stop. Hence, .
2. We show this by strong induction on . First, for , the statement is true. Now assume it is true for all ; using induction, we obtain

3. This follows from and the definitions of and .
4. We show this by induction on . For , this is clearly true. Assume it is true for ; then

5. Let be a common divisor of and . As , we see that divides . We now have to show that divides both and . We show that divides for all . It clearly divides and . Hence, is divisible by for ; as and , the claim is proven.
6. We have , whence . Now and are coprime by (5), and and are coprime by (4), whence we must have and .
7. Clearly, every element in the set is a solution of , as . Now let satisfy ; then , satisfy . Dividing by , we get . By (5), we get that and ; write and with . This gives , and cancelling shows ; therefore, lies in the set.
8. We have with , whence we have if, and only if, . This can only happen if .

For , we have , whereas would imply .

9. We have

and

We note two special properties of Euclidean division for and :

1. In case of , one can make unique by specifying or . I.e., for every , there exists unique elements such that and . Note, that in case we have that either or .
2. In case of , the polynomials and are unique and satisfy : if with and , we have . As and , we must have , hence also . Now if , we have ; otherwise, , whence .

Hence, in both cases, for every with , there exist unique with , and .

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

Proposition.

Assume that , that and that for all . Moreover, assume that and are chosen as above, i.e. such that for . Then:

1. we have that and have the same sign for ;
2. we have for all if and have the same sign, and for all if and have different signs.
3. if and have the same signs, and for ; if and have different signs, and for ;
4. we have for , and for ;
5. if with , we have and ;
6. we have and for ;
7. for , we have ; therefore, and .
Proof.
1. By construction, with . As we required , we must have that and have the same sign if .
2. Note that by our choice, and both are either or , i.e. has the same sign as . As , the claim follows.
3. If and have the same sign, for all . We show the claim by strong induction on . For and , the claim follows from the definition. For ,

as all terms on the right hand side are , we get . The same argument shows that .

If and have different signs, for all . Again, for , the claim is clear. If , by strong induction, and similarly .

4. For , we have , , whence . For , we have , ; as , and we only have if or , we get .

For resp. , we proceed by induction. We have , and and have different signs; hence, as . Similarly, one gets the result for .

Note that if, and only if, ; this only happens for , as for , .

5. If , and , whence .

If , we have for all . First consider the case that is odd. Then has the same sign as , whence . Hence, . Next, consider the case that is even. Then has the same sign as , whence . Hence, .

If , and , whence for .

If , we have for all . First consider the case that is odd. Then has the same sign as , whence . Hence, . Next, consider the case that is even. Then has the same sign as , whence . Hence, .

6. We show the claim by induction. For , we have

For , we have by the induction hypothesis and by

Now , whence and have the same sign. As , we get

Using , we obtain , which gives .

Next, . Hence, and have the same sign. As , we get

Using , we obtain , which gives the claim.

7. Note that for , we have . Hence, in case , we are done. Therefore, assume that . Now we required , whence ; but this implies , i.e. . As , we have .

Now and both and have the same sign, whence .

Proposition.

Assume that , that and that for all . Then:

1. we have and for ;
2. we have , and

for ; hence, we have for and for ;

3. we have and for .
Proof.
1. For , we have ; as , we must have ; this shows .
2. For , we have , , whence

For , we have , ; if , we have . Now assume ; as , we see that

Now assume that . As , and we have by induction, we get and, therefore, . As , the claim follows. If , one obtains the same result for .

3. For , we have

For , we have

and

We now continue by induction on . For , we have ; as

and – by induction – we obtain

Similarly, we obtain .

Hence, we obtain:

Corollary.

If with for all , or with for all , and if the and are chosen such that for , we have the following:

1. for , we have ; for , we have ;
2. we have and for ; in particular, we have and .
Proof.

We are left to show the last statement of 2. For that, note that and, analogously, .