Extended GCD and divisibility over ℤ

Main definitions

• Given x y : ℕ, xgcd x y computes the pair of integers (a, b) such that gcd x y = x * a + y * b. gcdA x y and gcdB x y are defined to be a and b, respectively.

Main statements

• gcd_eq_gcd_ab: Bézout's lemma, given x y : ℕ, gcd x y = x * gcdA x y + y * gcdB x y.

Tags

Bézout's lemma, Bezout's lemma

Extended Euclidean algorithm

def Nat.xgcdAux : ℕ → ℤ → ℤ → ℕ → ℤ → ℤ → ℕ × ℤ × ℤ

Helper function for the extended GCD algorithm (Nat.xgcd).

Equations

• Nat.xgcdAux 0 x✝³ x✝² x✝¹ x✝ x = (x✝¹, x✝, x)
• Nat.xgcdAux (Nat.succ k) x✝³ x✝² x✝¹ x✝ x = let_fun this := ⋯; let q := x✝¹ / Nat.succ k; Nat.xgcdAux (x✝¹ % Nat.succ k) (x✝ - ↑q * x✝³) (x - ↑q * x✝²) (Nat.succ k) x✝³ x✝²

theorem Nat.xgcdAux_zero {s : ℤ} {t : ℤ} {r' : ℕ} {s' : ℤ} {t' : ℤ} : Nat.xgcdAux 0 s t r' s' t' = (r', s', t')

theorem Nat.xgcdAux_succ {k : ℕ} {s : ℤ} {t : ℤ} {r' : ℕ} {s' : ℤ} {t' : ℤ} : Nat.xgcdAux (Nat.succ k) s t r' s' t' = Nat.xgcdAux (r' % Nat.succ k) (s' - ↑r' / ↑(Nat.succ k) * s) (t' - ↑r' / ↑(Nat.succ k) * t) (Nat.succ k) s t

@[simp]

theorem Nat.xgcd_zero_left {s : ℤ} {t : ℤ} {r' : ℕ} {s' : ℤ} {t' : ℤ} : Nat.xgcdAux 0 s t r' s' t' = (r', s', t')

theorem Nat.xgcdAux_rec {r : ℕ} {s : ℤ} {t : ℤ} {r' : ℕ} {s' : ℤ} {t' : ℤ} (h : 0 < r) : Nat.xgcdAux r s t r' s' t' = Nat.xgcdAux (r' % r) (s' - ↑r' / ↑r * s) (t' - ↑r' / ↑r * t) r s t

def Nat.xgcd (x : ℕ) (y : ℕ) : ℤ × ℤ

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

Equations

• Nat.xgcd x y = (Nat.xgcdAux x 1 0 y 0 1).2

def Nat.gcdA (x : ℕ) (y : ℕ) : ℤ

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

Equations

• Nat.gcdA x y = (Nat.xgcd x y).1

def Nat.gcdB (x : ℕ) (y : ℕ) : ℤ

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

Equations

• Nat.gcdB x y = (Nat.xgcd x y).2

@[simp]

theorem Nat.gcdA_zero_left {s : ℕ} : Nat.gcdA 0 s = 0

@[simp]

theorem Nat.gcdB_zero_left {s : ℕ} : Nat.gcdB 0 s = 1

@[simp]

theorem Nat.gcdA_zero_right {s : ℕ} (h : s ≠ 0) : Nat.gcdA s 0 = 1

@[simp]

theorem Nat.gcdB_zero_right {s : ℕ} (h : s ≠ 0) : Nat.gcdB s 0 = 0

@[simp]

theorem Nat.xgcdAux_fst (x : ℕ) (y : ℕ) (s : ℤ) (t : ℤ) (s' : ℤ) (t' : ℤ) : (Nat.xgcdAux x s t y s' t').1 = Nat.gcd x y

theorem Nat.xgcdAux_val (x : ℕ) (y : ℕ) : Nat.xgcdAux x 1 0 y 0 1 = (Nat.gcd x y, Nat.xgcd x y)

theorem Nat.xgcd_val (x : ℕ) (y : ℕ) : Nat.xgcd x y = (Nat.gcdA x y, Nat.gcdB x y)

theorem Nat.xgcdAux_P (x : ℕ) (y : ℕ) {r : ℕ} {r' : ℕ} {s : ℤ} {t : ℤ} {s' : ℤ} {t' : ℤ} : Nat.P x y (r, s, t) → Nat.P x y (r', s', t') → Nat.P x y (Nat.xgcdAux r s t r' s' t')

theorem Nat.gcd_eq_gcd_ab (x : ℕ) (y : ℕ) : ↑(Nat.gcd x y) = ↑x * Nat.gcdA x y + ↑y * Nat.gcdB x y

Bézout's lemma: given x y : ℕ, gcd x y = x * a + y * b, where a = gcd_a x y and b = gcd_b x y are computed by the extended Euclidean algorithm.

theorem Nat.exists_mul_emod_eq_gcd {k : ℕ} {n : ℕ} (hk : Nat.gcd n k < k) : ∃ (m : ℕ), n * m % k = Nat.gcd n k

theorem Nat.exists_mul_emod_eq_one_of_coprime {k : ℕ} {n : ℕ} (hkn : Nat.Coprime n k) (hk : 1 < k) : ∃ (m : ℕ), n * m % k = 1

Divisibility over ℤ

theorem Int.gcd_def (i : ℤ) (j : ℤ) : Int.gcd i j = Nat.gcd (Int.natAbs i) (Int.natAbs j)

theorem Int.coe_nat_gcd (m : ℕ) (n : ℕ) : Int.gcd ↑m ↑n = Nat.gcd m n

def Int.gcdA : ℤ → ℤ → ℤ

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

Equations

• Int.gcdA x✝ x = match x✝, x with | Int.ofNat m, n => Nat.gcdA m (Int.natAbs n) | Int.negSucc m, n => -Nat.gcdA (Nat.succ m) (Int.natAbs n)

def Int.gcdB : ℤ → ℤ → ℤ

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

Equations

• Int.gcdB x✝ x = match x✝, x with | m, Int.ofNat n => Nat.gcdB (Int.natAbs m) n | m, Int.negSucc n => -Nat.gcdB (Int.natAbs m) (Nat.succ n)

theorem Int.gcd_eq_gcd_ab (x : ℤ) (y : ℤ) : ↑(Int.gcd x y) = x * Int.gcdA x y + y * Int.gcdB x y

Bézout's lemma

theorem Int.natAbs_ediv (a : ℤ) (b : ℤ) (H : b ∣ a) : Int.natAbs (a / b) = Int.natAbs a / Int.natAbs b

theorem Int.dvd_of_mul_dvd_mul_left {i : ℤ} {j : ℤ} {k : ℤ} (k_non_zero : k ≠ 0) (H : k * i ∣ k * j) : i ∣ j

special case of mul_dvd_mul_iff_right for ℤ. Duplicated here to keep simple imports for this file.

theorem Int.dvd_of_mul_dvd_mul_right {i : ℤ} {j : ℤ} {k : ℤ} (k_non_zero : k ≠ 0) (H : i * k ∣ j * k) : i ∣ j

special case of mul_dvd_mul_iff_right for ℤ. Duplicated here to keep simple imports for this file.

theorem Int.lcm_def (i : ℤ) (j : ℤ) : Int.lcm i j = Nat.lcm (Int.natAbs i) (Int.natAbs j)

theorem Int.coe_nat_lcm (m : ℕ) (n : ℕ) : Int.lcm ↑m ↑n = Nat.lcm m n

theorem Int.dvd_gcd {i : ℤ} {j : ℤ} {k : ℤ} (h1 : k ∣ i) (h2 : k ∣ j) : k ∣ ↑(Int.gcd i j)

theorem Int.gcd_mul_lcm (i : ℤ) (j : ℤ) : Int.gcd i j * Int.lcm i j = Int.natAbs (i * j)

theorem Int.gcd_comm (i : ℤ) (j : ℤ) : Int.gcd i j = Int.gcd j i

theorem Int.gcd_assoc (i : ℤ) (j : ℤ) (k : ℤ) : Int.gcd (↑(Int.gcd i j)) k = Int.gcd i ↑(Int.gcd j k)

@[simp]

theorem Int.gcd_self (i : ℤ) : Int.gcd i i = Int.natAbs i

@[simp]

theorem Int.gcd_zero_left (i : ℤ) : Int.gcd 0 i = Int.natAbs i

@[simp]

theorem Int.gcd_zero_right (i : ℤ) : Int.gcd i 0 = Int.natAbs i

theorem Int.gcd_mul_left (i : ℤ) (j : ℤ) (k : ℤ) : Int.gcd (i * j) (i * k) = Int.natAbs i * Int.gcd j k

theorem Int.gcd_mul_right (i : ℤ) (j : ℤ) (k : ℤ) : Int.gcd (i * j) (k * j) = Int.gcd i k * Int.natAbs j

theorem Int.gcd_pos_of_ne_zero_left {i : ℤ} (j : ℤ) (hi : i ≠ 0) : 0 < Int.gcd i j

theorem Int.gcd_pos_of_ne_zero_right (i : ℤ) {j : ℤ} (hj : j ≠ 0) : 0 < Int.gcd i j

theorem Int.gcd_eq_zero_iff {i : ℤ} {j : ℤ} : Int.gcd i j = 0 ↔ i = 0 ∧ j = 0

theorem Int.gcd_pos_iff {i : ℤ} {j : ℤ} : 0 < Int.gcd i j ↔ i ≠ 0 ∨ j ≠ 0

theorem Int.gcd_div {i : ℤ} {j : ℤ} {k : ℤ} (H1 : k ∣ i) (H2 : k ∣ j) : Int.gcd (i / k) (j / k) = Int.gcd i j / Int.natAbs k

theorem Int.gcd_div_gcd_div_gcd {i : ℤ} {j : ℤ} (H : 0 < Int.gcd i j) : Int.gcd (i / ↑(Int.gcd i j)) (j / ↑(Int.gcd i j)) = 1

theorem Int.gcd_dvd_gcd_of_dvd_left {i : ℤ} {k : ℤ} (j : ℤ) (H : i ∣ k) : Int.gcd i j ∣ Int.gcd k j

theorem Int.gcd_dvd_gcd_of_dvd_right {i : ℤ} {k : ℤ} (j : ℤ) (H : i ∣ k) : Int.gcd j i ∣ Int.gcd j k

theorem Int.gcd_dvd_gcd_mul_left (i : ℤ) (j : ℤ) (k : ℤ) : Int.gcd i j ∣ Int.gcd (k * i) j

theorem Int.gcd_dvd_gcd_mul_right (i : ℤ) (j : ℤ) (k : ℤ) : Int.gcd i j ∣ Int.gcd (i * k) j

theorem Int.gcd_dvd_gcd_mul_left_right (i : ℤ) (j : ℤ) (k : ℤ) : Int.gcd i j ∣ Int.gcd i (k * j)

theorem Int.gcd_dvd_gcd_mul_right_right (i : ℤ) (j : ℤ) (k : ℤ) : Int.gcd i j ∣ Int.gcd i (j * k)

theorem Int.gcd_eq_one_of_gcd_mul_right_eq_one_left {a : ℤ} {m : ℕ} {n : ℕ} (h : Int.gcd a (↑m * ↑n) = 1) : Int.gcd a ↑m = 1

If gcd a (m * n) = 1, then gcd a m = 1.

theorem Int.gcd_eq_one_of_gcd_mul_right_eq_one_right {a : ℤ} {m : ℕ} {n : ℕ} (h : Int.gcd a (↑m * ↑n) = 1) : Int.gcd a ↑n = 1

If gcd a (m * n) = 1, then gcd a n = 1.

theorem Int.gcd_eq_left {i : ℤ} {j : ℤ} (H : i ∣ j) : Int.gcd i j = Int.natAbs i

theorem Int.gcd_eq_right {i : ℤ} {j : ℤ} (H : j ∣ i) : Int.gcd i j = Int.natAbs j

theorem Int.ne_zero_of_gcd {x : ℤ} {y : ℤ} (hc : Int.gcd x y ≠ 0) : x ≠ 0 ∨ y ≠ 0

theorem Int.exists_gcd_one {m : ℤ} {n : ℤ} (H : 0 < Int.gcd m n) : ∃ (m' : ℤ) (n' : ℤ), Int.gcd m' n' = 1 ∧ m = m' * ↑(Int.gcd m n) ∧ n = n' * ↑(Int.gcd m n)

theorem Int.exists_gcd_one' {m : ℤ} {n : ℤ} (H : 0 < Int.gcd m n) : ∃ (g : ℕ) (m' : ℤ) (n' : ℤ), 0 < g ∧ Int.gcd m' n' = 1 ∧ m = m' * ↑g ∧ n = n' * ↑g

theorem Int.pow_dvd_pow_iff {m : ℤ} {n : ℤ} {k : ℕ} (k0 : k ≠ 0) : m ^ k ∣ n ^ k ↔ m ∣ n

theorem Int.gcd_dvd_iff {a : ℤ} {b : ℤ} {n : ℕ} : Int.gcd a b ∣ n ↔ ∃ (x : ℤ) (y : ℤ), ↑n = a * x + b * y

theorem Int.gcd_greatest {a : ℤ} {b : ℤ} {d : ℤ} (hd_pos : 0 ≤ d) (hda : d ∣ a) (hdb : d ∣ b) (hd : ∀ (e : ℤ), e ∣ a → e ∣ b → e ∣ d) : d = ↑(Int.gcd a b)

theorem Int.dvd_of_dvd_mul_left_of_gcd_one {a : ℤ} {b : ℤ} {c : ℤ} (habc : a ∣ b * c) (hab : Int.gcd a c = 1) : a ∣ b

Euclid's lemma: if a ∣ b * c and gcd a c = 1 then a ∣ b. Compare with IsCoprime.dvd_of_dvd_mul_left and UniqueFactorizationMonoid.dvd_of_dvd_mul_left_of_no_prime_factors

theorem Int.dvd_of_dvd_mul_right_of_gcd_one {a : ℤ} {b : ℤ} {c : ℤ} (habc : a ∣ b * c) (hab : Int.gcd a b = 1) : a ∣ c

Euclid's lemma: if a ∣ b * c and gcd a b = 1 then a ∣ c. Compare with IsCoprime.dvd_of_dvd_mul_right and UniqueFactorizationMonoid.dvd_of_dvd_mul_right_of_no_prime_factors

theorem Int.gcd_least_linear {a : ℤ} {b : ℤ} (ha : a ≠ 0) : IsLeast {n : ℕ | 0 < n ∧ ∃ (x : ℤ) (y : ℤ), ↑n = a * x + b * y} (Int.gcd a b)

For nonzero integers a and b, gcd a b is the smallest positive natural number that can be written in the form a * x + b * y for some pair of integers x and y

lcm

theorem Int.lcm_comm (i : ℤ) (j : ℤ) : Int.lcm i j = Int.lcm j i

theorem Int.lcm_assoc (i : ℤ) (j : ℤ) (k : ℤ) : Int.lcm (↑(Int.lcm i j)) k = Int.lcm i ↑(Int.lcm j k)

@[simp]

theorem Int.lcm_zero_left (i : ℤ) : Int.lcm 0 i = 0

@[simp]

theorem Int.lcm_zero_right (i : ℤ) : Int.lcm i 0 = 0

@[simp]

theorem Int.lcm_one_left (i : ℤ) : Int.lcm 1 i = Int.natAbs i

@[simp]

theorem Int.lcm_one_right (i : ℤ) : Int.lcm i 1 = Int.natAbs i

theorem Int.lcm_dvd {i : ℤ} {j : ℤ} {k : ℤ} : i ∣ k → j ∣ k → ↑(Int.lcm i j) ∣ k

theorem Int.lcm_mul_left {m : ℤ} {n : ℤ} {k : ℤ} : Int.lcm (m * n) (m * k) = Int.natAbs m * Int.lcm n k

theorem Int.lcm_mul_right {m : ℤ} {n : ℤ} {k : ℤ} : Int.lcm (m * n) (k * n) = Int.lcm m k * Int.natAbs n

theorem gcd_nsmul_eq_zero {M : Type u_1} [AddMonoid M] (x : M) {m : ℕ} {n : ℕ} (hm : m • x = 0) (hn : n • x = 0) : Nat.gcd m n • x = 0

theorem pow_gcd_eq_one {M : Type u_1} [Monoid M] (x : M) {m : ℕ} {n : ℕ} (hm : x ^ m = 1) (hn : x ^ n = 1) : x ^ Nat.gcd m n = 1

theorem Commute.pow_eq_pow_iff_of_coprime {α : Type u_1} [GroupWithZero α] {a : α} {b : α} {m : ℕ} {n : ℕ} (hab : Commute a b) (hmn : Nat.Coprime m n) : a ^ m = b ^ n ↔ ∃ (c : α), a = c ^ n ∧ b = c ^ m

theorem pow_eq_pow_iff_of_coprime {α : Type u_1} [CommGroupWithZero α] {a : α} {b : α} {m : ℕ} {n : ℕ} (hmn : Nat.Coprime m n) : a ^ m = b ^ n ↔ ∃ (c : α), a = c ^ n ∧ b = c ^ m

theorem pow_mem_range_pow_of_coprime {α : Type u_1} [CommGroupWithZero α] {m : ℕ} {n : ℕ} (hmn : Nat.Coprime m n) (a : α) : (a ^ m ∈ Set.range fun (x : α) => x ^ n) ↔ a ∈ Set.range fun (x : α) => x ^ n