blob: ab7048664be32da9103f34223b929ad4d7731c51 [file]
/-
Copyright (c) 2024 Lean FRO, LLC. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Jeremy Avigad, Mario Carneiro, Joe Hendrix
-/
prelude
import Init.Data.Int.DivModLemmas
import Init.Data.Nat.Lemmas
/-
Int div and mod lemmas that omega does not depend on
-/
namespace Int
/-! ediv -/
theorem ediv_ofNat_negSucc (m n : Nat) : m / -[n+1] = -ofNat (m / Nat.succ n) := rfl
theorem ediv_negSucc_zero (m : Nat) : -[m+1] / 0 = 0 := rfl
theorem ediv_negSucc_succ (m n : Nat) : -[m+1] / (n + 1 : Nat) = -((m / (n + 1)) : Nat) + (-1) := by
simp [HDiv.hDiv, Div.div, Int.ediv, Int.negSucc_coe', Int.sub_eq_add_neg]
theorem ediv_negSucc_negSucc (m n : Nat) : -[m+1] / -[n+1] = ((m / (n + 1) + 1) : Nat) := rfl
/-! emod -/
theorem emod_ofNat (a : Nat) (b : Int) : Nat.cast a % b = Nat.cast (a % b.natAbs) := rfl
theorem emod_negSucc (a : Nat) (b : Int) : -[a+1] % b = (b.natAbs : Int) - (a % b.natAbs + 1) := rfl
theorem emod_neg_iff (m n : Int) : m % n < 0 ↔ (m < 0 ∧ n = 0) := by
change Int.emod m n < 0 ↔ (m < 0 ∧ n = 0)
match m with
| ofNat m =>
simp [-ofNat_emod, Int.emod, ofNat_not_neg]
| -[m+1] =>
simp [-ofNat_emod, -Int.natCast_add, Int.emod, Int.subNatNat_eq_coe, negSucc_lt_zero, Int.sub_lt_iff]
apply Iff.intro
· intro p
replace p := Nat.le_of_succ_le_succ p
by_cases nz : n = 0
· exact nz
· have q : n.natAbs > 0 := Int.natAbs_pos.mpr nz
have r : m % n.natAbs < n.natAbs := Nat.mod_lt _ q
exact False.elim (Nat.not_le_of_gt r p)
· intro p
simp [p]
theorem emod_lt (a b : Int) (h : b ≠ 0) : a % b < Int.natAbs b := by
rw [emod_as_nat_mod]
by_cases p : a ≥ 0
· simp [p, -Int.ofNat_emod]
exact Nat.mod_lt _ (by omega)
· simp [p, -Int.ofNat_emod]
apply Int.sub_lt_self
apply Int.succ_ofNat_pos
@[simp] theorem sub_emod_self_left (n y : Int) : (n - y) % n = (-y) % n := by
simp [Int.sub_eq_add_neg]
/-! dvd -/
@[simp] theorem dvd_natCast_natCast (a b : Nat) : (a : Int) ∣ (b : Int) ↔ a ∣ b := by
simp [Int.dvd_iff_mod_eq_zero, Nat.dvd_iff_mod_eq_zero, mod, Int.emod_ofNat, -emod_ofNat]
apply Int.ofNat_inj
@[simp] theorem dvd_negSucc (a : Int) (b : Nat) : a ∣ -[b +1] ↔ a ∣ (b+1 : Nat) := by
simp only [Int.dvd_def]
apply Iff.intro
· intro ⟨c, p⟩
apply Exists.intro (-c)
simp only [Int.mul_neg, ← p]
rfl
· intro ⟨c, p⟩
apply Exists.intro (-c)
simp only [Int.mul_neg, ← p]
rfl
@[simp] theorem negSucc_dvd (a : Nat) (b : Int) : -[a +1] ∣ b ↔ (((a+1 : Nat) : Int) ∣ b) := by
apply Iff.intro
· intro ⟨c, p⟩
apply Exists.intro (-c)
match c with
| .ofNat 0 =>
simp_all
| .ofNat (.succ c) =>
simp_all [-natCast_add, Int.mul_neg]
| -[c+1] =>
simp_all [-natCast_add, Int.mul_neg]
· intro ⟨c, p⟩
apply Exists.intro (-c)
match c with
| .ofNat 0 =>
simp_all
| .ofNat (.succ c) =>
simp_all [-natCast_add, Int.mul_neg]
| -[c+1] =>
simp_all [-natCast_add, Int.mul_neg]
/-! div -/
theorem div_eq_ediv' (a b : Int) : Int.div a b = a / b + ite (a < 0 ∧ ¬(b ∣ a)) (sign b) 0 :=
match a, b with
| (a : Nat), ofNat b => rfl
| (a : Nat), -[b +1] => by
simp [Int.div, ediv_ofNat_negSucc, ofNat_not_neg]
| -[a +1], 0 => by
simp [Int.div, ediv_negSucc_zero]
| -[a +1], (b+1 : Nat) => by
have q : ¬(Nat.cast ((b + 1) : Nat) = (0 : Int)) := by
norm_cast
simp [-Int.natCast_add] at q
simp [Int.div, ediv_negSucc_succ, Nat.succ_div,
Int.negSucc_lt_zero, q, true_and,
-Int.natCast_add]
split <;> rename_i pg
· simp [Int.neg_add]
· simp [Int.neg_add, Int.neg_add_cancel_right]
| -[m +1], -[n +1] => by
simp [Int.div, ediv_negSucc_negSucc,
Int.negSucc_lt_zero,
-ofNat_ediv, -natCast_add,
Nat.succ_div]
split <;> rename_i h
. simp
· simp [Int.add_neg_cancel_right]
/-! mod -/
theorem mod_eq_emod' (a b : Int) : Int.mod a b = a % b - b * ite (a < 0 ∧ ¬(b ∣ a)) (sign b) 0 := by
simp [emod_def, mod_def, div_eq_ediv',
Int.mul_add, Int.sub_eq_add_neg, Int.neg_add, Int.add_assoc]
@[simp] theorem emod_mod (a b : Int) : (mod a b) % b = a % b := by
simp [Int.mod_eq_emod', Int.sub_eq_add_neg, Int.neg_mul_eq_mul_neg]
@[simp] theorem mod_emod (m n : Int) : Int.mod (m % n) n = m % n := by
simp_all [mod_eq_emod', emod_neg_iff]
@[simp] theorem mod_mod (m n : Int) : Int.mod (Int.mod m n) n = Int.mod m n := by
simp only [mod_eq_emod' m n]
split
· rename_i mnn
rw [mod_eq_emod']
by_cases q : OfNat.ofNat 0 < natAbs n <;>
simp_all [Int.sub_eq_add_neg, Int.mul_sign, add_emod_of_dvd, Int.add_lt_iff,
Int.natAbs_pos, Int.emod_lt, Int.dvd_add_left]
· simp [mod_emod]
/-! fdiv -/
theorem fdiv_eq_ediv' (a b : Int) : Int.fdiv a b = a / b + if b < 0 ∧ ¬(b ∣ a) then (-1) else 0 := by
match a, b with
| 0, b =>
simp [Int.fdiv, Int.dvd_zero]
| ofNat (Nat.succ m), ofNat n =>
simp [Int.fdiv, Int.ofNat_not_neg]
| ofNat (Nat.succ m), -[n+1] =>
simp only [fdiv,Int.negSucc_lt_zero, true_and, Int.ofNat_eq_coe, ediv_ofNat_negSucc,
Int.negSucc_dvd, Int.dvd_natCast_natCast, ite_not,
Nat.succ_div, Nat.succ_eq_add_one]
split <;> rename_i h
· rw [Int.add_zero]; rfl
· rw [← Int.neg_add]; rfl
| -[_+1], 0 =>
simp
| -[m+1], ofNat (Nat.succ n) => rfl
| -[m+1], -[n+1] =>
simp only [Int.fdiv, Int.ediv_negSucc_negSucc, Nat.succ_div, Int.negSucc_lt_zero, true_and,
Int.dvd_negSucc, Int.negSucc_dvd, Int.dvd_natCast_natCast]
split <;> rename_i h
· simp only [Int.add_zero]
rfl
· simp only [Int.natCast_add, Int.Nat.cast_ofNat_Int, Int.add_neg_cancel_right]
rfl
/-! fmod -/
theorem fmod_eq_emod' (a b : Int) : Int.fmod a b = a % b - b * ite (b < 0 ∧ ¬(b ∣ a)) (-1) 0 := by
simp [fmod_def, emod_def, fdiv_eq_ediv', Int.sub_eq_add_neg, Int.mul_add, Int.neg_add,
Int.add_assoc]
@[simp] theorem emod_fmod (a b : Int) : (fmod a b) % b = a % b := by
simp [Int.fmod_eq_emod', Int.sub_eq_add_neg, Int.neg_mul_eq_mul_neg]
@[simp] theorem fmod_emod (m n : Int) : Int.fmod (m % n) n = Int.fmod m n := by
simp_all [fmod_eq_emod', emod_neg_iff]
@[simp]
theorem fmod_fmod (m n : Int) : Int.fmod (Int.fmod m n) n = Int.fmod m n := by
simp [fmod_eq_emod', Int.sub_eq_add_neg, Int.neg_mul_eq_mul_neg,
Int.dvd_add_left, Int.dvd_mul_right]
/-! bdiv -/
@[simp] theorem zero_bdiv (n : Nat) : bdiv 0 n = 0 := by unfold bdiv; simp; omega
@[simp] theorem bdiv_zero (n : Int) : bdiv n 0 = 0 := by rfl
@[simp] theorem bdiv_one (n : Int) : bdiv n 1 = n := by unfold bdiv; simp
/-! bmod -/
@[simp] theorem bmod_zero (n : Int) : bmod n 0 = n := by unfold bmod; simp
end Int