The Euclidean Algorithm, and More

Mike

2021-10-24

Page content

Euclid’s algorithm is both simple and powerful. It is essentially just division and recursion but with a tiny bit of tweaking, we can use it to find inverses in finite fields (which we will show in a later entry). Here we cover more ring theory, and then finish with the Euclidean Algorithm.

Definition: Ring Unit

Let $ R $ be a commutative ring with identity, $1$. Let $ x $ be an element, such that there exists a $ y \in R $ where $ xy = 1 $ or $ yx = 1 $ (or both). Then $ x $ is said to be a unit.

Notice that this is equivalent to saying that “a unit has a multiplicative inverse in $R$”.

Thus, the identity element is a unit, but a unit isn’t necessarily equal to the identity element. For example, in a field (like $ \mathbb{Q} $), every non-zero element is a unit.

Definition: Ring Norm

Let $ R $ be a commutative ring with identity and $ N : R \rightarrow \mathbb{Z}_{\geq 0} $ be a function, such that

$ N(r_1r_2) = N(r_1)N(r_2) $ for all $ r_1 $ and $ r_2 $ in $R$
$ N(r) = 1 $ if and only if $ r $ is a unit

Then, $N$ is said to be a norm map on $ R $.

Hopefully this next definition doesn’t surprise anyone.

Definition: Divides

Let $ R $ be a commutative ring, and $ x, z \in R $ such that there exists $ y \in R $ where $ xy = z $, then $ x $ divides $ z $.

This is often written “$ x | z $”.

However, the next two definitions might seem a bit puzzling, only because they don’t mean the same thing, in general.

Definition: Irreducible Element

Let $ R $ be a commutative Integral Domain with identity, then an element, $ y \in R $, which is not a unit is said to be irreducible whenever we have:

$ wx = y $ implies at least one of $ x $ or $ y $ is a unit.

Definition: Prime Element

Let $ R $ be a commutative integral domain with identity, then an element, $ p \in R $, which is not a unit, is said to be a prime whenever we have:

$ p | xy $ implies at least one (but possibly both) of the following holds:

$ p | x $
$ p | y $

Mini-lemma: cancelling in an Integral Domain

Let $ R $ be an integral Domain with identity, then:

$ y \neq 0 $ and $ xy = y $ implies $ x = 1 $
$ x \neq 0 $ and $ xy = x $ implies $ y = 1 $

Proof

We’ll prove 1, the other case is nearly identical.

Suppose $ xy = y $, then $ xy - y = 0 $, and since $ 1 \in R $, we can factor this as

\[ (x - 1)y = 0 \]

Now, since $ R $ is an integral domain, we have $ y = 0 $ or $ x - 1 = 0 $. We’ve assumed that $ y \neq 0 $, so we must have $ x - 1 = 0 $, which means that $ x = 1 $.

QED

Theorem: Primes are Irreducible

Let $ R $ be a commutative integral domain with identity, and suppose that $ p \in R $ is prime, then $ p $ is irreducible.

Proof

Let $ p $ be a prime element of $R$, and suppose that $ wx = p $. Then, $ p | wx $, and since $ p $ is a prime we have either

$ p | w $ or
$ p | x $

Suppose $ p | w $, then $ w = up $, for some $ u \in R $. This means that

$$ \begin{align} (up)x &= p \\ \implies p(ux) &= p \\ \implies ux &= 1 \\ \end{align} $$

where the last line follows from the previous cancellations mini-lemma. Thus, $ x $ is a unit.

The case where $ p | x $ is similar, and in that case we would prove that $ w $ is a unit.

Combining the two cases means that either $ w $ or $ x $ is a unit, and that means that $ p $ is irreducible.

QED

Theorem: Norm Map implies factorization into irreducibles

Let $ R $ be a commutative integral domain with identity, $ N : R \rightarrow \mathbb{Z}_{\geq 0} $ a norm map on $R$, and let $ r $ be an arbitrary element of $ R $. Then there exists a finite set

\[ F = \{ q_0, q_1, … q_n \} \]

such that each $ q_i \in F $ is either irreducible or a unit and

\[ \prod\limits_{q \in F} q = r \]

Proof

We’ll prove this by induction and contradiction. Clearly the result holds for every unit in $R$, since if $ r $ is a unit, then $ F = \{ r \} $ works.

Suppose the result fails for some elements of $R$. Let $ r’ $ be one of the elements of $R$ where the result fails, such that every element with smaller norm can be factored into units and irreducibles.

Now, since $ r’ $ can’t be factored into units and irreducibles, it can’t be irreducible, otherwise $ F = \{ r’ \} $ would work, so there must be $ x $ and $ y \in R $, such that neither $ x $ nor $ y $ is a unit and $ r’ = xy $ (otherwise $ r’ $ would be irreducible).

