# Euclidean domains #

This file introduces Euclidean domains and provides the extended Euclidean algorithm. To be precise, a slightly more general version is provided which is sometimes called a transfinite Euclidean domain and differs in the fact that the degree function need not take values in ℕ but can take values in any well-ordered set. Transfinite Euclidean domains were introduced by Motzkin and examples which don't satisfy the classical notion were provided independently by Hiblot and Nagata.

## Main definitions #

• EuclideanDomain: Defines Euclidean domain with functions quotient and remainder. Instances of Div and Mod are provided, so that one can write a = b * (a / b) + a % b.
• gcd: defines the greatest common divisors of two elements of a Euclidean domain.
• xgcd: given two elements a b : R, xgcd a b defines the pair (x, y) such that x * a + y * b = gcd a b.
• lcm: defines the lowest common multiple of two elements a and b of a Euclidean domain as a * b / (gcd a b)

## Main statements #

See Algebra.EuclideanDomain.Basic for most of the theorems about Euclidean domains, including Bézout's lemma.

See Algebra.EuclideanDomain.Instances for the fact that ℤ is a Euclidean domain, as is any field.

## Notation #

≺ denotes the well founded relation on the Euclidean domain, e.g. in the example of the polynomial ring over a field, p ≺ q for polynomials p and q if and only if the degree of p is less than the degree of q.

## Implementation details #

Instead of working with a valuation, EuclideanDomain is implemented with the existence of a well founded relation r on the integral domain R, which in the example of ℤ would correspond to setting i ≺ j for integers i and j if the absolute value of i is smaller than the absolute value of j.

## Tags #

Euclidean domain, transfinite Euclidean domain, Bézout's lemma

class EuclideanDomain (R : Type u) extends , :

A EuclideanDomain is a non-trivial commutative ring with a division and a remainder, satisfying b * (a / b) + a % b = a. The definition of a Euclidean domain usually includes a valuation function R → ℕ. This definition is slightly generalised to include a well founded relation r with the property that r (a % b) b, instead of a valuation.

• add_assoc : ∀ (a b c : R), a + b + c = a + (b + c)
• zero : R
• zero_add : ∀ (a : R), 0 + a = a
• add_zero : ∀ (a : R), a + 0 = a
• nsmul : RR
• nsmul_zero : ∀ (x : R), = 0
• nsmul_succ : ∀ (n : ) (x : R), AddMonoid.nsmul (n + 1) x = + x
• add_comm : ∀ (a b : R), a + b = b + a
• mul : RRR
• left_distrib : ∀ (a b c : R), a * (b + c) = a * b + a * c
• right_distrib : ∀ (a b c : R), (a + b) * c = a * c + b * c
• zero_mul : ∀ (a : R), 0 * a = 0
• mul_zero : ∀ (a : R), a * 0 = 0
• mul_assoc : ∀ (a b c : R), a * b * c = a * (b * c)
• one : R
• one_mul : ∀ (a : R), 1 * a = a
• mul_one : ∀ (a : R), a * 1 = a
• natCast : R
• natCast_zero :
• natCast_succ : ∀ (n : ), NatCast.natCast (n + 1) =
• npow : RR
• npow_zero : ∀ (x : R), = 1
• npow_succ : ∀ (n : ) (x : R), Semiring.npow (n + 1) x = * x
• neg : RR
• sub : RRR
• sub_eq_add_neg : ∀ (a b : R), a - b = a + -b
• zsmul : RR
• zsmul_zero' : ∀ (a : R), = 0
• zsmul_succ' : ∀ (n : ) (a : R), Ring.zsmul (Int.ofNat n.succ) a = Ring.zsmul () a + a
• zsmul_neg' : ∀ (n : ) (a : R), = -Ring.zsmul (n.succ) a
• add_left_neg : ∀ (a : R), -a + a = 0
• intCast : R
• intCast_ofNat : ∀ (n : ), = n
• intCast_negSucc : ∀ (n : ), = -(n + 1)
• mul_comm : ∀ (a b : R), a * b = b * a
• exists_pair_ne : ∃ (x : R), ∃ (y : R), x y
• quotient : RRR

A division function (denoted /) on R. This satisfies the property b * (a / b) + a % b = a, where % denotes remainder.

• quotient_zero : ∀ (a : R),

Division by zero should always give zero by convention.

• remainder : RRR

A remainder function (denoted %) on R. This satisfies the property b * (a / b) + a % b = a, where / denotes quotient.

• quotient_mul_add_remainder_eq : ∀ (a b : R), = a

The property that links the quotient and remainder functions. This allows us to compute GCDs and LCMs.

• r : RRProp

A well-founded relation on R, satisfying r (a % b) b. This ensures that the GCD algorithm always terminates.

• r_wellFounded : WellFounded EuclideanDomain.r

The relation r must be well-founded. This ensures that the GCD algorithm always terminates.

• remainder_lt : ∀ (a : R) {b : R}, b 0

The relation r satisfies r (a % b) b.

• mul_left_not_lt : ∀ (a : R) {b : R}, b 0¬EuclideanDomain.r (a * b) a

An additional constraint on r.

Instances
theorem EuclideanDomain.quotient_zero {R : Type u} [self : ] (a : R) :

Division by zero should always give zero by convention.

theorem EuclideanDomain.quotient_mul_add_remainder_eq {R : Type u} [self : ] (a : R) (b : R) :
= a

The property that links the quotient and remainder functions. This allows us to compute GCDs and LCMs.

theorem EuclideanDomain.r_wellFounded {R : Type u} [self : ] :
WellFounded EuclideanDomain.r

