ℕ and ℤ are normalized GCD monoids.

Main statements

• ℕ is a GCDMonoid
• ℕ is a NormalizedGCDMonoid
• ℤ is a NormalizationMonoid
• ℤ is a GCDMonoid
• ℤ is a NormalizedGCDMonoid

Tags

natural numbers, integers, normalization monoid, gcd monoid, greatest common divisor

instance instGCDMonoidNat : GCDMonoid ℕ

ℕ is a gcd_monoid.

theorem gcd_eq_nat_gcd (m n : ℕ) : gcd m n = m.gcd n

theorem lcm_eq_nat_lcm (m n : ℕ) : lcm m n = m.lcm n

instance instNormalizedGCDMonoidNat : NormalizedGCDMonoid ℕ

instance Int.normalizationMonoid : NormalizationMonoid ℤ

theorem Int.normUnit_eq (z : ℤ) : normUnit z = if 0 ≤ z then 1 else -1

theorem Int.normalize_of_nonneg {z : ℤ} (h : 0 ≤ z) : normalize z = z

theorem Int.normalize_of_nonpos {z : ℤ} (h : z ≤ 0) : normalize z = -z

theorem Int.normalize_coe_nat (n : ℕ) : normalize ↑n = ↑n

theorem Int.abs_eq_normalize (z : ℤ) : |z| = normalize z

theorem Int.nonneg_of_normalize_eq_self {z : ℤ} (hz : normalize z = z) : 0 ≤ z

theorem Int.nonneg_iff_normalize_eq_self (z : ℤ) : normalize z = z ↔ 0 ≤ z

theorem Int.eq_of_associated_of_nonneg {a b : ℤ} (h : Associated a b) (ha : 0 ≤ a) (hb : 0 ≤ b) : a = b

instance Int.instGCDMonoid : GCDMonoid ℤ

instance Int.instNormalizedGCDMonoid : NormalizedGCDMonoid ℤ

theorem Int.coe_gcd (i j : ℤ) : ↑(i.gcd j) = GCDMonoid.gcd i j

theorem Int.coe_lcm (i j : ℤ) : ↑(i.lcm j) = GCDMonoid.lcm i j

theorem Int.natAbs_gcd (i j : ℤ) : (GCDMonoid.gcd i j).natAbs = i.gcd j

theorem Int.natAbs_lcm (i j : ℤ) : (GCDMonoid.lcm i j).natAbs = i.lcm j

theorem Int.exists_unit_of_abs (a : ℤ) : ∃ (u : ℤ) (_ : IsUnit u), ↑a.natAbs = u * a

theorem Int.gcd_eq_natAbs {a b : ℤ} : a.gcd b = a.natAbs.gcd b.natAbs

def associatesIntEquivNat : Associates ℤ ≃ ℕ

Maps an associate class of integers consisting of -n, n to n : ℕ

theorem Int.associated_natAbs (k : ℤ) : Associated k ↑k.natAbs

theorem Int.associated_iff_natAbs {a b : ℤ} : Associated a b ↔ a.natAbs = b.natAbs

theorem Int.associated_iff {a b : ℤ} : Associated a b ↔ a = b ∨ a = -b