Since neither is a unit, we have $ N(x) > 1 $ and $ N(y) > 1 $ (by the definition of ring norm, given earlier), and, since

\[ N(r’) = N(xy) = N(x)N(y) \]

We must therefore also have

$$ \begin{align} N(x) < N(r’) \\ N(y) < N(r’) \\ \end{align} $$

but by our choice of $ r’ $, that means that $ x $ and $y$ can be factored as

$$ \begin{align} x &= \prod\limits_{s \in F_x} s \\ y &= \prod\limits_{t \in F_y} t \\ \end{align} $$

where each element of $ F_x $ and $ F_y $ are either irreducible or units. This means that $ r’ $ can be factored as

$$ \prod\limits_{ u \in F_x \cup F_y } u $$

where each $ u $ is either a unit or irreducible. A contradiction.

QED

Mini-lemma: The set of units forms a group under multiplication

Let $ R $ be a ring with identity (not necessarily commutative nor an integral domain), and let $ U $ be the set of all of the units of $R$. Then $ U $ is a group under the action of the $ \cdot $ operator of $R$.

Proof

$ 1 \in U $, so $ U $ has an identity element.

Notice that if $ x $ and $ y $ are units then $ x^{-1} \in R $ and $ y^{-1} \in R $. $ (xy)^{-1} = y^{-1}x^{-1} $, so $ U $ is closed under multiplication. It satisfies all the other group axioms because it satisfies the multiplicative (i.e. “$ \cdot $”) ring axioms.

QED

Mini-lemma: Multiplication by units forms equivalence classes

Let $ R $ be a commutative ring with identity, then we can define

$$ \begin{align} x &\equiv_{u} y \\ \iff \exists w, xw &= y \\ \end{align} $$

where $ w $ is a unit.

We defined equivalence classes and equivalence relations in earlier entries.

Proof

Notice that

$ x \equiv_{u} x $
$ x \equiv_{u} y $ if and only if $ y \equiv_{u} x $

Now, suppose we have

$$ \begin{align} x &\equiv_{u} y \\ y &\equiv_{u} z \\ \end{align} $$

Then there are units $ w_1 $ and $ w_2 $, such that

$$ \begin{align} xw_1 &= y \\ yw_2 &= z \\ \end{align} $$

Since $ R $ is commutative, we have

$ (xw_1)w_2 = z $, which means we have $ x(w_1w_2) = z $. By the previous lemma, units form a group, so $ w_1w_2 $ is a unit.

QED

Definition: Common Divisor / Greatest Common Divisor

Let $ R $ be a commutative ring. Let $ x $, $ y $ and $ d $ be elements of $R$, such that $ d | x $ and $ d | y $. Then $ d $ is said to be a common divisor of $ x $ and $ y $.

Moreover, if $ d $ is such that $ c | d $ for any other common divisor, $ c $, then $ d $ is said to be a greatest common divisor. When it is well-defined,it is often written:

\[ \gcd(x,y) = d \]

but it can also be written more succinctly as:

\[ (x,y) = d \]

We will usually use “$ \gcd(x,y) $”.

If $ R $ is an integral domain with identity, then $ \gcd(x,y) $ is well-defined up to multiplication by units, so $ d $ will be a representative of its equivalence class.

Proof

The proof is very simple. Suppose $ a $ and $ b $ are both non-zero greatest common divisors of $ x $ and $ y $. Then $ a | b $ and $ b | a $. This means we have

$$ \begin{align} as &= b \\ bt &= a \\ \implies a(st) &= a \\ \end{align} $$

Thus by this lemma from earlier, $ st = 1 $, so $ a $ and $ b $ are equivalent “modulo” units.

On the other hand, if one of $ a $ or $ b $ is equal to $ 0 $, then they are both equal to $ 0 $ (since for this result we are assuming that $ R $ is an integral domain), so the result still holds.

QED

Definition: Euclidean Domain

Let $ R $ be a commutative integral domain with identity with a map $ N : R \rightarrow \mathbb{Z}_{\geq 0} $ (Note this map does not have to be a norm map). Further, suppose that for each pair, $ a, b $ of non-zero elements of $R$, we have the existence of two more elements, $ q $ and $ r $, such that

\[ a = bq + r \]

where $ N(r) < N(b) $, then $ R $ is said to be a Euclidean Domain.

It is called this because we can apply the Euclidean Algorithm to any non-zero pair of elements of $R$ to find a greatest common divisor for them.

If the map $ N $ is a norm map, then $ R $ is said to be Norm Euclidean.