The relation r must be well-founded. This ensures that the GCD algorithm always terminates.

theorem EuclideanDomain.remainder_lt {R : Type u} [self : ] (a : R) {b : R} :
b 0

The relation r satisfies r (a % b) b.

theorem EuclideanDomain.mul_left_not_lt {R : Type u} [self : ] (a : R) {b : R} :
b 0¬EuclideanDomain.r (a * b) a

An additional constraint on r.

Equations
• EuclideanDomain.wellFoundedRelation = { rel := EuclideanDomain.r, wf := }
Instances For
@[instance 70]
instance EuclideanDomain.instDiv {R : Type u} [] :
Div R
Equations
• EuclideanDomain.instDiv = { div := EuclideanDomain.quotient }
@[instance 70]
instance EuclideanDomain.instMod {R : Type u} [] :
Mod R
Equations
• EuclideanDomain.instMod = { mod := EuclideanDomain.remainder }
theorem EuclideanDomain.div_add_mod {R : Type u} [] (a : R) (b : R) :
b * (a / b) + a % b = a
theorem EuclideanDomain.mod_add_div {R : Type u} [] (a : R) (b : R) :
a % b + b * (a / b) = a
theorem EuclideanDomain.mod_add_div' {R : Type u} [] (m : R) (k : R) :
m % k + m / k * k = m
theorem EuclideanDomain.div_add_mod' {R : Type u} [] (m : R) (k : R) :
m / k * k + m % k = m
theorem EuclideanDomain.mod_eq_sub_mul_div {R : Type u_1} [] (a : R) (b : R) :
a % b = a - b * (a / b)
theorem EuclideanDomain.mod_lt {R : Type u} [] (a : R) {b : R} :
b 0EuclideanDomain.r (a % b) b
theorem EuclideanDomain.mul_right_not_lt {R : Type u} [] {a : R} (b : R) (h : a 0) :
@[simp]
theorem EuclideanDomain.mod_zero {R : Type u} [] (a : R) :
a % 0 = a
theorem EuclideanDomain.lt_one {R : Type u} [] (a : R) :
a = 0
theorem EuclideanDomain.val_dvd_le {R : Type u} [] (a : R) (b : R) :
b aa 0
@[simp]
theorem EuclideanDomain.div_zero {R : Type u} [] (a : R) :
a / 0 = 0
@[irreducible]
theorem EuclideanDomain.GCD.induction {R : Type u} [] {P : RRProp} (a : R) (b : R) (H0 : ∀ (x : R), P 0 x) (H1 : ∀ (a b : R), a 0P (b % a) aP a b) :
P a b
@[irreducible]
def EuclideanDomain.gcd {R : Type u} [] [] (a : R) (b : R) :
R

gcd a b is a (non-unique) element such that gcd a b ∣ a gcd a b ∣ b, and for any element c such that c ∣ a and c ∣ b, then c ∣ gcd a b

Equations
Instances For
@[simp]
theorem EuclideanDomain.gcd_zero_left {R : Type u} [] [] (a : R) :
= a
@[irreducible]
def EuclideanDomain.xgcdAux {R : Type u} [] [] (r : R) (s : R) (t : R) (r' : R) (s' : R) (t' : R) :
R × R × R

An implementation of the extended GCD algorithm. At each step we are computing a triple (r, s, t), where r is the next value of the GCD algorithm, to compute the greatest common divisor of the input (say x and y), and s and t are the coefficients in front of x and y to obtain r (i.e. r = s * x + t * y). The function xgcdAux takes in two triples, and from these recursively computes the next triple:

xgcdAux (r, s, t) (r', s', t') = xgcdAux (r' % r, s' - (r' / r) * s, t' - (r' / r) * t) (r, s, t)

Equations
Instances For
@[simp]
theorem EuclideanDomain.xgcd_zero_left {R : Type u} [] [] {s : R} {t : R} {r' : R} {s' : R} {t' : R} :
EuclideanDomain.xgcdAux 0 s t r' s' t' = (r', s', t')
theorem EuclideanDomain.xgcdAux_rec {R : Type u} [] [] {r : R} {s : R} {t : R} {r' : R} {s' : R} {t' : R} (h : r 0) :
EuclideanDomain.xgcdAux r s t r' s' t' = EuclideanDomain.xgcdAux (r' % r) (s' - r' / r * s) (t' - r' / r * t) r s t
def EuclideanDomain.xgcd {R : Type u} [] [] (x : R) (y : R) :
R × R

Use the extended GCD algorithm to generate the a and b values satisfying gcd x y = x * a + y * b.

Equations
Instances For
def EuclideanDomain.gcdA {R : Type u} [] [] (x : R) (y : R) :
R

The extended GCD a value in the equation gcd x y = x * a + y * b.

Equations
• = ().1
Instances For
def EuclideanDomain.gcdB {R : Type u} [] [] (x : R) (y : R) :
R

The extended GCD b value in the equation gcd x y = x * a + y * b.

Equations
• = ().2
Instances For
@[simp]
theorem EuclideanDomain.gcdA_zero_left {R : Type u} [] [] {s : R} :
@[simp]
theorem EuclideanDomain.gcdB_zero_left {R : Type u} [] [] {s : R} :
theorem EuclideanDomain.xgcd_val {R : Type u} [] [] (x : R) (y : R) :
= (, )
def EuclideanDomain.lcm {R : Type u} [] [] (x : R) (y : R) :
R

lcm a b is a (non-unique) element such that a ∣ lcm a b b ∣ lcm a b, and for any element c such that a ∣ c and b ∣ c, then lcm a b ∣ c

Equations
Instances For