GCD and LCM operations on multisets

Main definitions

• Multiset.gcd - the greatest common denominator of a Multiset of elements of a GCDMonoid
• Multiset.lcm - the least common multiple of a Multiset of elements of a GCDMonoid

Implementation notes

TODO: simplify with a tactic and Data.Multiset.Lattice

Tags

multiset, gcd

LCM

def Multiset.lcm {α : Type u_1} [CancelCommMonoidWithZero α] [NormalizedGCDMonoid α] (s : Multiset α) : α

Least common multiple of a multiset

Equations

• Multiset.lcm s = Multiset.fold lcm 1 s

@[simp]

theorem Multiset.lcm_zero {α : Type u_1} [CancelCommMonoidWithZero α] [NormalizedGCDMonoid α] : Multiset.lcm 0 = 1

@[simp]

theorem Multiset.lcm_cons {α : Type u_1} [CancelCommMonoidWithZero α] [NormalizedGCDMonoid α] (a : α) (s : Multiset α) : Multiset.lcm (a ::ₘ s) = lcm a (Multiset.lcm s)

@[simp]

theorem Multiset.lcm_singleton {α : Type u_1} [CancelCommMonoidWithZero α] [NormalizedGCDMonoid α] {a : α} : Multiset.lcm {a} = normalize a

@[simp]

theorem Multiset.lcm_add {α : Type u_1} [CancelCommMonoidWithZero α] [NormalizedGCDMonoid α] (s₁ : Multiset α) (s₂ : Multiset α) : Multiset.lcm (s₁ + s₂) = lcm (Multiset.lcm s₁) (Multiset.lcm s₂)

theorem Multiset.lcm_dvd {α : Type u_1} [CancelCommMonoidWithZero α] [NormalizedGCDMonoid α] {s : Multiset α} {a : α} : Multiset.lcm s ∣ a ↔ ∀ b ∈ s, b ∣ a

theorem Multiset.dvd_lcm {α : Type u_1} [CancelCommMonoidWithZero α] [NormalizedGCDMonoid α] {s : Multiset α} {a : α} (h : a ∈ s) : a ∣ Multiset.lcm s

theorem Multiset.lcm_mono {α : Type u_1} [CancelCommMonoidWithZero α] [NormalizedGCDMonoid α] {s₁ : Multiset α} {s₂ : Multiset α} (h : s₁ ⊆ s₂) : Multiset.lcm s₁ ∣ Multiset.lcm s₂

@[simp]

theorem Multiset.normalize_lcm {α : Type u_1} [CancelCommMonoidWithZero α] [NormalizedGCDMonoid α] (s : Multiset α) : normalize (Multiset.lcm s) = Multiset.lcm s

@[simp]

theorem Multiset.lcm_eq_zero_iff {α : Type u_1} [CancelCommMonoidWithZero α] [NormalizedGCDMonoid α] [Nontrivial α] (s : Multiset α) : Multiset.lcm s = 0 ↔ 0 ∈ s

@[simp]

theorem Multiset.lcm_dedup {α : Type u_1} [CancelCommMonoidWithZero α] [NormalizedGCDMonoid α] [DecidableEq α] (s : Multiset α) : Multiset.lcm (Multiset.dedup s) = Multiset.lcm s

@[simp]

theorem Multiset.lcm_ndunion {α : Type u_1} [CancelCommMonoidWithZero α] [NormalizedGCDMonoid α] [DecidableEq α] (s₁ : Multiset α) (s₂ : Multiset α) : Multiset.lcm (Multiset.ndunion s₁ s₂) = lcm (Multiset.lcm s₁) (Multiset.lcm s₂)

@[simp]

theorem Multiset.lcm_union {α : Type u_1} [CancelCommMonoidWithZero α] [NormalizedGCDMonoid α] [DecidableEq α] (s₁ : Multiset α) (s₂ : Multiset α) : Multiset.lcm (s₁ ∪ s₂) = lcm (Multiset.lcm s₁) (Multiset.lcm s₂)

@[simp]

theorem Multiset.lcm_ndinsert {α : Type u_1} [CancelCommMonoidWithZero α] [NormalizedGCDMonoid α] [DecidableEq α] (a : α) (s : Multiset α) : Multiset.lcm (Multiset.ndinsert a s) = lcm a (Multiset.lcm s)

GCD

def Multiset.gcd {α : Type u_1} [CancelCommMonoidWithZero α] [NormalizedGCDMonoid α] (s : Multiset α) : α

Greatest common divisor of a multiset

Equations

• Multiset.gcd s = Multiset.fold gcd 0 s

@[simp]