We have one more tiny result before we get to the Euclidean Algorithm.

Mini-lemma divisor across a sum

Let $ R $ be a ring, $ d, a $ and $b \in R $ such that $ d | a + b $ and $ d | a $, then $ d | b $.

Proof

$ d | a + b $ implies there exists an $ x \in R $ such that $ dx = a + b $. Similarly, $ d | a $ implies there exists a $ y \in R $ such that $ dy = a $. Combining the two equations, we get $ dx = dy + b $, which implies $ dx - dy = b $, which gives us $ d(x - y) = b $. Therefore, $ d | b $.

QED

Finally, we’re about to explain the Euclidean Algorithm!

The Euclidean Algorithm

The Euclidean Algorithm will happen in a Euclidean Domain. We’ll define

\[ \left \lfloor \frac{a}{b} \right \rfloor := q \]

where

\[ a = bq + r \]

and $ N(r) < N(b) $, as it was above when we gave the definition of a Euclidean Domain. We also assume that $ N(b) < N(a) $. The euclidean algorithm will generate a sequence of $ x_i $’s, where

$$ \begin{align} x_0 := a \\ x_1 := b \\ \end{align} $$

We’ll also define

$$ f_i := \left \lfloor \frac{x_i}{x_{i+1}} \right \rfloor $$

Then, once we’ve generated $ x_0 $, $ x_1 $, … , $ x_i $, $x_{i+1}$, we continue the sequence with

$$ \begin{bmatrix} &x_{i+1} \\ &x_{i+2} \\ \end{bmatrix}:= \begin{bmatrix} &0 & 1 \\ &1 & -f_i \\ \end{bmatrix} \begin{bmatrix} &x_{i} \\ &x_{i+1} \\ \end{bmatrix} $$

Which generates $ x_{i+2} $ as $ x_{i} - f_ix_{i+1} $. Notice that, by the previous mini-lemma, (divisor across a sum), if a divisor divides $ x_i $ and $ x_{i+1} $ then it also divides $ x_{i+2} $.

Notice that

$$ x_i = x_{i+1} f_i + x_{i+2} $$

\[ N(x_{i+2}) < N(x_{i+1}) \]

Therefore the process will eventually generate $ x_{i+2} = 0 $, for some $i$, and then we take

$$ \gcd(a,b) = x_{i+1} $$

If we define the matrix

$$ M_i := \begin{bmatrix} &0 & 1 \\ &1 & -f_i \\ \end{bmatrix} $$

Notice that

$$ \begin{bmatrix} &x_{i+1} \\ &x_{i+2} \\ \end{bmatrix}= \left ( \prod\limits_{k = i}^{0} M_{k} \right ) \begin{bmatrix} &x_{0} \\ &x_{1} \\ \end{bmatrix} $$

And that

$$ P = \prod\limits_{k = i}^{0} M_{k} $$

is just a $ 2 \times 2 $ matrix (since it’s the product of a number of $ 2 \times 2 $ matrices). Let the components of $ P $ be

$$ \begin{bmatrix} &p_{1,1} &p_{1,2} \\ &p_{2,1} &p_{2,2} \\ \end{bmatrix} $$

They are all elements of $R$ (i.e. $ P \in R^{2 \times 2} $). Then, since $x_0 = a$ and $x_1 = b$, we have

\[ p_{1,1}a + p_{1,2}b = \gcd(a,b) \]

We’ll prove that the Euclidean Algorithm does indeed return the greatest common divisor of $ a $ and $ b $ in the next entry.

We’ve implemented this in Python for the ring of integers.

Python Extended Euclidean Algorithm for integers

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43


from math import floor

def euclidean_algorithm(a,b):
  if a < b:
    tmp = euclidean_algorithm(b,a)
    return {
      'gcd': tmp['gcd'],
      's': tmp['t'],
      't': tmp['s']
    }
  if b == 0: return {
    'gcd':a,
    's': 0,
    't': 0
  }
  f = floor(a/b)
  p11 = 0
  p12 = 1
  p21 = 1
  p22 = -f
  x0 = a
  x1 = b
  while True:
    f = floor(x0/x1)
    x0_new = x1
    x1_new = x0 - f*x1
    p11_new = p21
    p12_new = p22
    p21_new = p11 - f*p21
    p22_new = p12 - f*p22
    if x1_new == 0: break
    # Now update
    x0 = x0_new
    x1 = x1_new
    p11 = p11_new
    p12 = p12_new
    p21 = p21_new
    p22 = p22_new
  return {
    'gcd': x1,
    's': p11,
    't': p12
  }

That’s all for this entry. Thanks for reading!!