theorem Multiset.gcd_zero {α : Type u_1} [CancelCommMonoidWithZero α] [NormalizedGCDMonoid α] : Multiset.gcd 0 = 0

@[simp]

theorem Multiset.gcd_cons {α : Type u_1} [CancelCommMonoidWithZero α] [NormalizedGCDMonoid α] (a : α) (s : Multiset α) : Multiset.gcd (a ::ₘ s) = gcd a (Multiset.gcd s)

@[simp]

theorem Multiset.gcd_singleton {α : Type u_1} [CancelCommMonoidWithZero α] [NormalizedGCDMonoid α] {a : α} : Multiset.gcd {a} = normalize a

@[simp]

theorem Multiset.gcd_add {α : Type u_1} [CancelCommMonoidWithZero α] [NormalizedGCDMonoid α] (s₁ : Multiset α) (s₂ : Multiset α) : Multiset.gcd (s₁ + s₂) = gcd (Multiset.gcd s₁) (Multiset.gcd s₂)

theorem Multiset.dvd_gcd {α : Type u_1} [CancelCommMonoidWithZero α] [NormalizedGCDMonoid α] {s : Multiset α} {a : α} : a ∣ Multiset.gcd s ↔ ∀ b ∈ s, a ∣ b

theorem Multiset.gcd_dvd {α : Type u_1} [CancelCommMonoidWithZero α] [NormalizedGCDMonoid α] {s : Multiset α} {a : α} (h : a ∈ s) : Multiset.gcd s ∣ a

theorem Multiset.gcd_mono {α : Type u_1} [CancelCommMonoidWithZero α] [NormalizedGCDMonoid α] {s₁ : Multiset α} {s₂ : Multiset α} (h : s₁ ⊆ s₂) : Multiset.gcd s₂ ∣ Multiset.gcd s₁

@[simp]

theorem Multiset.normalize_gcd {α : Type u_1} [CancelCommMonoidWithZero α] [NormalizedGCDMonoid α] (s : Multiset α) : normalize (Multiset.gcd s) = Multiset.gcd s

theorem Multiset.gcd_eq_zero_iff {α : Type u_1} [CancelCommMonoidWithZero α] [NormalizedGCDMonoid α] (s : Multiset α) : Multiset.gcd s = 0 ↔ ∀ x ∈ s, x = 0

theorem Multiset.gcd_map_mul {α : Type u_1} [CancelCommMonoidWithZero α] [NormalizedGCDMonoid α] (a : α) (s : Multiset α) : Multiset.gcd (Multiset.map (fun (x : α) => a * x) s) = normalize a * Multiset.gcd s

@[simp]

theorem Multiset.gcd_dedup {α : Type u_1} [CancelCommMonoidWithZero α] [NormalizedGCDMonoid α] [DecidableEq α] (s : Multiset α) : Multiset.gcd (Multiset.dedup s) = Multiset.gcd s

@[simp]

theorem Multiset.gcd_ndunion {α : Type u_1} [CancelCommMonoidWithZero α] [NormalizedGCDMonoid α] [DecidableEq α] (s₁ : Multiset α) (s₂ : Multiset α) : Multiset.gcd (Multiset.ndunion s₁ s₂) = gcd (Multiset.gcd s₁) (Multiset.gcd s₂)

@[simp]

theorem Multiset.gcd_union {α : Type u_1} [CancelCommMonoidWithZero α] [NormalizedGCDMonoid α] [DecidableEq α] (s₁ : Multiset α) (s₂ : Multiset α) : Multiset.gcd (s₁ ∪ s₂) = gcd (Multiset.gcd s₁) (Multiset.gcd s₂)

@[simp]

theorem Multiset.gcd_ndinsert {α : Type u_1} [CancelCommMonoidWithZero α] [NormalizedGCDMonoid α] [DecidableEq α] (a : α) (s : Multiset α) : Multiset.gcd (Multiset.ndinsert a s) = gcd a (Multiset.gcd s)

theorem Multiset.extract_gcd' {α : Type u_1} [CancelCommMonoidWithZero α] [NormalizedGCDMonoid α] (s : Multiset α) (t : Multiset α) (hs : ∃ x ∈ s, x ≠ 0) (ht : s = Multiset.map (fun (x : α) => Multiset.gcd s * x) t) : Multiset.gcd t = 1

theorem Multiset.extract_gcd {α : Type u_1} [CancelCommMonoidWithZero α] [NormalizedGCDMonoid α] (s : Multiset α) (hs : s ≠ 0) : ∃ (t : Multiset α), s = Multiset.map (fun (x : α) => Multiset.gcd s * x) t ∧ Multiset.gcd t = 1