blob: 5b780239fe7b256793a0ec9b810fc84345708130 [file]
/-
Copyright (c) 2016 Jeremy Avigad. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Jeremy Avigad, Mario Carneiro, Kim Morrison, Markus Himmel
-/
prelude
import Init.Data.Int.DivMod.Bootstrap
import Init.Data.Nat.Lemmas
import Init.Data.Nat.Div.Lemmas
import Init.Data.Int.Order
import Init.Data.Int.Lemmas
import Init.Data.Nat.Dvd
import Init.RCases
/-!
# Further lemmas about integer division, now that `omega` is available.
-/
open Nat (succ)
namespace Int
protected theorem exists_add_of_le {a b : Int} (h : a ≤ b) : ∃ (c : Nat), b = a + c :=
⟨(b - a).toNat, by omega⟩
theorem toNat_emod {x y : Int} (hx : 0 ≤ x) (hy : 0 ≤ y) :
(x % y).toNat = x.toNat % y.toNat :=
match x, y, eq_ofNat_of_zero_le hx, eq_ofNat_of_zero_le hy with
| _, _, ⟨_, rfl⟩, ⟨_, rfl⟩ => rfl
/-! ### dvd -/
theorem dvd_antisymm {a b : Int} (H1 : 0 ≤ a) (H2 : 0 ≤ b) : a ∣ b → b ∣ a → a = b := by
rw [← natAbs_of_nonneg H1, ← natAbs_of_nonneg H2]
rw [ofNat_dvd, ofNat_dvd, ofNat_inj]
apply Nat.dvd_antisymm
protected theorem dvd_add : ∀ {a b c : Int}, a ∣ b → a ∣ c → a ∣ b + c
| _, _, _, ⟨d, rfl⟩, ⟨e, rfl⟩ => ⟨d + e, by rw [Int.mul_add]⟩
protected theorem dvd_sub : ∀ {a b c : Int}, a ∣ b → a ∣ c → a ∣ b - c
| _, _, _, ⟨d, rfl⟩, ⟨e, rfl⟩ => ⟨d - e, by rw [Int.mul_sub]⟩
protected theorem dvd_add_left {a b c : Int} (H : a ∣ c) : a ∣ b + c ↔ a ∣ b :=
⟨fun h => by have := Int.dvd_sub h H; rwa [Int.add_sub_cancel] at this, (Int.dvd_add · H)⟩
protected theorem dvd_add_right {a b c : Int} (H : a ∣ b) : a ∣ b + c ↔ a ∣ c := by
rw [Int.add_comm, Int.dvd_add_left H]
@[simp] protected theorem dvd_add_mul_self {a b c : Int} : a ∣ b + c * a ↔ a ∣ b := by
rw [Int.dvd_add_left (Int.dvd_mul_left c a)]
@[simp] protected theorem dvd_add_self_mul {a b c : Int} : a ∣ b + a * c ↔ a ∣ b := by
rw [Int.mul_comm, Int.dvd_add_mul_self]
@[simp] protected theorem dvd_mul_self_add {a b c : Int} : a ∣ b * a + c ↔ a ∣ c := by
rw [Int.add_comm, Int.dvd_add_mul_self]
@[simp] protected theorem dvd_self_mul_add {a b c : Int} : a ∣ a * b + c ↔ a ∣ c := by
rw [Int.mul_comm, Int.dvd_mul_self_add]
protected theorem dvd_iff_dvd_of_dvd_sub {a b c : Int} (H : a ∣ b - c) : a ∣ b ↔ a ∣ c :=
⟨fun h => Int.sub_sub_self b c ▸ Int.dvd_sub h H,
fun h => Int.sub_add_cancel b c ▸ Int.dvd_add H h⟩
protected theorem dvd_iff_dvd_of_dvd_add {a b c : Int} (H : a ∣ b + c) : a ∣ b ↔ a ∣ c := by
rw [← Int.sub_neg] at H; rw [Int.dvd_iff_dvd_of_dvd_sub H, Int.dvd_neg]
theorem le_of_dvd {a b : Int} (bpos : 0 < b) (H : a ∣ b) : a ≤ b :=
match a, b, eq_succ_of_zero_lt bpos, H with
| ofNat _, _, ⟨n, rfl⟩, H => ofNat_le.2 <| Nat.le_of_dvd n.succ_pos <| ofNat_dvd.1 H
| -[_+1], _, ⟨_, rfl⟩, _ => Int.le_trans (Int.le_of_lt <| negSucc_lt_zero _) (ofNat_zero_le _)
theorem natAbs_dvd {a b : Int} : (a.natAbs : Int) ∣ b ↔ a ∣ b :=
match natAbs_eq a with
| .inl e => by rw [← e]
| .inr e => by rw [← Int.neg_dvd, ← e]
theorem dvd_natAbs {a b : Int} : a ∣ b.natAbs ↔ a ∣ b :=
match natAbs_eq b with
| .inl e => by rw [← e]
| .inr e => by rw [← Int.dvd_neg, ← e]
theorem natAbs_dvd_self {a : Int} : (a.natAbs : Int) ∣ a := by
rw [Int.natAbs_dvd]
exact Int.dvd_refl a
theorem dvd_natAbs_self {a : Int} : a ∣ (a.natAbs : Int) := by
rw [Int.dvd_natAbs]
exact Int.dvd_refl a
theorem natAbs_eq_of_dvd_dvd (hmn : m ∣ n) (hnm : n ∣ m) : natAbs m = natAbs n :=
Nat.dvd_antisymm (natAbs_dvd_natAbs.2 hmn) (natAbs_dvd_natAbs.2 hnm)
theorem ofNat_dvd_right {n : Nat} {z : Int} : z ∣ (↑n : Int) ↔ z.natAbs ∣ n := by
rw [← natAbs_dvd_natAbs, natAbs_natCast]
@[simp] theorem negSucc_dvd {a : Nat} {b : Int} : -[a+1] ∣ b ↔ ((a + 1 : Nat) : Int) ∣ b := by
rw [← natAbs_dvd]
norm_cast
@[simp] theorem dvd_negSucc {a : Int} {b : Nat} : a ∣ -[b+1] ↔ a ∣ ((b + 1 : Nat) : Int) := by
rw [← dvd_natAbs]
norm_cast
theorem eq_one_of_dvd_one {a : Int} (H : 0 ≤ a) (H' : a ∣ 1) : a = 1 :=
match a, eq_ofNat_of_zero_le H, H' with
| _, ⟨_, rfl⟩, H' => congrArg ofNat <| Nat.eq_one_of_dvd_one <| ofNat_dvd.1 H'
theorem eq_one_of_mul_eq_one_right {a b : Int} (H : 0 ≤ a) (H' : a * b = 1) : a = 1 :=
eq_one_of_dvd_one H ⟨b, H'.symm⟩
theorem eq_one_of_mul_eq_one_left {a b : Int} (H : 0 ≤ b) (H' : a * b = 1) : b = 1 :=
eq_one_of_mul_eq_one_right (b := a) H <| by rw [Int.mul_comm, H']
instance decidableDvd : DecidableRel (α := Int) (· ∣ ·) := fun _ _ =>
decidable_of_decidable_of_iff (dvd_iff_emod_eq_zero ..).symm
protected theorem mul_dvd_mul_iff_left {a b c : Int} (h : a ≠ 0) : (a * b) ∣ (a * c) ↔ b ∣ c :=
⟨by rintro ⟨d, h'⟩; exact ⟨d, by rw [Int.mul_assoc] at h'; exact (mul_eq_mul_left_iff h).mp h'⟩,
by rintro ⟨d, rfl⟩; exact ⟨d, by simp [Int.mul_assoc]⟩⟩
protected theorem mul_dvd_mul_iff_right {a b c : Int} (h : a ≠ 0) : (b * a) ∣ (c * a) ↔ b ∣ c := by
rw [Int.mul_comm b a, Int.mul_comm c a]
exact Int.mul_dvd_mul_iff_left h
protected theorem mul_dvd_mul {a b c d : Int} : a ∣ b → c ∣ d → a * c ∣ b * d := by
simpa [← Int.natAbs_dvd_natAbs, natAbs_mul] using Nat.mul_dvd_mul
protected theorem mul_dvd_mul_left (a : Int) (h : b ∣ c) : a * b ∣ a * c :=
Int.mul_dvd_mul a.dvd_refl h
protected theorem mul_dvd_mul_right (a : Int) (h : b ∣ c) : b * a ∣ c * a :=
Int.mul_dvd_mul h a.dvd_refl
theorem dvd_of_mul_dvd_mul_left {a m n : Int} (ha : a ≠ 0) (h : a * m ∣ a * n) : m ∣ n := by
obtain ⟨b, hb⟩ := h
rw [Int.mul_assoc, Int.mul_eq_mul_left_iff ha] at hb
exact ⟨_, hb⟩
theorem dvd_of_mul_dvd_mul_right {a m n : Int} (ha : a ≠ 0) (h : m * a ∣ n * a) : m ∣ n :=
dvd_of_mul_dvd_mul_left ha (by simpa [Int.mul_comm] using h)
/-! ### *div zero -/
@[simp] protected theorem zero_tdiv : ∀ b : Int, tdiv 0 b = 0
| ofNat _ => show ofNat _ = _ by simp
| -[_+1] => show -ofNat _ = _ by simp
@[simp] protected theorem tdiv_zero : ∀ a : Int, tdiv a 0 = 0
| ofNat _ => show ofNat _ = _ by simp
| -[_+1] => by simp [tdiv]
@[simp] theorem zero_fdiv (b : Int) : fdiv 0 b = 0 := by cases b <;> rfl
@[simp] protected theorem fdiv_zero : ∀ a : Int, fdiv a 0 = 0
| 0 => rfl
| succ _ => by simp [fdiv]
| -[_+1] => rfl
/-! ### preliminaries for div equivalences -/
theorem negSucc_emod_ofNat_succ_eq_zero_iff {a b : Nat} :
-[a+1] % (b + 1 : Int) = 0 ↔ (a + 1) % (b + 1) = 0 := by
rw [← Int.natCast_one, ← Int.natCast_add]
change Int.emod _ _ = 0 ↔ _
rw [emod, natAbs_natCast]
simp only [Nat.succ_eq_add_one, subNat_eq_zero_iff, Nat.add_right_cancel_iff]
rw [eq_comm]
apply Nat.succ_mod_succ_eq_zero_iff.symm
theorem negSucc_emod_negSucc_eq_zero_iff {a b : Nat} :
-[a+1] % -[b+1] = 0 ↔ (a + 1) % (b + 1) = 0 := by
change Int.emod _ _ = 0 ↔ _
rw [emod, natAbs_negSucc]
simp only [Nat.succ_eq_add_one, subNat_eq_zero_iff, Nat.add_right_cancel_iff]
rw [eq_comm]
apply Nat.succ_mod_succ_eq_zero_iff.symm
/-! ### div equivalences -/
theorem tdiv_eq_ediv_of_nonneg : ∀ {a b : Int}, 0 ≤ a → a.tdiv b = a / b
| 0, _, _
| _, 0, _ => by simp
| succ _, succ _, _ => rfl
| succ _, -[_+1], _ => rfl
theorem tdiv_eq_ediv {a b : Int} :
a.tdiv b = a / b + if 0 ≤ a ∨ b ∣ a then 0 else sign b := by
simp only [dvd_iff_emod_eq_zero]
match a, b with
| ofNat a, ofNat b => simp [tdiv_eq_ediv_of_nonneg]
| ofNat a, -[b+1] => simp [tdiv_eq_ediv_of_nonneg]
| -[a+1], 0 => simp
| -[a+1], ofNat (succ b) =>
simp only [tdiv, Nat.succ_eq_add_one, ofNat_eq_coe, Int.natCast_add, cast_ofNat_Int,
negSucc_not_nonneg, sign_of_add_one]
simp only [negSucc_emod_ofNat_succ_eq_zero_iff]
norm_cast
simp only [subNat_eq_zero_iff, Nat.succ_eq_add_one, sign_negSucc, Int.sub_neg, false_or]
split <;> rename_i h
· rw [Int.add_zero, neg_ofNat_eq_negSucc_iff]
exact Nat.succ_div_of_mod_eq_zero h
· rw [neg_ofNat_eq_negSucc_add_one_iff]
exact Nat.succ_div_of_mod_ne_zero h
| -[a+1], -[b+1] =>
simp only [tdiv, ofNat_eq_coe, negSucc_not_nonneg, false_or, sign_negSucc]
norm_cast
simp only [negSucc_ediv_negSucc]
rw [Int.natCast_add, Int.natCast_one]
simp only [negSucc_emod_negSucc_eq_zero_iff]
split <;> rename_i h
· norm_cast
exact Nat.succ_div_of_mod_eq_zero h
· rw [Int.add_neg_eq_sub, Int.add_sub_cancel]
norm_cast
exact Nat.succ_div_of_mod_ne_zero h
theorem ediv_eq_tdiv {a b : Int} :
a / b = a.tdiv b - if 0 ≤ a ∨ b ∣ a then 0 else sign b := by
simp [tdiv_eq_ediv]
theorem fdiv_eq_ediv_of_nonneg : ∀ (a : Int) {b : Int}, 0 ≤ b → fdiv a b = a / b
| 0, _, _ | -[_+1], 0, _ => by simp
| succ _, ofNat _, _ | -[_+1], succ _, _ => rfl
theorem fdiv_eq_ediv {a b : Int} :
a.fdiv b = a / b - if 0 ≤ b ∨ b ∣ a then 0 else 1 := by
match a, b with
| ofNat a, ofNat b => simp [fdiv_eq_ediv_of_nonneg]
| -[a+1], ofNat b => simp [fdiv_eq_ediv_of_nonneg]
| 0, -[b+1] => simp
| ofNat (a + 1), -[b+1] =>
simp only [fdiv, ofNat_ediv_negSucc, negSucc_not_nonneg, negSucc_dvd, false_or]
simp only [ofNat_eq_coe, ofNat_dvd]
norm_cast
rw [Nat.succ_div, negSucc_eq]
split <;> rename_i h
· simp
· simp [Int.neg_add]
norm_cast
| -[a+1], -[b+1] =>
simp only [fdiv, ofNat_eq_coe, negSucc_ediv_negSucc, negSucc_not_nonneg, dvd_negSucc, negSucc_dvd,
false_or]
norm_cast
rw [Int.natCast_add, Int.natCast_one, Nat.succ_div]
split <;> simp
theorem ediv_eq_fdiv {a b : Int} :
a / b = a.fdiv b + if 0 ≤ b ∨ b ∣ a then 0 else 1 := by
simp [fdiv_eq_ediv]
theorem fdiv_eq_tdiv_of_nonneg {a b : Int} (Ha : 0 ≤ a) (Hb : 0 ≤ b) : fdiv a b = tdiv a b :=
tdiv_eq_ediv_of_nonneg Ha ▸ fdiv_eq_ediv_of_nonneg _ Hb
theorem fdiv_eq_tdiv {a b : Int} :
a.fdiv b = a.tdiv b -
if b ∣ a then 0
else
if 0 ≤ a then
if 0 ≤ b then 0
else 1
else
if 0 ≤ b then b.sign
else 1 + b.sign := by
rw [fdiv_eq_ediv, tdiv_eq_ediv]
by_cases h : b ∣ a <;> simp [h] <;> omega
theorem tdiv_eq_fdiv {a b : Int} :
a.tdiv b = a.fdiv b +
if b ∣ a then 0
else
if 0 ≤ a then
if 0 ≤ b then 0
else 1
else
if 0 ≤ b then b.sign
else 1 + b.sign := by
rw [fdiv_eq_tdiv]
omega
theorem tdiv_eq_ediv_of_dvd {a b : Int} (h : b ∣ a) : a.tdiv b = a / b := by
simp [tdiv_eq_ediv, h]
theorem fdiv_eq_ediv_of_dvd {a b : Int} (h : b ∣ a) : a.fdiv b = a / b := by
simp [fdiv_eq_ediv, h]
/-! ### mod zero -/
@[simp] theorem zero_tmod (b : Int) : tmod 0 b = 0 := by cases b <;> simp [tmod]
@[simp] theorem tmod_zero : ∀ a : Int, tmod a 0 = a
| ofNat _ => congrArg ofNat <| Nat.mod_zero _
| -[_+1] => congrArg (fun n => -ofNat n) <| Nat.mod_zero _
@[simp] theorem zero_fmod (b : Int) : fmod 0 b = 0 := by cases b <;> rfl
@[simp] theorem fmod_zero : ∀ a : Int, fmod a 0 = a
| 0 => rfl
| succ _ => congrArg ofNat <| Nat.mod_zero _
| -[_+1] => congrArg negSucc <| Nat.mod_zero _
/-! ### mod definitions -/
theorem tmod_add_tdiv : ∀ a b : Int, tmod a b + b * (a.tdiv b) = a
| ofNat _, ofNat _ => congrArg ofNat (Nat.mod_add_div ..)
| ofNat m, -[n+1] => by
show (m % succ n + -↑(succ n) * -↑(m / succ n) : Int) = m
rw [Int.neg_mul_neg]; exact congrArg ofNat (Nat.mod_add_div ..)
| -[m+1], 0 => by
show -(↑((succ m) % 0) : Int) + 0 * -↑(succ m / 0) = -↑(succ m)
rw [Nat.mod_zero, Int.zero_mul, Int.add_zero]
| -[m+1], ofNat n => by
show -(↑((succ m) % n) : Int) + ↑n * -↑(succ m / n) = -↑(succ m)
rw [Int.mul_neg, ← Int.neg_add]
exact congrArg (-ofNat ·) (Nat.mod_add_div ..)
| -[m+1], -[n+1] => by
show -(↑(succ m % succ n) : Int) + -↑(succ n) * ↑(succ m / succ n) = -↑(succ m)
rw [Int.neg_mul, ← Int.neg_add]
exact congrArg (-ofNat ·) (Nat.mod_add_div ..)
theorem tdiv_add_tmod (a b : Int) : b * a.tdiv b + tmod a b = a := by
rw [Int.add_comm]; apply tmod_add_tdiv ..
/-- Variant of `tmod_add_tdiv` with the multiplication written the other way around. -/
theorem tmod_add_tdiv' (m k : Int) : tmod m k + m.tdiv k * k = m := by
rw [Int.mul_comm]; apply tmod_add_tdiv
/-- Variant of `tdiv_add_tmod` with the multiplication written the other way around. -/
theorem tdiv_add_tmod' (m k : Int) : m.tdiv k * k + tmod m k = m := by
rw [Int.mul_comm]; apply tdiv_add_tmod
theorem tmod_def (a b : Int) : tmod a b = a - b * a.tdiv b := by
rw [← Int.add_sub_cancel (tmod a b), tmod_add_tdiv]
theorem fmod_add_fdiv : ∀ a b : Int, a.fmod b + b * a.fdiv b = a
| 0, ofNat _ | 0, -[_+1] => congrArg ofNat <| by simp
| succ _, ofNat _ => congrArg ofNat <| Nat.mod_add_div ..
| succ m, -[n+1] => by
show subNatNat (m % succ n) n + (↑(succ n * (m / succ n)) + n + 1) = (m + 1)
rw [Int.add_comm _ n, ← Int.add_assoc, ← Int.add_assoc,
Int.subNatNat_eq_coe, Int.sub_add_cancel]
exact congrArg (ofNat · + 1) <| Nat.mod_add_div ..
| -[_+1], 0 => by rw [fmod_zero]; rfl
| -[m+1], succ n => by
show subNatNat .. - (↑(succ n * (m / succ n)) + ↑(succ n)) = -↑(succ m)
rw [Int.subNatNat_eq_coe, ← Int.sub_sub, ← Int.neg_sub, Int.sub_sub, Int.sub_sub_self]
exact congrArg (-ofNat ·) <| Nat.succ_add .. ▸ Nat.mod_add_div .. ▸ rfl
| -[m+1], -[n+1] => by
show -(↑(succ m % succ n) : Int) + -↑(succ n * (succ m / succ n)) = -↑(succ m)
rw [← Int.neg_add]; exact congrArg (-ofNat ·) <| Nat.mod_add_div ..
/-- Variant of `fmod_add_fdiv` with the multiplication written the other way around. -/
theorem fmod_add_fdiv' (a b : Int) : a.fmod b + (a.fdiv b) * b = a := by
rw [Int.mul_comm]; exact fmod_add_fdiv ..
theorem fdiv_add_fmod (a b : Int) : b * a.fdiv b + a.fmod b = a := by
rw [Int.add_comm]; exact fmod_add_fdiv ..
/-- Variant of `fdiv_add_fmod` with the multiplication written the other way around. -/
theorem fdiv_add_fmod' (a b : Int) : (a.fdiv b) * b + a.fmod b = a := by
rw [Int.mul_comm]; exact fdiv_add_fmod ..
theorem fmod_def (a b : Int) : a.fmod b = a - b * a.fdiv b := by
rw [← Int.add_sub_cancel (a.fmod b), fmod_add_fdiv]
/-! ### mod equivalences -/
theorem fmod_eq_emod_of_nonneg (a : Int) {b : Int} (hb : 0 ≤ b) : fmod a b = a % b := by
simp [fmod_def, emod_def, fdiv_eq_ediv_of_nonneg _ hb]
theorem fmod_eq_emod {a b : Int} :
fmod a b = a % b + if 0 ≤ b ∨ b ∣ a then 0 else b := by
simp [fmod_def, emod_def, fdiv_eq_ediv]
split <;> simp [Int.mul_sub]
omega
theorem emod_eq_fmod {a b : Int} :
a % b = fmod a b - if 0 ≤ b ∨ b ∣ a then 0 else b := by
simp [fmod_eq_emod]
theorem tmod_eq_emod_of_nonneg {a b : Int} (ha : 0 ≤ a) : tmod a b = a % b := by
simp [emod_def, tmod_def, tdiv_eq_ediv_of_nonneg ha]
theorem tmod_eq_emod {a b : Int} :
tmod a b = a % b - if 0 ≤ a ∨ b ∣ a then 0 else b.natAbs := by
rw [tmod_def, tdiv_eq_ediv]
simp only [dvd_iff_emod_eq_zero]
split
· simp [emod_def]
· rw [Int.mul_add, ← Int.sub_sub, emod_def]
simp
theorem emod_eq_tmod {a b : Int} :
a % b = tmod a b + if 0 ≤ a ∨ b ∣ a then 0 else b.natAbs := by
simp [tmod_eq_emod]
theorem fmod_eq_tmod_of_nonneg {a b : Int} (ha : 0 ≤ a) (hb : 0 ≤ b) : fmod a b = tmod a b :=
tmod_eq_emod_of_nonneg ha ▸ fmod_eq_emod_of_nonneg _ hb
theorem fmod_eq_tmod {a b : Int} :
fmod a b = tmod a b +
if b ∣ a then 0
else
if 0 ≤ a then
if 0 ≤ b then 0
else b
else
if 0 ≤ b then b.natAbs
else 2 * b.toNat := by
simp [fmod_eq_emod, tmod_eq_emod]
by_cases h : b ∣ a <;> simp [h]
split <;> split <;> omega
theorem tmod_eq_fmod {a b : Int} :
tmod a b = fmod a b -
if b ∣ a then 0
else
if 0 ≤ a then
if 0 ≤ b then 0
else b
else
if 0 ≤ b then b.natAbs
else 2 * b.toNat := by
simp [fmod_eq_tmod]
/-! ### `/` ediv -/
theorem mul_add_ediv_right (a c : Int) {b : Int} (H : b ≠ 0) : (a * b + c) / b = a + c / b := by
rw [Int.add_comm, add_mul_ediv_right _ _ H, Int.add_comm]
theorem mul_add_ediv_left (b : Int) {a : Int}
(c : Int) (H : a ≠ 0) : (a * b + c) / a = b + c / a := by
rw [Int.add_comm, add_mul_ediv_left _ _ H, Int.add_comm]
theorem sub_mul_ediv_right (a b : Int) {c : Int} (H : c ≠ 0) : (a - b * c) / c = a / c - b := by
rw [Int.sub_eq_add_neg, ← Int.neg_mul, add_mul_ediv_right _ _ H, Int.sub_eq_add_neg]
theorem sub_mul_ediv_left (a : Int) {b : Int}
(c : Int) (H : b ≠ 0) : (a - b * c) / b = a / b - c := by
rw [Int.sub_eq_add_neg, ← Int.mul_neg, add_mul_ediv_left _ _ H, Int.sub_eq_add_neg]
theorem mul_sub_ediv_right (a c : Int) {b : Int} (H : b ≠ 0) : (a * b - c) / b = a + -c / b := by
rw [Int.sub_eq_add_neg, Int.add_comm, add_mul_ediv_right _ _ H, Int.add_comm]
theorem mul_sub_ediv_left (b : Int) {a : Int}
(c : Int) (H : a ≠ 0) : (a * b - c) / a = b + -c / a := by
rw [Int.sub_eq_add_neg, Int.add_comm, add_mul_ediv_left _ _ H, Int.add_comm]
theorem ediv_neg_of_neg_of_pos {a b : Int} (Ha : a < 0) (Hb : 0 < b) : a / b < 0 :=
match a, b, eq_negSucc_of_lt_zero Ha, eq_succ_of_zero_lt Hb with
| _, _, ⟨_, rfl⟩, ⟨_, rfl⟩ => negSucc_lt_zero _
@[deprecated ediv_neg_of_neg_of_pos (since := "2025-03-04")]
abbrev ediv_neg' := @ediv_neg_of_neg_of_pos
theorem negSucc_ediv (m : Nat) {b : Int} (H : 0 < b) : -[m+1] / b = -(ediv m b + 1) :=
match b, eq_succ_of_zero_lt H with
| _, ⟨_, rfl⟩ => rfl
theorem ediv_nonneg {a b : Int} (Ha : 0 ≤ a) (Hb : 0 ≤ b) : 0 ≤ a / b :=
match a, b, eq_ofNat_of_zero_le Ha, eq_ofNat_of_zero_le Hb with
| _, _, ⟨_, rfl⟩, ⟨_, rfl⟩ => ofNat_zero_le _
theorem ediv_nonneg_of_nonpos_of_nonpos {a b : Int} (Ha : a ≤ 0) (Hb : b ≤ 0) : 0 ≤ a / b := by
match a, b with
| ofNat a, b =>
match Int.le_antisymm Ha (ofNat_zero_le a) with
| h1 =>
rw [h1, zero_ediv]
exact Int.le_refl 0
| a, ofNat b =>
match Int.le_antisymm Hb (ofNat_zero_le b) with
| h1 =>
rw [h1, Int.ediv_zero]
exact Int.le_refl 0
| negSucc a, negSucc b =>
rw [Int.div_def, ediv]
exact le_add_one (ediv_nonneg (ofNat_zero_le a) (Int.le_trans (ofNat_zero_le b) (le.intro 1 rfl)))
theorem ediv_pos_of_neg_of_neg {a b : Int} (ha : a < 0) (hb : b < 0) : 0 < a / b := by
rw [Int.div_def]
match a, b, ha, hb with
| .negSucc a, .negSucc b, _, _ => apply ofNat_succ_pos
theorem ediv_nonpos_of_nonneg_of_nonpos {a b : Int} (Ha : 0 ≤ a) (Hb : b ≤ 0) : a / b ≤ 0 :=
Int.nonpos_of_neg_nonneg <| Int.ediv_neg .. ▸ Int.ediv_nonneg Ha (Int.neg_nonneg_of_nonpos Hb)
@[deprecated ediv_nonpos_of_nonneg_of_nonpos (since := "2025-03-04")]
abbrev ediv_nonpos := @ediv_nonpos_of_nonneg_of_nonpos
theorem ediv_eq_zero_of_lt {a b : Int} (H1 : 0 ≤ a) (H2 : a < b) : a / b = 0 :=
match a, b, eq_ofNat_of_zero_le H1, eq_succ_of_zero_lt (Int.lt_of_le_of_lt H1 H2) with
| _, _, ⟨_, rfl⟩, ⟨_, rfl⟩ => congrArg Nat.cast <| Nat.div_eq_of_lt <| ofNat_lt.1 H2
theorem ediv_eq_neg_one_of_neg_of_le {a b : Int} (H1 : a < 0) (H2 : -a ≤ b) : a / b = -1 := by
match a, b, H1, H2 with
| negSucc a', ofNat (b' + 1), H1, H2 =>
rw [Int.div_def, ediv, Int.negSucc_eq, Int.neg_inj]
norm_cast
rw [Nat.add_eq_right, Nat.div_eq_zero_iff_lt (by omega)]
simp [Int.negSucc_eq] at H2
omega
theorem ediv_eq_one_of_neg_of_le {a b : Int} (H1 : a < 0) (H2 : b ≤ a) : a / b = 1 := by
match a, b, H1, H2 with
| negSucc a', ofNat n', H1, H2 => simp [Int.negSucc_eq] at H2; omega
| negSucc a', negSucc b', H1, H2 =>
rw [Int.div_def, ediv, ofNat_eq_coe]
norm_cast
rw [Nat.succ_eq_add_one, Nat.add_eq_right, Nat.div_eq_zero_iff_lt (by omega)]
simp [Int.negSucc_eq] at H2
omega
theorem one_ediv (b : Int) : 1 / b = if b.natAbs = 1 then b else 0 := by
induction b using wlog_sign
case inv => simp; split <;> simp
case w b =>
match b with
| 0 => simp
| 1 => simp
| b + 2 =>
apply ediv_eq_zero_of_lt (by decide) (by omega)
theorem neg_one_ediv (b : Int) : -1 / b = -b.sign :=
match b with
| ofNat 0 => by simp
| ofNat (b + 1) =>
ediv_eq_neg_one_of_neg_of_le (by decide) (by simp [ofNat_eq_coe]; omega)
| negSucc b =>
ediv_eq_one_of_neg_of_le (by decide) (by omega)
@[simp] theorem mul_ediv_mul_of_pos {a : Int}
(b c : Int) (H : 0 < a) : (a * b) / (a * c) = b / c :=
suffices ∀ (m k : Nat) (b : Int), (m.succ * b) / (m.succ * k) = b / k from
match a, eq_succ_of_zero_lt H, c, Int.eq_nat_or_neg c with
| _, ⟨m, rfl⟩, _, ⟨k, .inl rfl⟩ => this _ ..
| _, ⟨m, rfl⟩, _, ⟨k, .inr rfl⟩ => by
rw [Int.mul_neg, Int.ediv_neg, Int.ediv_neg]; apply congrArg Neg.neg; apply this
fun m k b =>
match b, k with
| ofNat _, _ => congrArg ofNat (Nat.mul_div_mul_left _ _ m.succ_pos)
| -[n+1], 0 => by
rw [Int.ofNat_zero, Int.mul_zero, Int.ediv_zero, Int.ediv_zero]
| -[n+1], succ k => congrArg negSucc <|
show (m.succ * n + m) / (m.succ * k.succ) = n / k.succ by
apply Nat.div_eq_of_lt_le
· refine Nat.le_trans ?_ (Nat.le_add_right _ _)
rw [← Nat.mul_div_mul_left _ _ m.succ_pos]
apply Nat.div_mul_le_self
· show m.succ * n.succ ≤ _
rw [Nat.mul_left_comm]
apply Nat.mul_le_mul_left
apply (Nat.div_lt_iff_lt_mul k.succ_pos).1
apply Nat.lt_succ_self
@[simp] theorem mul_ediv_mul_of_pos_left
(a : Int) {b : Int} (c : Int) (H : 0 < b) : (a * b) / (c * b) = a / c := by
rw [Int.mul_comm, Int.mul_comm c, mul_ediv_mul_of_pos _ _ H]
protected theorem ediv_eq_of_eq_mul_right {a b c : Int}
(H1 : b ≠ 0) (H2 : a = b * c) : a / b = c := by rw [H2, Int.mul_ediv_cancel_left _ H1]
protected theorem eq_ediv_of_mul_eq_right {a b c : Int}
(H1 : a ≠ 0) (H2 : a * b = c) : b = c / a :=
(Int.ediv_eq_of_eq_mul_right H1 H2.symm).symm
protected theorem ediv_eq_of_eq_mul_left {a b c : Int}
(H1 : b ≠ 0) (H2 : a = c * b) : a / b = c :=
Int.ediv_eq_of_eq_mul_right H1 (by rw [Int.mul_comm, H2])
protected theorem eq_ediv_of_mul_eq_left {a b c : Int}
(H1 : b ≠ 0) (H2 : a * b = c) : a = c / b :=
(Int.ediv_eq_of_eq_mul_left H1 H2.symm).symm
@[simp] protected theorem ediv_self {a : Int} (H : a ≠ 0) : a / a = 1 := by
have := Int.mul_ediv_cancel 1 H; rwa [Int.one_mul] at this
@[simp] protected theorem neg_ediv_self (a : Int) (h : a ≠ 0) : (-a) / a = -1 := by
rw [neg_ediv_of_dvd (Int.dvd_refl a), Int.ediv_self h]
theorem sign_ediv (a b : Int) : sign (a / b) = if 0 ≤ a ∧ a < b.natAbs then 0 else sign a * sign b := by
induction b using wlog_sign
case inv => simp; split <;> simp [Int.mul_neg]
case w b =>
match b with
| 0 => simp
| b + 1 =>
have : ((b + 1 : Nat) : Int).natAbs = b + 1 := by omega
rw [this]
match a with
| 0 => simp
| (a + 1 : Nat) =>
norm_cast
simp only [Nat.le_add_left, Nat.add_lt_add_iff_right, true_and, Int.natCast_add,
cast_ofNat_Int, sign_of_add_one, Int.mul_one]
split
· rw [Nat.div_eq_of_lt (by omega)]
simp
· have := Nat.div_pos (a := a + 1) (b := b + 1) (by omega) (by omega)
rw [sign_eq_one_of_pos (mod_cast this)]
| negSucc a =>
norm_cast
@[simp, norm_cast] theorem natCast_ediv (m n : Nat) : ((m / n : Nat) : Int) = m / n := rfl
/-! ### emod -/
theorem mod_def' (m n : Int) : m % n = emod m n := rfl
theorem negSucc_emod (m : Nat) {b : Int} (bpos : 0 < b) : -[m+1] % b = b - 1 - m % b := by
rw [Int.sub_sub, Int.add_comm]
match b, eq_succ_of_zero_lt bpos with
| _, ⟨n, rfl⟩ => rfl
theorem emod_negSucc (m : Nat) (n : Int) :
(Int.negSucc m) % n = Int.subNatNat (Int.natAbs n) (Nat.succ (m % Int.natAbs n)) := rfl
theorem ofNat_mod_ofNat (m n : Nat) : (m % n : Int) = ↑(m % n) := rfl
@[simp] theorem add_neg_mul_emod_self_right (a b c : Int) : (a + -(b * c)) % c = a % c := by
rw [Int.neg_mul_eq_neg_mul, add_mul_emod_self_right]
@[deprecated add_neg_mul_emod_self_right (since := "2025-04-11")]
theorem add_neg_mul_emod_self {a b c : Int} : (a + -(b * c)) % c = a % c :=
add_neg_mul_emod_self_right ..
@[simp] theorem add_neg_mul_emod_self_left (a b c : Int) : (a + -(b * c)) % b = a % b := by
rw [Int.neg_mul_eq_mul_neg, add_mul_emod_self_left]
@[simp] theorem add_emod_right (a b : Int) : (a + b) % b = a % b := by
have := add_mul_emod_self_left a b 1; rwa [Int.mul_one] at this
@[deprecated add_emod_right (since := "2025-04-11")]
theorem add_emod_self {a b : Int} : (a + b) % b = a % b := add_emod_right ..
@[simp] theorem add_emod_left (a b : Int) : (a + b) % a = b % a := by
rw [Int.add_comm, add_emod_right]
@[deprecated add_emod_left (since := "2025-04-11")]
theorem add_emod_self_left {a b : Int} : (a + b) % a = b % a := add_emod_left ..
@[simp] theorem sub_mul_emod_self_right (a b c : Int) : (a - b * c) % c = a % c := by
simp [Int.sub_eq_add_neg]
@[simp] theorem sub_mul_emod_self_left (a b c : Int) : (a - b * c) % b = a % b := by
simp [Int.sub_eq_add_neg]
@[simp] theorem mul_sub_emod_self_right (a b c : Int) : (a * b - c) % b = -c % b := by
simp [Int.sub_eq_add_neg]
@[simp] theorem mul_sub_emod_self_left (a b c : Int) : (a * b - c) % a = -c % a := by
simp [Int.sub_eq_add_neg]
@[simp] theorem sub_emod_right (a b : Int) : (a - b) % b = a % b := by
rw (occs := [1]) [← Int.mul_one b, sub_mul_emod_self_left]
@[simp] theorem sub_emod_left (a b : Int) : (a - b) % a = -b % a := by
simp [Int.sub_eq_add_neg]
theorem neg_emod_eq_sub_emod {a b : Int} : -a % b = (b - a) % b := by
rw [← add_emod_left, Int.sub_eq_add_neg]
theorem emod_eq_add_self_emod {a b : Int} : a % b = (a + b) % b :=
(Int.add_emod_right ..).symm
@[simp] theorem emod_neg (a b : Int) : a % -b = a % b := by
rw [emod_def, emod_def, Int.ediv_neg, Int.neg_mul_neg]
@[simp] theorem neg_emod_self (a : Int) : -a % a = 0 := by
rw [neg_emod_eq_sub_emod, Int.sub_self, zero_emod]
@[simp] theorem emod_sub_emod (m n k : Int) : (m % n - k) % n = (m - k) % n :=
Int.emod_add_emod m n (-k)
@[simp] theorem sub_emod_emod (m n k : Int) : (m - n % k) % k = (m - n) % k := by
apply (emod_add_cancel_right (n % k)).mp
rw [Int.sub_add_cancel, Int.add_emod_emod, Int.sub_add_cancel]
theorem emod_eq_of_lt {a b : Int} (H1 : 0 ≤ a) (H2 : a < b) : a % b = a :=
have b0 := Int.le_trans H1 (Int.le_of_lt H2)
match a, b, eq_ofNat_of_zero_le H1, eq_ofNat_of_zero_le b0 with
| _, _, ⟨_, rfl⟩, ⟨_, rfl⟩ => congrArg ofNat <| Nat.mod_eq_of_lt (Int.ofNat_lt.1 H2)
theorem emod_lt_of_neg (a : Int) {b : Int} (h : b < 0) : a % b < -b := by
match b, h with
| .negSucc b', h =>
simp only [negSucc_eq, emod_neg]
apply emod_lt_of_pos
omega
theorem emod_lt (a : Int) {b : Int} (h : b ≠ 0) : a % b < b.natAbs :=
match b, h with
| (b : Nat), h => emod_lt_of_pos a (by omega)
| negSucc b, h => emod_lt_of_neg a (by omega)
@[simp] theorem emod_self_add_one {x : Int} (h : 0 ≤ x) : x % (x + 1) = x :=
emod_eq_of_lt h (Int.lt_succ x)
theorem sign_emod (a : Int) {b} (h : b ≠ 0) : sign (a % b) = if b ∣ a then 0 else 1 := by
split <;> rename_i w
· simp [emod_eq_zero_of_dvd, w]
· obtain rfl | w := emod_pos_of_not_dvd w
· simp at h
· simp [sign_eq_one_of_pos w]
theorem one_emod {b : Int} : 1 % b = if b.natAbs = 1 then 0 else 1 := by
rw [emod_def, one_ediv]
split <;> rename_i h
· obtain rfl | rfl := natAbs_eq_iff.mp h <;> simp
· simp
@[simp] theorem neg_emod_two (i : Int) : -i % 2 = i % 2 := by omega
@[simp, norm_cast] theorem natCast_emod (m n : Nat) : (↑(m % n) : Int) = ↑m % ↑n := rfl
/-! ### properties of `/` and `%` -/
theorem mul_ediv_cancel_of_dvd {a b : Int} (H : b ∣ a) : b * (a / b) = a :=
mul_ediv_cancel_of_emod_eq_zero (emod_eq_zero_of_dvd H)
theorem ediv_mul_cancel_of_dvd {a b : Int} (H : b ∣ a) : a / b * b = a :=
ediv_mul_cancel_of_emod_eq_zero (emod_eq_zero_of_dvd H)
theorem emod_two_eq (x : Int) : x % 2 = 0 ∨ x % 2 = 1 := by omega
theorem add_emod_eq_add_emod_left {m n k : Int} (i : Int)
(H : m % n = k % n) : (i + m) % n = (i + k) % n := by
rw [Int.add_comm, add_emod_eq_add_emod_right _ H, Int.add_comm]
theorem emod_add_cancel_left {m n k i : Int} : (i + m) % n = (i + k) % n ↔ m % n = k % n := by
rw [Int.add_comm, Int.add_comm i, emod_add_cancel_right]
theorem emod_sub_cancel_right {m n k : Int} (i) : (m - i) % n = (k - i) % n ↔ m % n = k % n :=
emod_add_cancel_right _
theorem emod_eq_emod_iff_emod_sub_eq_zero {m n k : Int} : m % n = k % n ↔ (m - k) % n = 0 :=
(emod_sub_cancel_right k).symm.trans <| by simp [Int.sub_self]
theorem emod_sub_cancel_left {m n k : Int} (i) : (i - m) % n = (i - k) % n ↔ m % n = k % n := by
simp only [emod_eq_emod_iff_emod_sub_eq_zero, ← dvd_iff_emod_eq_zero,
(by omega : i - m - (i - k) = -(m - k)), Int.dvd_neg]
protected theorem ediv_emod_unique {a b r q : Int} (h : 0 < b) :
a / b = q ∧ a % b = r ↔ r + b * q = a ∧ 0 ≤ r ∧ r < b := by
constructor
· intro ⟨rfl, rfl⟩
exact ⟨emod_add_ediv a b, emod_nonneg _ (Int.ne_of_gt h), emod_lt_of_pos _ h⟩
· intro ⟨rfl, hz, hb⟩
constructor
· rw [Int.add_mul_ediv_left r q (Int.ne_of_gt h), ediv_eq_zero_of_lt hz hb]
simp [Int.zero_add]
· rw [add_mul_emod_self_left, emod_eq_of_lt hz hb]
protected theorem ediv_emod_unique' {a b r q : Int} (h : b < 0) :
a / b = q ∧ a % b = r ↔ r + b * q = a ∧ 0 ≤ r ∧ r < -b := by
have := Int.ediv_emod_unique (a := a) (b := -b) (r := r) (q := -q) (by omega)
simpa [Int.neg_inj, Int.neg_mul, Int.mul_neg]
@[simp] theorem mul_emod_mul_of_pos
{a : Int} (b c : Int) (H : 0 < a) : (a * b) % (a * c) = a * (b % c) := by
rw [emod_def, emod_def, mul_ediv_mul_of_pos _ _ H, Int.mul_sub, Int.mul_assoc]
theorem lt_ediv_add_one_mul_self (a : Int) {b : Int} (H : 0 < b) : a < (a / b + 1) * b := by
rw [Int.add_mul, Int.one_mul, Int.mul_comm]
exact Int.lt_add_of_sub_left_lt <| Int.emod_def .. ▸ emod_lt_of_pos _ H
theorem neg_ediv {a b : Int} : (-a) / b = -(a / b) - if b ∣ a then 0 else b.sign := by
if hb : b = 0 then
simp [hb]
else
conv => lhs; rw [← ediv_add_emod a b]
rw [Int.neg_add, ← Int.mul_neg, mul_add_ediv_left _ _ hb, Int.add_comm]
split <;> rename_i h
· rw [emod_eq_zero_of_dvd h]
simp
· if hb : 0 < b then
rw [Int.sign_eq_one_of_pos hb, ediv_eq_neg_one_of_neg_of_le]
· omega
· have : 0 < a % b := (emod_pos_of_not_dvd h).resolve_left (by omega)
omega
· have := emod_lt_of_pos a hb
omega
else
replace hb : b < 0 := by omega
rw [Int.sign_eq_neg_one_of_neg hb, Int.ediv_eq_one_of_neg_of_le]
· omega
· have : 0 < a % b := (emod_pos_of_not_dvd h).resolve_left (by omega)
omega
· have := emod_lt_of_neg a hb
omega
theorem tdiv_cases (n m : Int) : n.tdiv m =
if 0 ≤ n then
if 0 ≤ m then n / m else -(n / (-m))
else
if 0 ≤ m then -((-n) / m) else (-n) / (-m) := by
split <;> rename_i hn
· split <;> rename_i hm
· rw [Int.tdiv_eq_ediv_of_nonneg hn]
· rw [Int.tdiv_eq_ediv_of_nonneg hn]
simp
· split <;> rename_i hm
· rw [Int.tdiv_eq_ediv, Int.neg_ediv]
simp [hn, Int.neg_sub, Int.add_comm]
· rw [Int.tdiv_eq_ediv, Int.neg_ediv, Int.ediv_neg]
simp [hn, Int.sub_eq_add_neg, apply_ite Neg.neg]
theorem neg_emod {a b : Int} : (-a) % b = if b ∣ a then 0 else b.natAbs - (a % b) := by
rw [emod_def, emod_def, neg_ediv, Int.mul_sub, Int.mul_neg]
split <;> rename_i h
· simp [mul_ediv_cancel_of_dvd h]
· simp
omega
theorem natAbs_ediv (a : Int) (b : Int) : natAbs (a / b) = natAbs a / natAbs b + if 0 ≤ a ∨ b = 0 ∨ b ∣ a then 0 else 1 := by
by_cases hb : b = 0 <;> try (simp_all; done)
simp only [hb, false_or]
induction b using wlog_sign
case neg.inv => simp
case neg.w b =>
match a with
| 0 => simp
| (a + 1 : Nat) => norm_cast
| negSucc a =>
simp only [negSucc_eq]
norm_cast
rw [neg_ediv]
norm_cast
rw [natAbs_neg, natAbs_natCast]
have : ¬ 0 ≤ -((a + 1 : Nat) : Int) := by omega
simp only [this]
have : ↑b ∣ -((a + 1 : Nat) : Int) ↔ b ∣ a + 1 := by simp; norm_cast
simp only [this, false_or]
split <;> rename_i h
· simp [-natCast_ediv]
· rw [Nat.succ_div, if_neg h, sign_eq_one_of_pos (by omega), Int.sub_eq_add_neg, ← Int.neg_add, natAbs_neg]
norm_cast
theorem natAbs_ediv_of_nonneg {a b : Int} (ha : 0 ≤ a) : (a / b).natAbs = a.natAbs / b.natAbs := by
rw [natAbs_ediv, if_pos (Or.inl ha), Nat.add_zero]
theorem natAbs_ediv_of_dvd {a b : Int} (hab : b ∣ a) : (a / b).natAbs = a.natAbs / b.natAbs := by
rw [natAbs_ediv, if_pos (Or.inr (Or.inr hab)), Nat.add_zero]
theorem natAbs_emod_of_nonneg {a : Int} (h : 0 ≤ a) (b : Int) :
natAbs (a % b) = natAbs a % natAbs b := by
match a, b, h with
| (a : Nat), (b : Nat), _ => norm_cast
| (a : Nat), negSucc b, _ => simp [negSucc_eq]; norm_cast
theorem natAbs_emod (a : Int) {b : Int} (hb : b ≠ 0):
natAbs (a % b) = if 0 ≤ a ∨ b ∣ a then natAbs a % natAbs b else natAbs b - natAbs a % natAbs b := by
match a with
| (a : Nat) => simp [natAbs_emod_of_nonneg]
| negSucc a =>
simp
split <;> rename_i h
· simp [negSucc_eq]
rw [emod_eq_zero_of_dvd, Nat.mod_eq_zero_of_dvd, natAbs_zero]
· exact ofNat_dvd_right.mp h
· exact dvd_natAbs.mp h
simp [negSucc_eq]
simp [neg_emod]
rw [if_neg h]
norm_cast
have := natAbs_emod_of_nonneg (a := a + 1) (by omega) b
norm_cast at this
rw [natAbs_sub_of_nonneg_of_le, this]
omega
· exact emod_nonneg _ hb
· have := emod_lt (a + 1 : Nat) hb
omega
theorem natAbs_ediv_le_natAbs (a b : Int) : natAbs (a / b) ≤ natAbs a :=
match b, Int.eq_nat_or_neg b with
| _, ⟨n, .inl rfl⟩ => aux _ _
| _, ⟨n, .inr rfl⟩ => by rw [Int.ediv_neg, natAbs_neg]; apply aux
where
aux : ∀ (a : Int) (n : Nat), natAbs (a / n) ≤ natAbs a
| ofNat _, _ => Nat.div_le_self ..
| -[_+1], 0 => Nat.zero_le _
| -[_+1], succ _ => Nat.succ_le_succ (Nat.div_le_self _ _)
@[deprecated natAbs_ediv_le_natAbs (since := "2025-03-05")]
abbrev natAbs_div_le_natAbs := natAbs_ediv_le_natAbs
theorem ediv_le_self {a : Int} (b : Int) (Ha : 0 ≤ a) : a / b ≤ a := by
have := Int.le_trans le_natAbs (ofNat_le.2 <| natAbs_ediv_le_natAbs a b)
rwa [natAbs_of_nonneg Ha] at this
theorem dvd_emod_sub_self {x m : Int} : m ∣ x % m - x :=
dvd_of_emod_eq_zero (by simp)
theorem dvd_self_sub_emod {x m : Int} : m ∣ x - x % m :=
dvd_of_emod_eq_zero (by simp)
theorem emod_eq_iff {a b c : Int} (hb : b ≠ 0) : a % b = c ↔ 0 ≤ c ∧ c < b.natAbs ∧ b ∣ c - a := by
refine ⟨?_, ?_⟩
· rintro rfl
exact ⟨emod_nonneg a hb, emod_lt a hb, dvd_emod_sub_self⟩
· rintro ⟨h₁, h₂, h₃⟩
rw [← Int.sub_eq_zero]
have := dvd_emod_sub_self (x := a) (m := b)
have hdvd := Int.dvd_sub this h₃
rw [(by omega : a % b - a - (c - a) = a % b - c)] at hdvd
apply eq_zero_of_dvd_of_natAbs_lt_natAbs hdvd
have := emod_nonneg a hb
have := emod_lt a hb
omega
@[simp] theorem neg_mul_emod_left (a b : Int) : -(a * b) % b = 0 := by
rw [← dvd_iff_emod_eq_zero, Int.dvd_neg]
exact Int.dvd_mul_left a b
@[simp] theorem neg_mul_emod_right (a b : Int) : -(a * b) % a = 0 := by
rw [← dvd_iff_emod_eq_zero, Int.dvd_neg]
exact Int.dvd_mul_right a b
@[deprecated mul_ediv_cancel (since := "2025-03-05")]
theorem neg_mul_ediv_cancel (a b : Int) (h : b ≠ 0) : -(a * b) / b = -a := by
rw [neg_ediv_of_dvd (Int.dvd_mul_left a b), mul_ediv_cancel _ h]
@[deprecated mul_ediv_cancel (since := "2025-03-05")]
theorem neg_mul_ediv_cancel_left (a b : Int) (h : a ≠ 0) : -(a * b) / a = -b := by
rw [neg_ediv_of_dvd (Int.dvd_mul_right a b), mul_ediv_cancel_left _ h]
@[simp] theorem ediv_one : ∀ a : Int, a / 1 = a
| (_:Nat) => congrArg Nat.cast (Nat.div_one _)
| -[_+1] => congrArg negSucc (Nat.div_one _)
@[simp] theorem emod_one (a : Int) : a % 1 = 0 := by
simp [emod_def, Int.one_mul, Int.sub_self]
@[deprecated sub_emod_right (since := "2025-04-11")]
theorem emod_sub_cancel (x y : Int) : (x - y) % y = x % y :=
sub_emod_right ..
@[simp] theorem add_neg_emod_self (a b : Int) : (a + -b) % b = a % b := by
rw [Int.add_neg_eq_sub, sub_emod_right]
@[simp] theorem neg_add_emod_self (a b : Int) : (-a + b) % a = b % a := by
rw [Int.add_comm, add_neg_emod_self]
/-- If `a % b = c` then `b` divides `a - c`. -/
theorem dvd_self_sub_of_emod_eq {a b : Int} : {c : Int} → a % b = c → b ∣ a - c
| _, rfl => dvd_self_sub_emod
@[deprecated dvd_self_sub_of_emod_eq (since := "2025-04-12")]
theorem dvd_sub_of_emod_eq {a b : Int} : {c : Int} → a % b = c → b ∣ a - c :=
dvd_self_sub_of_emod_eq
theorem dvd_sub_self_of_emod_eq {a b : Int} : {c : Int} → a % b = c → b ∣ c - a
| _, rfl => dvd_emod_sub_self
protected theorem eq_mul_of_ediv_eq_right {a b c : Int}
(H1 : b ∣ a) (H2 : a / b = c) : a = b * c := by rw [← H2, Int.mul_ediv_cancel' H1]
protected theorem ediv_eq_iff_eq_mul_right {a b c : Int}
(H : b ≠ 0) (H' : b ∣ a) : a / b = c ↔ a = b * c :=
⟨Int.eq_mul_of_ediv_eq_right H', Int.ediv_eq_of_eq_mul_right H⟩
protected theorem ediv_eq_iff_eq_mul_left {a b c : Int}
(H : b ≠ 0) (H' : b ∣ a) : a / b = c ↔ a = c * b := by
rw [Int.mul_comm]; exact Int.ediv_eq_iff_eq_mul_right H H'
protected theorem eq_mul_of_ediv_eq_left {a b c : Int}
(H1 : b ∣ a) (H2 : a / b = c) : a = c * b := by
rw [Int.mul_comm, Int.eq_mul_of_ediv_eq_right H1 H2]
protected theorem eq_zero_of_ediv_eq_zero {d n : Int} (h : d ∣ n) (H : n / d = 0) : n = 0 := by
rw [← Int.mul_ediv_cancel' h, H, Int.mul_zero]
theorem sub_ediv_of_dvd_sub {a b c : Int}
(hcab : c ∣ a - b) : (a - b) / c = a / c - b / c := by
rw [← Int.add_sub_cancel ((a - b) / c), ← Int.add_ediv_of_dvd_left hcab, Int.sub_add_cancel]
@[simp] protected theorem ediv_left_inj {a b d : Int}
(hda : d ∣ a) (hdb : d ∣ b) : a / d = b / d ↔ a = b := by
refine ⟨fun h => ?_, congrArg (ediv · d)⟩
rw [← Int.mul_ediv_cancel' hda, ← Int.mul_ediv_cancel' hdb, h]
theorem ediv_sign : ∀ a b, a / sign b = a * sign b
| _, succ _ => by simp [sign, Int.mul_one]
| _, 0 => by simp [sign, Int.mul_zero]
| _, -[_+1] => by simp [sign, Int.mul_neg, Int.mul_one]
protected theorem sign_eq_ediv_natAbs (a : Int) : sign a = a / (natAbs a) :=
if az : a = 0 then by simp [az] else
(Int.ediv_eq_of_eq_mul_left (ofNat_ne_zero.2 <| natAbs_ne_zero.2 az)
(sign_mul_natAbs _).symm).symm
theorem dvd_mul_of_ediv_dvd {a b c : Int} (h : b ∣ a) (hdiv : a / b ∣ c) : a ∣ b * c := by
obtain ⟨e, rfl⟩ := hdiv
rw [← Int.mul_assoc, Int.mul_comm _ (a / b), Int.ediv_mul_cancel h]
exact Int.dvd_mul_right a e
@[simp] theorem ediv_dvd_iff_dvd_mul {a b c : Int} (h : b ∣ a) (hb : b ≠ 0) : a / b ∣ c ↔ a ∣ b * c :=
exists_congr <| fun d ↦ by
have := Int.dvd_trans (Int.dvd_mul_left _ _) (Int.mul_dvd_mul_left d h)
rw [eq_comm, Int.mul_comm, ← Int.mul_ediv_assoc d h, Int.ediv_eq_iff_eq_mul_right hb this,
Int.mul_comm, eq_comm]
theorem mul_dvd_of_dvd_ediv {a b c : Int} (hcb : c ∣ b) (h : a ∣ b / c) : c * a ∣ b :=
have ⟨d, hd⟩ := h
⟨d, by simpa [Int.mul_comm, Int.mul_left_comm] using Int.eq_mul_of_ediv_eq_left hcb hd⟩
theorem dvd_ediv_of_mul_dvd {a b c : Int} (h : a * b ∣ c) : b ∣ c / a := by
obtain rfl | ha := Decidable.em (a = 0)
· simp
· obtain ⟨d, rfl⟩ := h
simp [Int.mul_assoc, ha]
@[simp] theorem dvd_ediv_iff_mul_dvd {a b c : Int} (hbc : c ∣ b) : a ∣ b / c ↔ c * a ∣ b :=
⟨mul_dvd_of_dvd_ediv hbc, dvd_ediv_of_mul_dvd⟩
theorem ediv_dvd_ediv : ∀ {a b c : Int}, a ∣ b → b ∣ c → b / a ∣ c / a
| a, _, _, ⟨b, rfl⟩, ⟨c, rfl⟩ =>
if az : a = 0 then by simp [az]
else by
rw [Int.mul_ediv_cancel_left _ az, Int.mul_assoc, Int.mul_ediv_cancel_left _ az]
apply Int.dvd_mul_right
theorem ediv_dvd_of_dvd {m n : Int} (hmn : m ∣ n) : n / m ∣ n := by
obtain rfl | hm := Decidable.em (m = 0)
· simpa using hmn
· obtain ⟨a, ha⟩ := hmn
simp [ha, Int.mul_ediv_cancel_left _ hm, Int.dvd_mul_left]
/-! ### `/` and ordering -/
protected theorem ediv_mul_le (a : Int) {b : Int} (H : b ≠ 0) : a / b * b ≤ a :=
Int.le_of_sub_nonneg <| by rw [Int.mul_comm, ← emod_def]; apply emod_nonneg _ H
theorem le_of_mul_le_mul_left {a b c : Int} (w : a * b ≤ a * c) (h : 0 < a) : b ≤ c := by
have w := Int.sub_nonneg_of_le w
rw [← Int.mul_sub] at w
have w := Int.ediv_nonneg w (Int.le_of_lt h)
rw [Int.mul_ediv_cancel_left _ (Int.ne_of_gt h)] at w
exact Int.le_of_sub_nonneg w
theorem le_of_mul_le_mul_right {a b c : Int} (w : b * a ≤ c * a) (h : 0 < a) : b ≤ c := by
rw [Int.mul_comm b, Int.mul_comm c] at w
exact le_of_mul_le_mul_left w h
protected theorem mul_le_mul_iff_of_pos_right {a b c : Int} (ha : 0 < a) : b * a ≤ c * a ↔ b ≤ c :=
⟨(le_of_mul_le_mul_right · ha), (Int.mul_le_mul_of_nonneg_right · (Int.le_of_lt ha))⟩
protected theorem mul_nonneg_iff_of_pos_right {a b : Int} (hb : 0 < b) : 0 ≤ a * b ↔ 0 ≤ a := by
simpa using (Int.mul_le_mul_iff_of_pos_right hb : 0 * b ≤ a * b ↔ 0 ≤ a)
protected theorem ediv_le_of_le_mul {a b c : Int} (H : 0 < c) (H' : a ≤ b * c) : a / c ≤ b :=
le_of_mul_le_mul_right (Int.le_trans (Int.ediv_mul_le _ (Int.ne_of_gt H)) H') H
protected theorem ediv_nonpos_of_nonpos_of_neg {n s : Int} (h : n ≤ 0) (h2 : 0 < s) : n / s ≤ 0 :=
Int.ediv_le_of_le_mul h2 (by simp [h])
protected theorem mul_lt_of_lt_ediv {a b c : Int} (H : 0 < c) (H3 : a < b / c) : a * c < b :=
Int.lt_of_not_ge <| mt (Int.ediv_le_of_le_mul H) (Int.not_le_of_gt H3)
protected theorem mul_le_of_le_ediv {a b c : Int} (H1 : 0 < c) (H2 : a ≤ b / c) : a * c ≤ b :=
Int.le_trans (Int.mul_le_mul_of_nonneg_right H2 (Int.le_of_lt H1))
(Int.ediv_mul_le _ (Int.ne_of_gt H1))
protected theorem ediv_lt_of_lt_mul {a b c : Int} (H : 0 < c) (H' : a < b * c) : a / c < b :=
Int.lt_of_not_ge <| mt (Int.mul_le_of_le_ediv H) (Int.not_le_of_gt H')
theorem lt_of_mul_lt_mul_left {a b c : Int} (w : a * b < a * c) (h : 0 ≤ a) : b < c := by
rcases Int.lt_trichotomy b c with lt | rfl | gt
· exact lt
· exact False.elim (Int.lt_irrefl _ w)
· rcases Int.lt_trichotomy a 0 with a_lt | rfl | a_gt
· exact False.elim (Int.lt_irrefl _ (Int.lt_of_lt_of_le a_lt h))
· exact False.elim (Int.lt_irrefl b (by simp at w))
· have := le_of_mul_le_mul_left (Int.le_of_lt w) a_gt
exact False.elim (Int.lt_irrefl _ (Int.lt_of_lt_of_le gt this))
theorem lt_of_mul_lt_mul_right {a b c : Int} (w : b * a < c * a) (h : 0 ≤ a) : b < c := by
rw [Int.mul_comm b, Int.mul_comm c] at w
exact lt_of_mul_lt_mul_left w h
protected theorem le_ediv_of_mul_le {a b c : Int} (H1 : 0 < c) (H2 : a * c ≤ b) : a ≤ b / c :=
le_of_lt_add_one <|
lt_of_mul_lt_mul_right (Int.lt_of_le_of_lt H2 (lt_ediv_add_one_mul_self _ H1)) (Int.le_of_lt H1)
protected theorem le_ediv_iff_mul_le {a b c : Int} (H : 0 < c) : a ≤ b / c ↔ a * c ≤ b :=
⟨Int.mul_le_of_le_ediv H, Int.le_ediv_of_mul_le H⟩
protected theorem lt_mul_of_ediv_lt {a b c : Int} (H1 : 0 < c) (H2 : a / c < b) : a < b * c :=
Int.lt_of_not_ge <| mt (Int.le_ediv_of_mul_le H1) (Int.not_le_of_gt H2)
protected theorem ediv_lt_iff_lt_mul {a b c : Int} (H : 0 < c) : a / c < b ↔ a < b * c :=
⟨Int.lt_mul_of_ediv_lt H, Int.ediv_lt_of_lt_mul H⟩
theorem ediv_le_iff_le_mul {k x y : Int} (h : 0 < k) : x / k ≤ y ↔ x < y * k + k := by
rw [Int.le_iff_lt_add_one, Int.ediv_lt_iff_lt_mul h, Int.add_mul]
omega
protected theorem le_mul_of_ediv_le {a b c : Int} (H1 : 0 ≤ b) (H2 : b ∣ a) (H3 : a / b ≤ c) :
a ≤ c * b := by
rw [← Int.ediv_mul_cancel H2]; exact Int.mul_le_mul_of_nonneg_right H3 H1
protected theorem lt_ediv_of_mul_lt {a b c : Int} (H1 : 0 ≤ b) (H2 : b ∣ c) (H3 : a * b < c) :
a < c / b :=
Int.lt_of_not_ge <| mt (Int.le_mul_of_ediv_le H1 H2) (Int.not_le_of_gt H3)
protected theorem lt_ediv_iff_mul_lt {a b : Int} {c : Int} (H : 0 < c) (H' : c ∣ b) :
a < b / c ↔ a * c < b :=
⟨Int.mul_lt_of_lt_ediv H, Int.lt_ediv_of_mul_lt (Int.le_of_lt H) H'⟩
theorem ediv_pos_of_pos_of_dvd {a b : Int} (H1 : 0 < a) (H2 : 0 ≤ b) (H3 : b ∣ a) : 0 < a / b :=
Int.lt_ediv_of_mul_lt H2 H3 (by rwa [Int.zero_mul])
theorem ediv_eq_ediv_of_mul_eq_mul {a b c d : Int}
(H2 : d ∣ c) (H3 : b ≠ 0) (H4 : d ≠ 0) (H5 : a * d = b * c) : a / b = c / d :=
Int.ediv_eq_of_eq_mul_right H3 <| by
rw [← Int.mul_ediv_assoc _ H2]; exact (Int.ediv_eq_of_eq_mul_left H4 H5.symm).symm
theorem ediv_eq_iff_of_pos {k x y : Int} (h : 0 < k) : x / k = y ↔ y * k ≤ x ∧ x < y * k + k := by
rw [Int.eq_iff_le_and_ge, and_comm, Int.le_ediv_iff_mul_le h, Int.ediv_le_iff_le_mul h]
theorem add_ediv_of_pos {a b c : Int} (h : 0 < c) :
(a + b) / c = a / c + b / c + if c ≤ a % c + b % c then 1 else 0 := by
have h' : c ≠ 0 := by omega
conv => lhs; rw [← Int.ediv_add_emod a c]
rw [Int.add_assoc, Int.mul_add_ediv_left _ _ h']
conv => lhs; rw [← Int.ediv_add_emod b c]
rw [Int.add_comm (a % c), Int.add_assoc, Int.mul_add_ediv_left _ _ h',
← Int.add_assoc, Int.add_comm (b % c)]
congr
rw [Int.ediv_eq_iff_of_pos h]
have := emod_lt_of_pos a h
have := emod_lt_of_pos b h
constructor
· have := emod_nonneg a h'
have := emod_nonneg b h'
split <;> · simp; omega
· split <;> · simp; omega
theorem add_ediv {a b c : Int} (h : c ≠ 0) :
(a + b) / c = a / c + b / c + if c.natAbs ≤ a % c + b % c then c.sign else 0 := by
induction c using wlog_sign
case inv => simp; omega
rename_i c
norm_cast at h
have : 0 < (c : Int) := by omega
simp [sign_natCast_of_ne_zero h, add_ediv_of_pos this]
protected theorem ediv_le_ediv {a b c : Int} (H : 0 < c) (H' : a ≤ b) : a / c ≤ b / c :=
Int.le_ediv_of_mul_le H (Int.le_trans (Int.ediv_mul_le _ (Int.ne_of_gt H)) H')
/-- If `n > 0` then `m` is not divisible by `n` iff it is between `n * k` and `n * (k + 1)`
for some `k`. -/
theorem not_dvd_iff_lt_mul_succ (m : Int) (hn : 0 < n) :
¬n ∣ m ↔ (∃ k, n * k < m ∧ m < n * (k + 1)) := by
refine ⟨fun h ↦ ?_, ?_⟩
· rw [dvd_iff_emod_eq_zero, ← Ne] at h
rw [← emod_add_ediv m n]
refine ⟨m / n, Int.lt_add_of_pos_left _ ?_, ?_⟩
· have := emod_nonneg m (Int.ne_of_gt hn)
omega
· rw [Int.add_comm _ (1 : Int), Int.mul_add, Int.mul_one]
exact Int.add_lt_add_right (emod_lt_of_pos _ hn) _
· rintro ⟨k, h1k, h2k⟩ ⟨l, rfl⟩
replace h1k := lt_of_mul_lt_mul_left h1k (by omega)
replace h2k := lt_of_mul_lt_mul_left h2k (by omega)
rw [Int.lt_add_one_iff, ← Int.not_lt] at h2k
exact h2k h1k
/-! ### tdiv -/
-- `tdiv` analogues of `ediv` lemmas from `Bootstrap.lean`
@[simp] protected theorem tdiv_neg : ∀ a b : Int, a.tdiv (-b) = -(a.tdiv b)
| ofNat m, 0 => show ofNat (m / 0) = -↑(m / 0) by rw [Nat.div_zero]; rfl
| ofNat _, -[_+1] | -[_+1], succ _ => (Int.neg_neg _).symm
| ofNat _, succ _ | -[_+1], 0 => by simp [Int.tdiv, Int.neg_zero, ← Int.negSucc_eq]
| -[_+1], -[_+1] => by simp only [tdiv, neg_negSucc]
/-!
There are no lemmas
* `add_mul_tdiv_right : c ≠ 0 → (a + b * c).tdiv c = a.tdiv c + b`
* `add_mul_tdiv_left : b ≠ 0 → (a + b * c).tdiv b = a.tdiv b + c`
* (similarly `mul_add_tdiv_right`, `mul_add_tdiv_left`)
* `add_tdiv_of_dvd_right : c ∣ b → (a + b).tdiv c = a.tdiv c + b.tdiv c`
* `add_tdiv_of_dvd_left : c ∣ a → (a + b).tdiv c = a.tdiv c + b.tdiv c`
because these statements are all incorrect, and require awkward conditional off-by-one corrections.
-/
@[simp] theorem mul_tdiv_cancel (a : Int) {b : Int} (H : b ≠ 0) : (a * b).tdiv b = a := by
rw [tdiv_eq_ediv_of_dvd (Int.dvd_mul_left a b), mul_ediv_cancel _ H]
@[simp] theorem mul_tdiv_cancel_left (b : Int) (H : a ≠ 0) : (a * b).tdiv a = b :=
Int.mul_comm .. ▸ Int.mul_tdiv_cancel _ H
-- `tdiv` analogues of `ediv` lemmas given above
-- There are no lemmas `tdiv_nonneg_iff_of_pos`, `tdiv_neg_of_neg_of_pos`, or `negSucc_tdiv`
-- corresponding to `ediv_nonneg_iff_of_pos`, `ediv_neg_of_neg_of_pos`, or `negSucc_ediv` as they require awkward corrections.
protected theorem tdiv_nonneg {a b : Int} (Ha : 0 ≤ a) (Hb : 0 ≤ b) : 0 ≤ a.tdiv b :=
match a, b, eq_ofNat_of_zero_le Ha, eq_ofNat_of_zero_le Hb with
| _, _, ⟨_, rfl⟩, ⟨_, rfl⟩ => ofNat_zero_le _
theorem tdiv_nonneg_of_nonpos_of_nonpos {a b : Int} (Ha : a ≤ 0) (Hb : b ≤ 0) : 0 ≤ a.tdiv b := by
rw [tdiv_eq_ediv]
split <;> rename_i h
· simpa using ediv_nonneg_of_nonpos_of_nonpos Ha Hb
· simp at h
by_cases h' : b = 0
· subst h'
simp
· replace h' : b < 0 := by omega
rw [sign_eq_neg_one_of_neg h']
have : 0 < a / b := by
by_cases h'' : a = 0
· subst h''
simp at h
· replace h'' : a < 0 := by omega
exact ediv_pos_of_neg_of_neg h'' h'
omega
protected theorem tdiv_nonpos_of_nonneg_of_nonpos {a b : Int} (Ha : 0 ≤ a) (Hb : b ≤ 0) : a.tdiv b ≤ 0 :=
Int.nonpos_of_neg_nonneg <| Int.tdiv_neg .. ▸ Int.tdiv_nonneg Ha (Int.neg_nonneg_of_nonpos Hb)
@[deprecated Int.tdiv_nonpos_of_nonneg_of_nonpos (since := "2025-03-04")]
abbrev tdiv_nonpos := @Int.tdiv_nonpos_of_nonneg_of_nonpos
theorem tdiv_eq_zero_of_lt {a b : Int} (H1 : 0 ≤ a) (H2 : a < b) : a.tdiv b = 0 :=
match a, b, eq_ofNat_of_zero_le H1, eq_succ_of_zero_lt (Int.lt_of_le_of_lt H1 H2) with
| _, _, ⟨_, rfl⟩, ⟨_, rfl⟩ => congrArg Nat.cast <| Nat.div_eq_of_lt <| ofNat_lt.1 H2
@[simp] theorem mul_tdiv_mul_of_pos {a : Int}
(b c : Int) (H : 0 < a) : (a * b).tdiv (a * c) = b.tdiv c := by
rw [tdiv_eq_ediv, mul_ediv_mul_of_pos _ _ H, tdiv_eq_ediv]
simp only [sign_mul]
by_cases h : 0 ≤ b
· rw [if_pos, if_pos (.inl h)]
left
exact Int.mul_nonneg (Int.le_of_lt H) h
· have H' : a ≠ 0 := by omega
simp only [Int.mul_dvd_mul_iff_left H']
by_cases h' : c ∣ b
· simp [h']
· rw [if_neg, if_neg]
· simp [sign_eq_one_of_pos H]
· simp [h']; omega
· simp_all only [Int.not_le, ne_eq, or_false]
exact Int.mul_neg_of_pos_of_neg H h
@[simp] theorem mul_tdiv_mul_of_pos_left
(a : Int) {b : Int} (c : Int) (H : 0 < b) : (a * b).tdiv (c * b) = a.tdiv c := by
rw [Int.mul_comm, Int.mul_comm c, mul_tdiv_mul_of_pos _ _ H]
protected theorem tdiv_eq_of_eq_mul_right {a b c : Int}
(H1 : b ≠ 0) (H2 : a = b * c) : a.tdiv b = c := by rw [H2, Int.mul_tdiv_cancel_left _ H1]
protected theorem eq_tdiv_of_mul_eq_right {a b c : Int}
(H1 : a ≠ 0) (H2 : a * b = c) : b = c.tdiv a :=
(Int.tdiv_eq_of_eq_mul_right H1 H2.symm).symm
protected theorem tdiv_eq_of_eq_mul_left {a b c : Int}
(H1 : b ≠ 0) (H2 : a = c * b) : a.tdiv b = c :=
Int.tdiv_eq_of_eq_mul_right H1 (by rw [Int.mul_comm, H2])
protected theorem eq_tdiv_of_mul_eq_left {a b c : Int}
(H1 : b ≠ 0) (H2 : a * b = c) : a = c.tdiv b :=
(Int.tdiv_eq_of_eq_mul_left H1 H2.symm).symm
@[simp] protected theorem tdiv_self {a : Int} (H : a ≠ 0) : a.tdiv a = 1 := by
have := Int.mul_tdiv_cancel 1 H; rwa [Int.one_mul] at this
@[simp] protected theorem neg_tdiv : ∀ a b : Int, (-a).tdiv b = -(a.tdiv b)
| 0, n => by simp [Int.neg_zero]
| succ _, (n:Nat) => by simp [tdiv, ← Int.negSucc_eq]
| -[_+1], 0 | -[_+1], -[_+1] => by
simp only [tdiv, neg_negSucc, ← Int.natCast_succ, Int.neg_neg]
| succ _, -[_+1] | -[_+1], succ _ => (Int.neg_neg _).symm
protected theorem neg_tdiv_neg (a b : Int) : (-a).tdiv (-b) = a.tdiv b := by
simp [Int.tdiv_neg, Int.neg_tdiv, Int.neg_neg]
theorem sign_tdiv (a b : Int) : sign (a.tdiv b) = if natAbs a < natAbs b then 0 else sign a * sign b := by
induction b using wlog_sign
case inv => simp; split <;> simp [Int.mul_neg]
case w b =>
induction a using wlog_sign
case inv => simp; split <;> simp [Int.neg_mul]
case w a =>
rw [tdiv_eq_ediv_of_nonneg (by simp), sign_ediv]
simp
@[simp] theorem natAbs_tdiv (a b : Int) : natAbs (a.tdiv b) = (natAbs a).div (natAbs b) :=
match a, b, Int.eq_nat_or_neg a, Int.eq_nat_or_neg b with
| _, _, ⟨_, .inl rfl⟩, ⟨_, .inl rfl⟩ => rfl
| _, _, ⟨_, .inl rfl⟩, ⟨_, .inr rfl⟩ => by rw [Int.tdiv_neg, natAbs_neg, natAbs_neg]; rfl
| _, _, ⟨_, .inr rfl⟩, ⟨_, .inl rfl⟩ => by rw [Int.neg_tdiv, natAbs_neg, natAbs_neg]; rfl
| _, _, ⟨_, .inr rfl⟩, ⟨_, .inr rfl⟩ => by rw [Int.neg_tdiv_neg, natAbs_neg, natAbs_neg]; rfl
/-! ### tmod -/
-- `tmod` analogues of `emod` lemmas from `Bootstrap.lean`
theorem ofNat_tmod (m n : Nat) : (↑(m % n) : Int) = tmod m n := rfl
theorem tmod_nonneg : ∀ {a : Int} (b : Int), 0 ≤ a → 0 ≤ tmod a b
| ofNat _, -[_+1], _ | ofNat _, ofNat _, _ => ofNat_nonneg _
@[simp] theorem tmod_neg (a b : Int) : tmod a (-b) = tmod a b := by
rw [tmod_def, tmod_def, Int.tdiv_neg, Int.neg_mul_neg]
@[simp] theorem neg_tmod (a b : Int) : tmod (-a) b = -tmod a b := by
rw [tmod_def, Int.neg_tdiv, Int.mul_neg, tmod_def]
omega
theorem tmod_lt_of_pos (a : Int) {b : Int} (H : 0 < b) : tmod a b < b :=
match a, b, eq_succ_of_zero_lt H with
| ofNat _, _, ⟨n, rfl⟩ => ofNat_lt.2 <| Nat.mod_lt _ n.succ_pos
| -[_+1], _, ⟨n, rfl⟩ => Int.lt_of_le_of_lt
(Int.neg_nonpos_of_nonneg <| Int.ofNat_nonneg _) (ofNat_pos.2 n.succ_pos)
theorem lt_tmod_of_pos (a : Int) {b : Int} (H : 0 < b) : -b < tmod a b :=
match a, b, eq_succ_of_zero_lt H with
| ofNat _, _, ⟨n, rfl⟩ => by rw [ofNat_eq_coe, ← Int.natCast_succ, ← ofNat_tmod]; omega
| -[a+1], _, ⟨n, rfl⟩ => by
rw [negSucc_eq, neg_tmod, ← Int.natCast_succ, ← Int.natCast_succ, ← ofNat_tmod]
have : (a + 1) % (n + 1) < n + 1 := Nat.mod_lt _ (Nat.zero_lt_succ n)
omega
-- The following statements for `tmod` are false:
-- `add_mul_tmod_self_right {a b c : Int} : (a + b * c).tmod c = a.tmod c`
-- `add_mul_tmod_self_left (a b c : Int) : (a + b * c).tmod b = a.tmod b`
-- `tmod_add_tmod (m n k : Int) : (m.tmod n + k).tmod n = (m + k).tmod n`
-- `add_tmod_tmod (m n k : Int) : (m + n.tmod k).tmod k = (m + n).tmod k`
-- `add_tmod (a b n : Int) : (a + b).tmod n = (a.tmod n + b.tmod n).tmod n`
-- `add_tmod_eq_add_tmod_right {m n k : Int} (i : Int) : (m.tmod n = k.tmod n) → (m + i).tmod n = (k + i).tmod n`
-- `tmod_add_cancel_right {m n k : Int} (i) : (m + i).tmod n = (k + i).tmod n ↔ m.tmod n = k.tmod n`
-- `sub_tmod (a b n : Int) : (a - b).tmod n = (a.tmod n - b.tmod n).tmod n`
@[simp] theorem mul_tmod_left (a b : Int) : (a * b).tmod b = 0 :=
if h : b = 0 then by simp [h, Int.mul_zero] else by
rw [Int.tmod_def, Int.mul_tdiv_cancel _ h, Int.mul_comm, Int.sub_self]
@[simp] theorem mul_tmod_right (a b : Int) : (a * b).tmod a = 0 := by
rw [Int.mul_comm, mul_tmod_left]
theorem mul_tmod (a b n : Int) : (a * b).tmod n = (a.tmod n * b.tmod n).tmod n := by
induction a using wlog_sign
case inv => simp [Int.neg_mul]
induction b using wlog_sign
case inv => simp [Int.mul_neg]
induction n using wlog_sign
case inv => simp
simp only [← Int.natCast_mul, ← ofNat_tmod]
rw [Nat.mul_mod]
@[simp] theorem tmod_self {a : Int} : a.tmod a = 0 := by
have := mul_tmod_left 1 a; rwa [Int.one_mul] at this
@[simp] theorem tmod_tmod_of_dvd (n : Int) {m k : Int}
(h : m ∣ k) : (n.tmod k).tmod m = n.tmod m := by
induction n using wlog_sign
case inv => simp
induction k using wlog_sign
case inv => simp [Int.dvd_neg]
induction m using wlog_sign
case inv => simp
simp only [← Int.natCast_mul, ← ofNat_tmod]
norm_cast at h
rw [Nat.mod_mod_of_dvd _ h]
@[simp] theorem tmod_tmod (a b : Int) : (a.tmod b).tmod b = a.tmod b :=
tmod_tmod_of_dvd a (Int.dvd_refl b)
theorem tmod_eq_zero_of_dvd : ∀ {a b : Int}, a ∣ b → tmod b a = 0
| _, _, ⟨_, rfl⟩ => mul_tmod_right ..
-- `tmod` analogues of `emod` lemmas from above
theorem tmod_eq_of_lt {a b : Int} (H1 : 0 ≤ a) (H2 : a < b) : tmod a b = a := by
rw [tmod_eq_emod_of_nonneg H1, emod_eq_of_lt H1 H2]
theorem sign_tmod (a b : Int) : sign (tmod a b) = if b ∣ a then 0 else sign a := by
if hb : b = 0 then
subst hb
split <;> simp_all
else
induction a using wlog_sign
case inv a => split <;> simp_all
rename_i a
match a with
| 0 => simp
| (a + 1) =>
simp
split
· simp [tmod_eq_zero_of_dvd, *]
· norm_cast
rw [tmod_eq_emod_of_nonneg (by omega)]
rw [sign_emod _ hb]
simp_all
@[simp] theorem natAbs_tmod (a b : Int) : natAbs (tmod a b) = natAbs a % natAbs b := by
induction a using wlog_sign
case inv => simp
induction b using wlog_sign
case inv => simp
norm_cast
/-! properties of `tdiv` and `tmod` -/
-- Analogues of statements about `ediv` and `emod` from `Bootstrap.lean`
theorem mul_tdiv_cancel_of_tmod_eq_zero {a b : Int} (H : a.tmod b = 0) : b * (a.tdiv b) = a := by
have := tmod_add_tdiv a b; rwa [H, Int.zero_add] at this
theorem tdiv_mul_cancel_of_tmod_eq_zero {a b : Int} (H : a.tmod b = 0) : a.tdiv b * b = a := by
rw [Int.mul_comm, mul_tdiv_cancel_of_tmod_eq_zero H]
theorem dvd_of_tmod_eq_zero {a b : Int} (H : tmod b a = 0) : a ∣ b :=
⟨b.tdiv a, (mul_tdiv_cancel_of_tmod_eq_zero H).symm⟩
theorem dvd_iff_tmod_eq_zero {a b : Int} : a ∣ b ↔ tmod b a = 0 :=
⟨tmod_eq_zero_of_dvd, dvd_of_tmod_eq_zero⟩
protected theorem tdiv_mul_cancel {a b : Int} (H : b ∣ a) : a.tdiv b * b = a :=
tdiv_mul_cancel_of_tmod_eq_zero (tmod_eq_zero_of_dvd H)
protected theorem mul_tdiv_cancel' {a b : Int} (H : a ∣ b) : a * b.tdiv a = b := by
rw [Int.mul_comm, Int.tdiv_mul_cancel H]
@[simp] theorem neg_tmod_self (a : Int) : (-a).tmod a = 0 := by
rw [← dvd_iff_tmod_eq_zero, Int.dvd_neg]
exact Int.dvd_refl a
theorem lt_tdiv_add_one_mul_self (a : Int) {b : Int} (H : 0 < b) : a < (a.tdiv b + 1) * b := by
rw [Int.add_mul, Int.one_mul, Int.mul_comm]
exact Int.lt_add_of_sub_left_lt <| Int.tmod_def .. ▸ tmod_lt_of_pos _ H
protected theorem mul_tdiv_assoc (a : Int) : ∀ {b c : Int}, c ∣ b → (a * b).tdiv c = a * (b.tdiv c)
| _, c, ⟨d, rfl⟩ =>
if cz : c = 0 then by simp [cz, Int.mul_zero] else by
rw [Int.mul_left_comm, Int.mul_tdiv_cancel_left _ cz, Int.mul_tdiv_cancel_left _ cz]
protected theorem mul_tdiv_assoc' (b : Int) {a c : Int} (h : c ∣ a) :
(a * b).tdiv c = a.tdiv c * b := by
rw [Int.mul_comm, Int.mul_tdiv_assoc _ h, Int.mul_comm]
theorem neg_tdiv_of_dvd : ∀ {a b : Int}, b ∣ a → (-a).tdiv b = -(a.tdiv b)
| _, b, ⟨c, rfl⟩ => by
by_cases bz : b = 0
· simp [bz]
· rw [Int.neg_mul_eq_mul_neg, Int.mul_tdiv_cancel_left _ bz, Int.mul_tdiv_cancel_left _ bz]
-- `sub_tdiv_of_dvd (a : Int) {b c : Int} (hcb : c ∣ b) : (a - b).tdiv c = a.tdiv c - b.tdiv c` is false in general
theorem tdiv_dvd_tdiv : ∀ {a b c : Int}, a ∣ b → b ∣ c → b.tdiv a ∣ c.tdiv a
| a, _, _, ⟨b, rfl⟩, ⟨c, rfl⟩ => by
by_cases az : a = 0
· simp [az]
· rw [Int.mul_tdiv_cancel_left _ az, Int.mul_assoc, Int.mul_tdiv_cancel_left _ az]
apply Int.dvd_mul_right
-- Analogues of statements about `emod` and `ediv` from above.
theorem mul_tdiv_cancel_of_dvd {a b : Int} (H : b ∣ a) : b * (a.tdiv b) = a :=
mul_tdiv_cancel_of_tmod_eq_zero (tmod_eq_zero_of_dvd H)
theorem tdiv_mul_cancel_of_dvd {a b : Int} (H : b ∣ a) : a.tdiv b * b = a :=
tdiv_mul_cancel_of_tmod_eq_zero (tmod_eq_zero_of_dvd H)
theorem tmod_two_eq (x : Int) : x.tmod 2 = -1 ∨ x.tmod 2 = 0 ∨ x.tmod 2 = 1 := by
have h₁ : -2 < x.tmod 2 := Int.lt_tmod_of_pos x (by decide)
have h₂ : x.tmod 2 < 2 := Int.tmod_lt_of_pos x (by decide)
match x.tmod 2, h₁, h₂ with
| -1, _, _ => simp
| 0, _, _ => simp
| 1, _, _ => simp
-- The following statements about `tmod` are false:
-- `add_tmod_eq_add_tmod_left {m n k : Int} (i : Int) (H : m.tmod n = k.tmod n) : (i + m).tmod n = (i + k).tmod n`
-- `tmod_add_cancel_left {m n k i : Int} : (i + m).tmod n = (i + k).tmod n ↔ m.tmod n = k.tmod n`
-- `tmod_sub_cancel_right {m n k : Int} (i) : (m - i).tmod n = (k - i).tmod n ↔ m.tmod n = k.tmod n`
-- `tmod_eq_tmod_iff_tmod_sub_eq_zero {m n k : Int} : m.tmod n = k.tmod n ↔ (m - k).tmod n = 0`
protected theorem tdiv_tmod_unique {a b r q : Int} (ha : 0 ≤ a) (hb : b ≠ 0) :
a.tdiv b = q ∧ a.tmod b = r ↔ r + b * q = a ∧ 0 ≤ r ∧ r < natAbs b := by
rw [tdiv_eq_ediv_of_nonneg ha, tmod_eq_emod_of_nonneg ha]
by_cases hb' : 0 < b
· rw [Int.ediv_emod_unique hb']
omega
· replace hb' : 0 < -b := by omega
have := Int.ediv_emod_unique (a := a) (q := -q) (r := r) hb'
simp at this
simp [this, Int.neg_mul, Int.mul_neg]
omega
protected theorem tdiv_tmod_unique' {a b r q : Int} (ha : a ≤ 0) (hb : b ≠ 0) :
a.tdiv b = q ∧ a.tmod b = r ↔ r + b * q = a ∧ -natAbs b < r ∧ r ≤ 0 := by
have := Int.tdiv_tmod_unique (a := -a) (q := -q) (r := -r) (by omega) hb
simp at this
simp [this, Int.mul_neg]
omega
@[simp] theorem mul_tmod_mul_of_pos
{a : Int} (b c : Int) (H : 0 < a) : (a * b).tmod (a * c) = a * (b.tmod c) := by
rw [tmod_def, tmod_def, mul_tdiv_mul_of_pos _ _ H, Int.mul_sub, Int.mul_assoc]
theorem natAbs_tdiv_le_natAbs (a b : Int) : natAbs (a.tdiv b) ≤ natAbs a := by
induction a using wlog_sign
case inv => simp
induction b using wlog_sign
case inv => simp
simpa using Nat.div_le_self _ _
theorem tdiv_le_self {a : Int} (b : Int) (Ha : 0 ≤ a) : a.tdiv b ≤ a := by
have := Int.le_trans le_natAbs (ofNat_le.2 <| natAbs_tdiv_le_natAbs a b)
rwa [natAbs_of_nonneg Ha] at this
theorem dvd_tmod_sub_self {x m : Int} : m ∣ x.tmod m - x := by
rw [tmod_eq_emod]
have := dvd_emod_sub_self (x := x) (m := m)
split
· simpa
· rw [Int.sub_sub, Int.add_comm, ← Int.sub_sub]
exact Int.dvd_sub this dvd_natAbs_self
theorem dvd_self_sub_tmod {x m : Int} : m ∣ x - x.tmod m :=
Int.dvd_neg.1 (by simpa only [Int.neg_sub] using dvd_tmod_sub_self)
@[simp] theorem neg_mul_tmod_right (a b : Int) : (-(a * b)).tmod a = 0 := by
rw [← dvd_iff_tmod_eq_zero, Int.dvd_neg]
exact Int.dvd_mul_right a b
@[simp] theorem neg_mul_tmod_left (a b : Int) : (-(a * b)).tmod b = 0 := by
rw [← dvd_iff_tmod_eq_zero, Int.dvd_neg]
exact Int.dvd_mul_left a b
@[simp] protected theorem tdiv_one : ∀ a : Int, a.tdiv 1 = a
| (n:Nat) => congrArg ofNat (Nat.div_one _)
| -[n+1] => by simp [Int.tdiv, neg_ofNat_succ]; rfl
@[simp] theorem tmod_one (a : Int) : tmod a 1 = 0 := by
simp [tmod_def, Int.tdiv_one, Int.one_mul, Int.sub_self]
-- The following statements about `tmod` are false:
-- `tmod_sub_cancel (x y : Int) : (x - y).tmod y = x.tmod y`
-- `add_neg_tmod_self (a b : Int) : (a + -b).tmod b = a.tmod b`
-- `neg_add_tmod_self (a b : Int) : (-a + b).tmod a = b.tmod a`
theorem dvd_self_sub_of_tmod_eq {a b c : Int} (h : a.tmod b = c) : b ∣ a - c :=
h ▸ dvd_self_sub_tmod
theorem dvd_sub_self_of_tmod_eq {a b c : Int} (h : a.tmod b = c) : b ∣ c - a :=
h ▸ dvd_tmod_sub_self
protected theorem eq_mul_of_tdiv_eq_right {a b c : Int}
(H1 : b ∣ a) (H2 : a.tdiv b = c) : a = b * c := by rw [← H2, Int.mul_tdiv_cancel' H1]
protected theorem tdiv_eq_iff_eq_mul_right {a b c : Int}
(H : b ≠ 0) (H' : b ∣ a) : a.tdiv b = c ↔ a = b * c :=
⟨Int.eq_mul_of_tdiv_eq_right H', Int.tdiv_eq_of_eq_mul_right H⟩
protected theorem tdiv_eq_iff_eq_mul_left {a b c : Int}
(H : b ≠ 0) (H' : b ∣ a) : a.tdiv b = c ↔ a = c * b := by
rw [Int.mul_comm]; exact Int.tdiv_eq_iff_eq_mul_right H H'
protected theorem eq_mul_of_tdiv_eq_left {a b c : Int}
(H1 : b ∣ a) (H2 : a.tdiv b = c) : a = c * b := by
rw [Int.mul_comm, Int.eq_mul_of_tdiv_eq_right H1 H2]
protected theorem eq_zero_of_tdiv_eq_zero {d n : Int} (h : d ∣ n) (H : n.tdiv d = 0) : n = 0 := by
rw [← Int.mul_tdiv_cancel' h, H, Int.mul_zero]
-- `sub_tdiv_of_dvd_sub {a b c : Int} (hcab : c ∣ a - b) : (a - b).tdiv c = a.tdiv c - b.tdiv c` is false in general
@[simp] protected theorem tdiv_left_inj {a b d : Int}
(hda : d ∣ a) (hdb : d ∣ b) : a.tdiv d = b.tdiv d ↔ a = b := by
refine ⟨fun h => ?_, congrArg (tdiv · d)⟩
rw [← Int.mul_tdiv_cancel' hda, ← Int.mul_tdiv_cancel' hdb, h]
theorem tdiv_sign : ∀ a b, a.tdiv (sign b) = a * sign b
| _, succ _ => by simp [sign, Int.mul_one]
| _, 0 => by simp [sign, Int.mul_zero]
| _, -[_+1] => by simp [sign, Int.mul_neg, Int.mul_one]
protected theorem sign_eq_tdiv_abs (a : Int) : sign a = a.tdiv (natAbs a) :=
if az : a = 0 then by simp [az] else
(Int.tdiv_eq_of_eq_mul_left (ofNat_ne_zero.2 <| natAbs_ne_zero.2 az)
(sign_mul_natAbs _).symm).symm
@[simp high] protected theorem mul_le_mul_left {a b c : Int} (ha : 0 < a) : a * b ≤ a * c ↔ b ≤ c where
mp hbc := Int.le_of_mul_le_mul_left hbc ha
mpr hbc := Int.mul_le_mul_of_nonneg_left hbc <| Int.le_of_lt ha
@[simp high] protected theorem mul_le_mul_right {a b c : Int} (ha : 0 < a) : b * a ≤ c * a ↔ b ≤ c where
mp hbc := Int.le_of_mul_le_mul_right hbc ha
mpr hbc := Int.mul_le_mul_of_nonneg_right hbc <| Int.le_of_lt ha
@[simp high] protected theorem mul_lt_mul_left {a b c : Int} (ha : 0 < a) : a * b < a * c ↔ b < c where
mp hbc := Int.lt_of_mul_lt_mul_left hbc <| Int.le_of_lt ha
mpr hbc := Int.mul_lt_mul_of_pos_left hbc ha
@[simp high] protected theorem mul_lt_mul_right {a b c : Int} (ha : 0 < a) : b * a < c * a ↔ b < c where
mp hbc := Int.lt_of_mul_lt_mul_right hbc <| Int.le_of_lt ha
mpr hbc := Int.mul_lt_mul_of_pos_right hbc ha
@[simp high] protected theorem mul_le_mul_left_of_neg {a b c : Int} (ha : a < 0) :
a * b ≤ a * c ↔ c ≤ b := by
rw [← Int.neg_le_neg_iff, Int.neg_mul_eq_neg_mul, Int.neg_mul_eq_neg_mul,
Int.mul_le_mul_left <| Int.neg_pos.2 ha]
@[simp high] protected theorem mul_le_mul_right_of_neg {a b c : Int} (ha : a < 0) :
b * a ≤ c * a ↔ c ≤ b := by
rw [← Int.neg_le_neg_iff, Int.neg_mul_eq_mul_neg, Int.neg_mul_eq_mul_neg,
Int.mul_le_mul_right <| Int.neg_pos.2 ha]
@[simp high] protected theorem mul_lt_mul_left_of_neg {a b c : Int} (ha : a < 0) :
a * b < a * c ↔ c < b := by
rw [← Int.neg_lt_neg_iff, Int.neg_mul_eq_neg_mul, Int.neg_mul_eq_neg_mul,
Int.mul_lt_mul_left <| Int.neg_pos.2 ha]
@[simp high] protected theorem mul_lt_mul_right_of_neg {a b c : Int} (ha : a < 0) :
b * a < c * a ↔ c < b := by
rw [← Int.neg_lt_neg_iff, Int.neg_mul_eq_mul_neg, Int.neg_mul_eq_mul_neg,
Int.mul_lt_mul_right <| Int.neg_pos.2 ha]
theorem ediv_le_iff_of_dvd_of_pos {a b c : Int} (hb : 0 < b) (hba : b ∣ a) :
a / b ≤ c ↔ a ≤ b * c := by
obtain ⟨x, rfl⟩ := hba; simp [*, Int.ne_of_gt]
theorem ediv_le_iff_of_dvd_of_neg {a b c : Int} (hb : b < 0) (hba : b ∣ a) :
a / b ≤ c ↔ b * c ≤ a := by
obtain ⟨x, rfl⟩ := hba; simp [*, Int.ne_of_lt]
theorem ediv_lt_iff_of_dvd_of_pos {a b c : Int} (hb : 0 < b) (hba : b ∣ a) :
a / b < c ↔ a < b * c := by
obtain ⟨x, rfl⟩ := hba; simp [*, Int.ne_of_gt]
theorem ediv_lt_iff_of_dvd_of_neg {a b c : Int} (hb : b < 0) (hba : b ∣ a) :
a / b < c ↔ b * c < a := by
obtain ⟨x, rfl⟩ := hba; simp [*, Int.ne_of_lt]
theorem le_ediv_iff_of_dvd_of_pos {a b c : Int} (hc : 0 < c) (hcb : c ∣ b) :
a ≤ b / c ↔ c * a ≤ b := by
obtain ⟨x, rfl⟩ := hcb; simp [*, Int.ne_of_gt]
theorem le_ediv_iff_of_dvd_of_neg {a b c : Int} (hc : c < 0) (hcb : c ∣ b) :
a ≤ b / c ↔ b ≤ c * a := by
obtain ⟨x, rfl⟩ := hcb; simp [*, Int.ne_of_lt]
theorem lt_ediv_iff_of_dvd_of_pos {a b c : Int} (hc : 0 < c) (hcb : c ∣ b) :
a < b / c ↔ c * a < b := by
obtain ⟨x, rfl⟩ := hcb; simp [*, Int.ne_of_gt]
theorem lt_ediv_iff_of_dvd_of_neg {a b c : Int} (hc : c < 0) (hcb : c ∣ b) :
a < b / c ↔ b < c * a := by
obtain ⟨x, rfl⟩ := hcb; simp [*, Int.ne_of_lt]
theorem ediv_le_ediv_iff_of_dvd_of_pos_of_pos {a b c d : Int} (hb : 0 < b) (hd : 0 < d)
(hba : b ∣ a) (hdc : d ∣ c) : a / b ≤ c / d ↔ d * a ≤ c * b := by
obtain ⟨⟨x, rfl⟩, y, rfl⟩ := hba, hdc
simp [*, Int.ne_of_lt, Int.ne_of_gt, d.mul_assoc, b.mul_comm]
theorem ediv_le_ediv_iff_of_dvd_of_pos_of_neg {a b c d : Int} (hb : 0 < b) (hd : d < 0)
(hba : b ∣ a) (hdc : d ∣ c) : a / b ≤ c / d ↔ c * b ≤ d * a := by
obtain ⟨⟨x, rfl⟩, y, rfl⟩ := hba, hdc
simp [*, Int.ne_of_lt, Int.ne_of_gt, d.mul_assoc, b.mul_comm]
theorem ediv_le_ediv_iff_of_dvd_of_neg_of_pos {a b c d : Int} (hb : b < 0) (hd : 0 < d)
(hba : b ∣ a) (hdc : d ∣ c) : a / b ≤ c / d ↔ c * b ≤ d * a := by
obtain ⟨⟨x, rfl⟩, y, rfl⟩ := hba, hdc
simp [*, Int.ne_of_lt, Int.ne_of_gt, d.mul_assoc, b.mul_comm]
theorem ediv_le_ediv_iff_of_dvd_of_neg_of_neg {a b c d : Int} (hb : b < 0) (hd : d < 0)
(hba : b ∣ a) (hdc : d ∣ c) : a / b ≤ c / d ↔ d * a ≤ c * b := by
obtain ⟨⟨x, rfl⟩, y, rfl⟩ := hba, hdc
simp [*, Int.ne_of_lt, Int.ne_of_gt, d.mul_assoc, b.mul_comm]
theorem ediv_lt_ediv_iff_of_dvd_of_pos {a b c d : Int} (hb : 0 < b) (hd : 0 < d) (hba : b ∣ a)
(hdc : d ∣ c) : a / b < c / d ↔ d * a < c * b := by
obtain ⟨⟨x, rfl⟩, y, rfl⟩ := hba, hdc
simp [*, Int.ne_of_lt, Int.ne_of_gt, d.mul_assoc, b.mul_comm]
theorem ediv_lt_ediv_iff_of_dvd_of_pos_of_neg {a b c d : Int} (hb : 0 < b) (hd : d < 0)
(hba : b ∣ a) (hdc : d ∣ c) : a / b < c / d ↔ c * b < d * a := by
obtain ⟨⟨x, rfl⟩, y, rfl⟩ := hba, hdc
simp [*, Int.ne_of_lt, Int.ne_of_gt, d.mul_assoc, b.mul_comm]
theorem ediv_lt_ediv_iff_of_dvd_of_neg_of_pos {a b c d : Int} (hb : b < 0) (hd : 0 < d)
(hba : b ∣ a) (hdc : d ∣ c) : a / b < c / d ↔ c * b < d * a := by
obtain ⟨⟨x, rfl⟩, y, rfl⟩ := hba, hdc
simp [*, Int.ne_of_lt, Int.ne_of_gt, d.mul_assoc, b.mul_comm]
theorem ediv_lt_ediv_iff_of_dvd_of_neg_of_neg {a b c d : Int} (hb : b < 0) (hd : d < 0)
(hba : b ∣ a) (hdc : d ∣ c) : a / b < c / d ↔ d * a < c * b := by
obtain ⟨⟨x, rfl⟩, y, rfl⟩ := hba, hdc
simp [*, Int.ne_of_lt, Int.ne_of_gt, d.mul_assoc, b.mul_comm]
/-! ### `tdiv` and ordering -/
-- Theorems about `tdiv` and ordering, whose `ediv` analogues are in `Bootstrap.lean`.
theorem mul_tdiv_self_le {x k : Int} (h : 0 ≤ x) : k * (x.tdiv k) ≤ x := by
by_cases w : k = 0
· simp [w, h]
· rw [tdiv_eq_ediv_of_nonneg h]
apply mul_ediv_self_le w
theorem lt_mul_tdiv_self_add {x k : Int} (h : 0 < k) : x < k * (x.tdiv k) + k := by
rw [tdiv_eq_ediv, sign_eq_one_of_pos h]
have := lt_mul_ediv_self_add (x := x) h
split <;> simp [Int.mul_add] <;> omega
-- Theorems about `tdiv` and ordering, whose `ediv` analogues proved above.
protected theorem tdiv_mul_le (a : Int) {b : Int} (hb : b ≠ 0) : a.tdiv b * b ≤ a + if 0 ≤ a then 0 else (b.natAbs - 1) :=
Int.le_of_sub_nonneg <| by
rw [Int.mul_comm, Int.add_comm, Int.add_sub_assoc, ← tmod_def]
split
· simp_all [tmod_nonneg]
· match b, hb with
| .ofNat (b + 1), _ =>
have := lt_tmod_of_pos a (Int.ofNat_pos.2 (b.succ_pos))
simp_all
omega
| .negSucc b, _ =>
simp only [negSucc_eq, natAbs_neg, tmod_neg]
have := lt_tmod_of_pos (b := b + 1) a (by omega)
omega
protected theorem tdiv_le_of_le_mul {a b c : Int} (Hc : 0 < c) (H' : a ≤ b * c) : a.tdiv c ≤ b + if 0 ≤ a then 0 else 1 :=
le_of_mul_le_mul_right (Int.le_trans (Int.tdiv_mul_le _ (by omega))
(by
split
· simpa using H'
· simp [Int.add_mul]
omega)) Hc
-- We don't provide `tdiv` analogues of the lemmas
-- `mul_lt_of_lt_ediv`
-- `mul_le_of_le_ediv`
-- `ediv_lt_of_lt_mul`
-- `le_ediv_iff_mul_le`
-- `ediv_lt_iff_lt_mul`
-- `lt_ediv_iff_mul_lt`
-- as they would require quite awkward statements.
protected theorem le_tdiv_of_mul_le {a b c : Int} (H1 : 0 < c) (H2 : a * c ≤ b) : a ≤ b.tdiv c :=
le_of_lt_add_one <|
lt_of_mul_lt_mul_right (Int.lt_of_le_of_lt H2 (lt_tdiv_add_one_mul_self _ H1)) (Int.le_of_lt H1)
protected theorem lt_mul_of_tdiv_lt {a b c : Int} (H1 : 0 < c) (H2 : a.tdiv c < b) : a < b * c :=
Int.lt_of_not_ge <| mt (Int.le_tdiv_of_mul_le H1) (Int.not_le_of_gt H2)
protected theorem le_mul_of_tdiv_le {a b c : Int} (H1 : 0 ≤ b) (H2 : b ∣ a) (H3 : a.tdiv b ≤ c) :
a ≤ c * b := by
rw [← Int.tdiv_mul_cancel H2]; exact Int.mul_le_mul_of_nonneg_right H3 H1
protected theorem lt_tdiv_of_mul_lt {a b c : Int} (H1 : 0 ≤ b) (H2 : b ∣ c) (H3 : a * b < c) :
a < c.tdiv b :=
Int.lt_of_not_ge <| mt (Int.le_mul_of_tdiv_le H1 H2) (Int.not_le_of_gt H3)
theorem tdiv_pos_of_pos_of_dvd {a b : Int} (H1 : 0 < a) (H2 : 0 ≤ b) (H3 : b ∣ a) : 0 < a.tdiv b :=
Int.lt_tdiv_of_mul_lt H2 H3 (by rwa [Int.zero_mul])
theorem tdiv_eq_tdiv_of_mul_eq_mul {a b c d : Int}
(H2 : d ∣ c) (H3 : b ≠ 0) (H4 : d ≠ 0) (H5 : a * d = b * c) : a.tdiv b = c.tdiv d :=
Int.tdiv_eq_of_eq_mul_right H3 <| by
rw [← Int.mul_tdiv_assoc _ H2]; exact (Int.tdiv_eq_of_eq_mul_left H4 H5.symm).symm
theorem le_emod_self_add_one_iff {a b : Int} (h : 0 < b) : b ≤ a % b + 1 ↔ b ∣ a + 1 := by
match b, h with
| .ofNat 1, h => simp
| .ofNat (b + 2), h =>
simp only [ofNat_eq_coe, Int.natCast_add, cast_ofNat_Int] at *
constructor
· rw [dvd_iff_emod_eq_zero]
intro w
have := emod_lt_of_pos a h
have : a % (b + 2) = b + 1 := by omega
rw [add_emod, this, one_emod, if_neg (by omega)]
have : (b + 1 + 1 : Int) = b + 2 := by omega
rw [this, emod_self]
· rintro ⟨d, w⟩
replace w : a = (b + 2 : Int) * d - 1 := by omega
subst w
rw [emod_def, mul_sub_ediv_left _ _ (by omega), neg_one_ediv,
sign_eq_one_of_pos (by omega), Int.mul_add]
omega
@[deprecated le_emod_self_add_one_iff (since := "2025-04-12")]
theorem le_mod_self_add_one_iff {a b : Int} (h : 0 < b) : b ≤ a % b + 1 ↔ b ∣ a + 1 :=
le_emod_self_add_one_iff h
theorem add_one_tdiv_of_pos {a b : Int} (h : 0 < b) :
(a + 1).tdiv b = a.tdiv b + if (0 < a + 1 ∧ b ∣ a + 1) ∨ (a < 0 ∧ b ∣ a) then 1 else 0 := by
match b, h with
| .ofNat 1, h => simp; omega
| .ofNat (b + 2), h =>
simp only [ofNat_eq_coe]
rw [tdiv_eq_ediv, add_ediv (by omega), tdiv_eq_ediv]
simp only [Int.natCast_add, cast_ofNat_Int]
have : 1 / (b + 2 : Int) = 0 := by rw [one_ediv]; omega
rw [this]
have one_mod : 1 % (b + 2 : Int) = 1 := emod_eq_of_lt (by omega) (by omega)
rw [one_mod]
have : ↑(b + 2 : Int).natAbs = (b + 2 : Int) := by omega
rw [this]
have : (b + 2 : Int).sign = 1 := sign_eq_one_of_pos (by omega)
rw [this]
have : (b + 2) ≤ a % (b + 2 : Int) + 1 ↔ (b + 2 : Int) ∣ a + 1 := le_emod_self_add_one_iff (by omega)
simp only [this]
simp only [Int.add_zero]
split <;> rename_i h
· simp only [h, or_true, ↓reduceIte, and_true]
omega
· simp only [h, or_false, and_false]
by_cases h₂ : 0 ≤ a
· simp only [Int.add_zero, h₂, true_or, ↓reduceIte, false_or]
have : 0 ≤ a + 1 := by omega
have : 0 < a + 1 := by omega
have : ¬ a < 0 := by omega
simp [*]
· simp only [Int.add_zero, h₂, false_or]
split
· have : a = -1 := by omega
simp_all
· have : a < 0 := by omega
simp only [true_and, this]
split <;> simp
theorem add_one_tdiv {a b : Int} :
(a + 1).tdiv b = a.tdiv b + if (0 < a + 1 ∧ b ∣ a + 1) ∨ (a < 0 ∧ b ∣ a) then b.sign else 0 := by
if hb : b = 0 then
simp [hb]
else
induction b using wlog_sign
case inv => simp; omega
rename_i c
norm_cast at hb
have : 0 < (c : Int) := by omega
simp [sign_natCast_of_ne_zero hb, add_one_tdiv_of_pos this]
-- One could prove a general `add_tdiv` theorem giving `(a + b).tdiv c = a.tdiv c + b.tdiv c + ...`
-- but the error term would be very complicated.
protected theorem tdiv_le_tdiv {a b c : Int} (H : 0 < c) (H' : a ≤ b) : a.tdiv c ≤ b.tdiv c := by
obtain ⟨d, rfl⟩ := Int.exists_add_of_le H'
clear H'
induction d with
| zero => simp
| succ d ih =>
simp only [Int.natCast_add, cast_ofNat_Int, ← Int.add_assoc]
rw [add_one_tdiv_of_pos (by omega)]
omega
/-! ### fdiv -/
theorem add_mul_fdiv_right (a b : Int) {c : Int} (H : c ≠ 0) : (a + b * c).fdiv c = a.fdiv c + b := by
rw [fdiv_eq_ediv, add_mul_ediv_right _ _ H, fdiv_eq_ediv]
simp only [Int.dvd_add_left (Int.dvd_mul_left _ _)]
split <;> omega
theorem add_mul_fdiv_left (a : Int) {b : Int}
(c : Int) (H : b ≠ 0) : (a + b * c).fdiv b = a.fdiv b + c := by
rw [Int.mul_comm, Int.add_mul_fdiv_right _ _ H]
theorem mul_add_fdiv_right (a c : Int) {b : Int} (H : b ≠ 0) : (a * b + c).fdiv b = c.fdiv b + a := by
rw [Int.add_comm, add_mul_fdiv_right _ _ H]
theorem mul_add_fdiv_left (b : Int) {a : Int}
(c : Int) (H : a ≠ 0) : (a * b + c).fdiv a = c.fdiv a + b := by
rw [Int.add_comm, add_mul_fdiv_left _ _ H]
theorem sub_mul_fdiv_right (a b : Int) {c : Int} (H : c ≠ 0) : (a - b * c).fdiv c = a.fdiv c - b := by
rw [Int.sub_eq_add_neg, ← Int.neg_mul, add_mul_fdiv_right _ _ H, Int.sub_eq_add_neg]
theorem sub_mul_fdiv_left (a : Int) {b : Int}
(c : Int) (H : b ≠ 0) : (a - b * c).fdiv b = a.fdiv b - c := by
rw [Int.sub_eq_add_neg, ← Int.mul_neg, add_mul_fdiv_left _ _ H, Int.sub_eq_add_neg]
theorem mul_sub_fdiv_right (a c : Int) {b : Int} (H : b ≠ 0) : (a * b - c).fdiv b = a + (-c).fdiv b := by
rw [Int.sub_eq_add_neg, Int.add_comm, add_mul_fdiv_right _ _ H, Int.add_comm]
theorem mul_sub_fdiv_left (b : Int) {a : Int}
(c : Int) (H : a ≠ 0) : (a * b - c).fdiv a = b + (-c).fdiv a := by
rw [Int.sub_eq_add_neg, Int.add_comm, add_mul_fdiv_left _ _ H, Int.add_comm]
@[simp] theorem mul_fdiv_cancel (a : Int) {b : Int} (H : b ≠ 0) : fdiv (a * b) b = a :=
if b0 : 0 ≤ b then by
rw [fdiv_eq_ediv_of_nonneg _ b0, mul_ediv_cancel _ H]
else
match a, b, Int.not_le.1 b0 with
| 0, _, _ => by simp [Int.zero_mul]
| succ a, -[b+1], _ => congrArg ofNat <| Nat.mul_div_cancel (succ a) b.succ_pos
| -[a+1], -[b+1], _ => congrArg negSucc <| Nat.div_eq_of_lt_le
(Nat.le_of_lt_succ <| Nat.mul_lt_mul_of_pos_right a.lt_succ_self b.succ_pos)
(Nat.lt_succ_self _)
@[simp] theorem mul_fdiv_cancel_left (b : Int) (H : a ≠ 0) : fdiv (a * b) a = b :=
Int.mul_comm .. ▸ Int.mul_fdiv_cancel _ H
theorem add_fdiv_of_dvd_right {a b c : Int} (H : c ∣ b) : (a + b).fdiv c = a.fdiv c + b.fdiv c := by
by_cases h : c = 0
· simp [h]
· obtain ⟨d, rfl⟩ := H
rw [add_mul_fdiv_left _ _ h]
simp [h]
theorem add_fdiv_of_dvd_left {a b c : Int} (H : c ∣ a) : (a + b).fdiv c = a.fdiv c + b.fdiv c := by
rw [Int.add_comm, Int.add_fdiv_of_dvd_right H, Int.add_comm]
theorem fdiv_nonneg {a b : Int} (Ha : 0 ≤ a) (Hb : 0 ≤ b) : 0 ≤ a.fdiv b :=
match a, b, eq_ofNat_of_zero_le Ha, eq_ofNat_of_zero_le Hb with
| _, _, ⟨_, rfl⟩, ⟨_, rfl⟩ => ofNat_fdiv .. ▸ ofNat_zero_le _
theorem fdiv_nonneg_of_nonpos_of_nonpos {a b : Int} (Ha : a ≤ 0) (Hb : b ≤ 0) : 0 ≤ a.fdiv b := by
rw [fdiv_eq_ediv]
by_cases ha : a = 0
· simp [ha]
· by_cases hb : b = 0
· simp [hb]
· have : 0 < a / b := ediv_pos_of_neg_of_neg (by omega) (by omega)
split <;> omega
theorem fdiv_nonpos_of_nonneg_of_nonpos : ∀ {a b : Int}, 0 ≤ a → b ≤ 0 → a.fdiv b ≤ 0
| 0, 0, _, _ | 0, -[_+1], _, _ | succ _, 0, _, _ | succ _, -[_+1], _, _ => by
simp [fdiv, negSucc_le_zero]
@[deprecated fdiv_nonpos_of_nonneg_of_nonpos (since := "2025-03-04")]
abbrev fdiv_nonpos := @fdiv_nonpos_of_nonneg_of_nonpos
theorem fdiv_neg_of_neg_of_pos : ∀ {a b : Int}, a < 0 → 0 < b → a.fdiv b < 0
| -[_+1], succ _, _, _ => negSucc_lt_zero _
theorem fdiv_eq_zero_of_lt {a b : Int} (H1 : 0 ≤ a) (H2 : a < b) : a.fdiv b = 0 := by
rw [fdiv_eq_ediv, if_pos, Int.sub_zero]
· apply ediv_eq_zero_of_lt (by omega) (by omega)
· left; omega
@[simp] theorem mul_fdiv_mul_of_pos {a : Int}
(b c : Int) (H : 0 < a) : (a * b).fdiv (a * c) = b.fdiv c := by
rw [fdiv_eq_ediv, mul_ediv_mul_of_pos _ _ H, fdiv_eq_ediv]
congr 2
simp [Int.mul_dvd_mul_iff_left (Int.ne_of_gt H)]
constructor
· rintro (h | h)
· exact .inl (Int.nonneg_of_mul_nonneg_right h H)
· exact .inr h
· rintro (h | h)
· exact .inl (Int.mul_nonneg (by omega) h)
· exact .inr h
@[simp] theorem mul_fdiv_mul_of_pos_left
(a : Int) {b : Int} (c : Int) (H : 0 < b) : (a * b).fdiv (c * b) = a.fdiv c := by
rw [Int.mul_comm a b, Int.mul_comm c b, Int.mul_fdiv_mul_of_pos _ _ H]
@[simp] theorem fdiv_one : ∀ a : Int, a.fdiv 1 = a
| 0 => rfl
| succ _ => congrArg Nat.cast (Nat.div_one _)
| -[_+1] => congrArg negSucc (Nat.div_one _)
protected theorem fdiv_eq_of_eq_mul_right {a b c : Int}
(H1 : b ≠ 0) (H2 : a = b * c) : a.fdiv b = c := by rw [H2, Int.mul_fdiv_cancel_left _ H1]
protected theorem eq_fdiv_of_mul_eq_right {a b c : Int}
(H1 : a ≠ 0) (H2 : a * b = c) : b = c.tdiv a :=
(Int.tdiv_eq_of_eq_mul_right H1 H2.symm).symm
protected theorem fdiv_eq_of_eq_mul_left {a b c : Int}
(H1 : b ≠ 0) (H2 : a = c * b) : a.fdiv b = c :=
Int.fdiv_eq_of_eq_mul_right H1 (by rw [Int.mul_comm, H2])
protected theorem eq_fdiv_of_mul_eq_left {a b c : Int}
(H1 : b ≠ 0) (H2 : a * b = c) : a = c.fdiv b :=
(Int.fdiv_eq_of_eq_mul_left H1 H2.symm).symm
@[simp] protected theorem fdiv_self {a : Int} (H : a ≠ 0) : a.fdiv a = 1 := by
have := Int.mul_fdiv_cancel 1 H; rwa [Int.one_mul] at this
theorem neg_fdiv {a b : Int} : (-a).fdiv b = -(a.fdiv b) - if b = 0 ∨ b ∣ a then 0 else 1 := by
rw [fdiv_eq_ediv, fdiv_eq_ediv, neg_ediv]
simp
by_cases h : b ∣ a
· simp [h]
· simp [h]
by_cases h' : 0 ≤ b
· by_cases h'' : b = 0
· simp [h'']
· simp only [h', ↓reduceIte, Int.sub_zero, h'']
replace h' : 0 < b := by omega
rw [sign_eq_one_of_pos (by omega)]
· simp only [h', ↓reduceIte]
rw [sign_eq_neg_one_of_neg (by omega), if_neg (by omega)]
omega
@[simp] protected theorem neg_fdiv_neg (a b : Int) : (-a).fdiv (-b) = a.fdiv b := by
match a, b with
| 0, 0 => rfl
| 0, ofNat b => simp
| 0, -[b+1] => simp
| ofNat (a + 1), 0 => simp
| ofNat (a + 1), ofNat (b + 1) =>
unfold fdiv
simp only [ofNat_eq_coe, Int.natCast_add, cast_ofNat_Int, Nat.succ_eq_add_one]
rw [← negSucc_eq, ← negSucc_eq]
| ofNat (a + 1), -[b+1] =>
unfold fdiv
simp only [ofNat_eq_coe, Int.natCast_add, cast_ofNat_Int, Nat.succ_eq_add_one]
rw [← negSucc_eq, neg_negSucc]
| -[a+1], 0 => simp
| -[a+1], ofNat (b + 1) =>
unfold fdiv
simp only [ofNat_eq_coe, Int.natCast_add, cast_ofNat_Int, Nat.succ_eq_add_one]
rw [neg_negSucc, ← negSucc_eq]
| -[a+1], -[b+1] =>
unfold fdiv
simp only [ofNat_eq_coe, ofNat_ediv, Nat.succ_eq_add_one, Int.natCast_add, cast_ofNat_Int]
rw [neg_negSucc, neg_negSucc]
simp
theorem fdiv_neg {a b : Int} (h : b ≠ 0) : a.fdiv (-b) = if b ∣ a then -(a.fdiv b) else -(a.fdiv b) - 1 := by
rw [← Int.neg_fdiv_neg, Int.neg_neg, neg_fdiv]
simp only [h, false_or]
split <;> omega
/-!
One could prove the following, but as the statements are quite awkward, so far it doesn't seem worthwhile.
```
theorem natAbs_fdiv {a b : Int} (h : b ≠ 0) :
natAbs (a.fdiv b) = a.natAbs / b.natAbs + if a.sign = b.sign ∨ b ∣ a then 0 else 1 := ...
theorem sign_fdiv (a b : Int) :
sign (a.fdiv b) = if a.sign = b.sign ∧ natAbs a < natAbs b then 0 else sign a * sign b := ...
```
-/
/-! ### fmod -/
-- `fmod` analogues of `emod` lemmas from `Bootstrap.lean`
theorem ofNat_fmod (m n : Nat) : ↑(m % n) = fmod m n := by
cases m <;> simp [fmod, Nat.succ_eq_add_one]
theorem fmod_nonneg {a b : Int} (ha : 0 ≤ a) (hb : 0 ≤ b) : 0 ≤ a.fmod b :=
fmod_eq_tmod_of_nonneg ha hb ▸ tmod_nonneg _ ha
theorem fmod_nonneg_of_pos (a : Int) {b : Int} (hb : 0 < b) : 0 ≤ a.fmod b :=
fmod_eq_emod_of_nonneg _ (Int.le_of_lt hb) ▸ emod_nonneg _ (Int.ne_of_lt hb).symm
@[deprecated fmod_nonneg_of_pos (since := "2025-03-04")]
abbrev fmod_nonneg' := @fmod_nonneg_of_pos
theorem fmod_lt_of_pos (a : Int) {b : Int} (H : 0 < b) : a.fmod b < b :=
fmod_eq_emod_of_nonneg _ (Int.le_of_lt H) ▸ emod_lt_of_pos a H
-- There is no `fmod_neg : ∀ {a b : Int}, a.fmod (-b) = -a.fmod b` as this is false.
@[simp] theorem add_mul_fmod_self_right (a b c : Int) : (a + b * c).fmod c = a.fmod c := by
rw [fmod_eq_emod, add_mul_emod_self_right, fmod_eq_emod]
simp
@[deprecated add_mul_fmod_self_right (since := "2025-04-11")]
theorem add_mul_fmod_self {a b c : Int} : (a + b * c).fmod c = a.fmod c :=
add_mul_fmod_self_right ..
@[simp] theorem add_mul_fmod_self_left (a b c : Int) : (a + b * c).fmod b = a.fmod b := by
rw [Int.mul_comm, Int.add_mul_fmod_self_right]
@[simp] theorem mul_add_fmod_self_right (a b c : Int) : (a * b + c).fmod b = c.fmod b := by
rw [Int.add_comm, add_mul_fmod_self_right]
@[simp] theorem mul_add_fmod_self_left (a b c : Int) : (a * b + c).fmod a = c.fmod a := by
rw [Int.add_comm, add_mul_fmod_self_left]
@[simp] theorem add_neg_mul_fmod_self_right (a b c : Int) : (a + -(b * c)).fmod c = a.fmod c := by
rw [Int.neg_mul_eq_neg_mul, add_mul_fmod_self_right]
@[simp] theorem add_neg_mul_fmod_self_left (a b c : Int) : (a + -(b * c)).fmod b = a.fmod b := by
rw [Int.neg_mul_eq_mul_neg, add_mul_fmod_self_left]
@[simp] theorem add_fmod_right (a b : Int) : (a + b).fmod b = a.fmod b := by
have := add_mul_fmod_self_left a b 1; rwa [Int.mul_one] at this
@[simp] theorem add_fmod_left (a b : Int) : (a + b).fmod a = b.fmod a := by
rw [Int.add_comm, add_fmod_right]
@[simp] theorem sub_mul_fmod_self_right (a b c : Int) : (a - b * c).fmod c = a.fmod c := by
simp [Int.sub_eq_add_neg]
@[simp] theorem sub_mul_fmod_self_left (a b c : Int) : (a - b * c).fmod b = a.fmod b := by
simp [Int.sub_eq_add_neg]
@[simp] theorem mul_sub_fmod_self_right (a b c : Int) : (a * b - c).fmod b = (-c).fmod b := by
simp [Int.sub_eq_add_neg]
@[simp] theorem mul_sub_fmod_self_left (a b c : Int) : (a * b - c).fmod a = (-c).fmod a := by
simp [Int.sub_eq_add_neg]
@[simp] theorem sub_fmod_right (a b : Int) : (a - b).fmod b = a.fmod b := by
have := sub_mul_fmod_self_left a b 1; rwa [Int.mul_one] at this
@[simp] theorem sub_fmod_left (a b : Int) : (a - b).fmod a = (-b).fmod a := by
simp [Int.sub_eq_add_neg]
@[simp] theorem fmod_add_fmod (m n k : Int) : (m.fmod n + k).fmod n = (m + k).fmod n := by
by_cases h : n = 0
· simp [h]
rw [fmod_def, fmod_def]
conv => rhs; rw [fmod_def]
have : m - n * m.fdiv n + k = m + k + n * (- m.fdiv n) := by simp [Int.mul_neg]; omega
rw [this, add_fdiv_of_dvd_right (Int.dvd_mul_right ..), Int.mul_add, mul_fdiv_cancel_left _ h]
omega
@[simp] theorem add_fmod_fmod (m n k : Int) : (m + n.fmod k).fmod k = (m + n).fmod k := by
rw [Int.add_comm, Int.fmod_add_fmod, Int.add_comm]
theorem add_fmod (a b n : Int) : (a + b).fmod n = (a.fmod n + b.fmod n).fmod n := by
simp
theorem add_fmod_eq_add_fmod_right {m n k : Int} (i : Int)
(H : m.fmod n = k.fmod n) : (m + i).fmod n = (k + i).fmod n := by
rw [add_fmod]
conv => rhs; rw [add_fmod]
rw [H]
theorem fmod_add_cancel_right {m n k : Int} (i) : (m + i).fmod n = (k + i).fmod n ↔ m.fmod n = k.fmod n :=
⟨fun H => by
have := add_fmod_eq_add_fmod_right (-i) H
rwa [Int.add_neg_cancel_right, Int.add_neg_cancel_right] at this,
add_fmod_eq_add_fmod_right _⟩
@[simp] theorem mul_fmod_left (a b : Int) : (a * b).fmod b = 0 :=
if h : b = 0 then by simp [h, Int.mul_zero] else by
rw [Int.fmod_def, Int.mul_fdiv_cancel _ h, Int.mul_comm, Int.sub_self]
@[simp] theorem mul_fmod_right (a b : Int) : (a * b).fmod a = 0 := by
rw [Int.mul_comm, mul_fmod_left]
theorem mul_fmod (a b n : Int) : (a * b).fmod n = (a.fmod n * b.fmod n).fmod n := by
conv => lhs; rw [
← fmod_add_fdiv a n, ← fmod_add_fdiv' b n, Int.add_mul, Int.mul_add, Int.mul_add,
Int.mul_assoc, Int.mul_assoc, ← Int.mul_add n _ _, add_mul_fmod_self_left,
← Int.mul_assoc, add_mul_fmod_self_right]
@[simp] theorem fmod_self {a : Int} : a.fmod a = 0 := by
have := mul_fmod_left 1 a; rwa [Int.one_mul] at this
@[simp] theorem fmod_fmod_of_dvd (n : Int) {m k : Int}
(h : m ∣ k) : (n.fmod k).fmod m = n.fmod m := by
conv => rhs; rw [← fmod_add_fdiv n k]
match k, h with
| _, ⟨t, rfl⟩ => rw [Int.mul_assoc, add_mul_fmod_self_left]
@[simp] theorem fmod_fmod (a b : Int) : (a.fmod b).fmod b = a.fmod b :=
fmod_fmod_of_dvd _ (Int.dvd_refl b)
theorem sub_fmod (a b n : Int) : (a - b).fmod n = (a.fmod n - b.fmod n).fmod n := by
apply (fmod_add_cancel_right b).mp
rw [Int.sub_add_cancel, ← Int.add_fmod_fmod, Int.sub_add_cancel, fmod_fmod]
theorem fmod_eq_zero_of_dvd : ∀ {a b : Int}, a ∣ b → b.fmod a = 0
| _, _, ⟨_, rfl⟩ => mul_fmod_right ..
-- `fmod` analogues of `emod` lemmas from above
theorem fmod_eq_of_lt {a b : Int} (H1 : 0 ≤ a) (H2 : a < b) : a.fmod b = a := by
rw [fmod_eq_emod_of_nonneg _ (Int.le_trans H1 (Int.le_of_lt H2)), emod_eq_of_lt H1 H2]
@[simp] protected theorem neg_fmod_neg (a b : Int) : (-a).fmod (-b) = -a.fmod b := by
rw [fmod_def, Int.neg_fdiv_neg, fmod_def, Int.neg_mul]
omega
-- Are `sign_fmod`, `natAbs_fmod` useful?
/-! ### properties of `fdiv` and `fmod` -/
-- Analogues of properties of `ediv` and `emod` from `Bootstrap.lean`
theorem mul_fdiv_cancel_of_fmod_eq_zero {a b : Int} (H : a.fmod b = 0) : b * (a.fdiv b) = a := by
have := fmod_add_fdiv a b; rwa [H, Int.zero_add] at this
theorem fdiv_mul_cancel_of_fmod_eq_zero {a b : Int} (H : a.fmod b = 0) : (a.fdiv b) * b= a := by
rw [Int.mul_comm, mul_fdiv_cancel_of_fmod_eq_zero H]
theorem dvd_of_fmod_eq_zero {a b : Int} (H : b.fmod a = 0) : a ∣ b :=
⟨b.fdiv a, (mul_fdiv_cancel_of_fmod_eq_zero H).symm⟩
theorem dvd_iff_fmod_eq_zero {a b : Int} : a ∣ b ↔ b.fmod a = 0 :=
⟨fmod_eq_zero_of_dvd, dvd_of_fmod_eq_zero⟩
protected theorem fdiv_mul_cancel {a b : Int} (H : b ∣ a) : a.fdiv b * b = a :=
fdiv_mul_cancel_of_fmod_eq_zero (fmod_eq_zero_of_dvd H)
protected theorem mul_fdiv_cancel' {a b : Int} (H : a ∣ b) : a * b.fdiv a = b := by
rw [Int.mul_comm, Int.fdiv_mul_cancel H]
protected theorem eq_mul_of_fdiv_eq_right {a b c : Int}
(H1 : b ∣ a) (H2 : a.fdiv b = c) : a = b * c := by rw [← H2, Int.mul_fdiv_cancel' H1]
@[simp] theorem neg_fmod_self (a : Int) : (-a).fmod a = 0 := by
rw [← dvd_iff_fmod_eq_zero, Int.dvd_neg]
exact Int.dvd_refl a
theorem lt_fdiv_add_one_mul_self (a : Int) {b : Int} (H : 0 < b) : a < (a.fdiv b + 1) * b := by
rw [Int.add_mul, Int.one_mul, Int.mul_comm]
exact Int.lt_add_of_sub_left_lt <| Int.fmod_def .. ▸ fmod_lt_of_pos _ H
protected theorem fdiv_eq_iff_eq_mul_right {a b c : Int}
(H : b ≠ 0) (H' : b ∣ a) : a.fdiv b = c ↔ a = b * c :=
⟨Int.eq_mul_of_fdiv_eq_right H', Int.fdiv_eq_of_eq_mul_right H⟩
protected theorem fdiv_eq_iff_eq_mul_left {a b c : Int}
(H : b ≠ 0) (H' : b ∣ a) : a.fdiv b = c ↔ a = c * b := by
rw [Int.mul_comm]; exact Int.fdiv_eq_iff_eq_mul_right H H'
protected theorem eq_mul_of_fdiv_eq_left {a b c : Int}
(H1 : b ∣ a) (H2 : a.fdiv b = c) : a = c * b := by
rw [Int.mul_comm, Int.eq_mul_of_fdiv_eq_right H1 H2]
protected theorem eq_zero_of_fdiv_eq_zero {d n : Int} (h : d ∣ n) (H : n.fdiv d = 0) : n = 0 := by
rw [← Int.mul_fdiv_cancel' h, H, Int.mul_zero]
@[simp] protected theorem fdiv_left_inj {a b d : Int}
(hda : d ∣ a) (hdb : d ∣ b) : a.fdiv d = b.fdiv d ↔ a = b := by
refine ⟨fun h => ?_, congrArg (fdiv · d)⟩
rw [← Int.mul_fdiv_cancel' hda, ← Int.mul_fdiv_cancel' hdb, h]
protected theorem mul_fdiv_assoc (a : Int) : ∀ {b c : Int}, c ∣ b → (a * b).fdiv c = a * (b.fdiv c)
| _, c, ⟨d, rfl⟩ =>
if cz : c = 0 then by simp [cz, Int.mul_zero] else by
rw [Int.mul_left_comm, Int.mul_fdiv_cancel_left _ cz, Int.mul_fdiv_cancel_left _ cz]
protected theorem mul_fdiv_assoc' (b : Int) {a c : Int} (h : c ∣ a) :
(a * b).fdiv c = a.fdiv c * b := by
rw [Int.mul_comm, Int.mul_fdiv_assoc _ h, Int.mul_comm]
theorem neg_fdiv_of_dvd : ∀ {a b : Int}, b ∣ a → (-a).fdiv b = -(a.fdiv b)
| _, b, ⟨c, rfl⟩ => by
by_cases bz : b = 0
· simp [bz]
· rw [Int.neg_mul_eq_mul_neg, Int.mul_fdiv_cancel_left _ bz, Int.mul_fdiv_cancel_left _ bz]
theorem sub_fdiv_of_dvd (a : Int) {b c : Int}
(hcb : c ∣ b) : (a - b).fdiv c = a.fdiv c - b.fdiv c := by
rw [Int.sub_eq_add_neg, Int.sub_eq_add_neg, Int.add_fdiv_of_dvd_right (Int.dvd_neg.2 hcb)]
congr; exact Int.neg_fdiv_of_dvd hcb
theorem fdiv_dvd_fdiv : ∀ {a b c : Int}, a ∣ b → b ∣ c → b.fdiv a ∣ c.fdiv a
| a, _, _, ⟨b, rfl⟩, ⟨c, rfl⟩ => by
by_cases az : a = 0
· simp [az]
· rw [Int.mul_fdiv_cancel_left _ az, Int.mul_assoc, Int.mul_fdiv_cancel_left _ az]
apply Int.dvd_mul_right
-- Analogues of properties about `ediv` and `emod` from above.
theorem mul_fdiv_cancel_of_dvd {a b : Int} (H : b ∣ a) : b * (a.fdiv b) = a :=
mul_fdiv_cancel_of_fmod_eq_zero (fmod_eq_zero_of_dvd H)
theorem fdiv_mul_cancel_of_dvd {a b : Int} (H : b ∣ a) : a.fdiv b * b = a :=
fdiv_mul_cancel_of_fmod_eq_zero (fmod_eq_zero_of_dvd H)
theorem fmod_two_eq (x : Int) : x.fmod 2 = 0 ∨ x.fmod 2 = 1 := by
have h₁ : 0 ≤ x.fmod 2 := Int.fmod_nonneg_of_pos _ (by decide)
have h₂ : x.fmod 2 < 2 := Int.fmod_lt_of_pos x (by decide)
match x.fmod 2, h₁, h₂ with
| 0, _, _ => simp
| 1, _, _ => simp
theorem add_fmod_eq_add_fmod_left {m n k : Int} (i : Int)
(H : m.fmod n = k.fmod n) : (i + m).fmod n = (i + k).fmod n := by
rw [Int.add_comm, add_fmod_eq_add_fmod_right _ H, Int.add_comm]
theorem fmod_add_cancel_left {m n k i : Int} : (i + m).fmod n = (i + k).fmod n ↔ m.fmod n = k.fmod n := by
rw [Int.add_comm, Int.add_comm i, fmod_add_cancel_right]
theorem fmod_sub_cancel_right {m n k : Int} (i) : (m - i).fmod n = (k - i).fmod n ↔ m.fmod n = k.fmod n :=
fmod_add_cancel_right _
theorem fmod_eq_fmod_iff_fmod_sub_eq_zero {m n k : Int} : m.fmod n = k.fmod n ↔ (m - k).fmod n = 0 :=
(fmod_sub_cancel_right k).symm.trans <| by simp [Int.sub_self]
theorem fmod_sub_cancel_left {m n k : Int} (i) : (i - m).fmod n = (i - k).fmod n ↔ m.fmod n = k.fmod n := by
simp only [fmod_eq_fmod_iff_fmod_sub_eq_zero, ← dvd_iff_fmod_eq_zero,
(by omega : i - m - (i - k) = -(m - k)), Int.dvd_neg]
protected theorem fdiv_fmod_unique {a b r q : Int} (h : 0 < b) :
a.fdiv b = q ∧ a.fmod b = r ↔ r + b * q = a ∧ 0 ≤ r ∧ r < b := by
rw [fdiv_eq_ediv_of_nonneg, fmod_eq_emod_of_nonneg, Int.ediv_emod_unique]
all_goals omega
protected theorem fdiv_fmod_unique' {a b r q : Int} (h : b < 0) :
a.fdiv b = q ∧ a.fmod b = r ↔ r + b * q = a ∧ b < r ∧ r ≤ 0 := by
have := Int.fdiv_fmod_unique (a := -a) (b := -b) (r := -r) (q := q) (by omega)
simp at this
simp [this, Int.neg_mul]
omega
@[simp] theorem mul_fmod_mul_of_pos
{a : Int} (b c : Int) (H : 0 < a) : (a * b).fmod (a * c) = a * (b.fmod c) := by
rw [fmod_def, fmod_def, mul_fdiv_mul_of_pos _ _ H, Int.mul_sub, Int.mul_assoc]
theorem natAbs_fdiv_le_natAbs (a b : Int) : natAbs (a.fdiv b) ≤ natAbs a := by
rw [fdiv_eq_ediv]
split
· simp [natAbs_ediv_le_natAbs]
· rename_i h
simp at h
match a, b, h with
| 0, .negSucc b, h => simp at h
| .ofNat (a + 1), .negSucc 0, h => simp at h
| .ofNat (a + 1), .negSucc (b + 1), h =>
rw [negSucc_eq, ofNat_eq_coe]
norm_cast
rw [Int.ediv_neg, Int.sub_eq_add_neg, ← Int.neg_add, natAbs_neg]
norm_cast
apply Nat.div_lt_self
omega
omega
| .negSucc a, .negSucc b, h =>
simp [negSucc_eq]
norm_cast
rw [Int.neg_ediv, if_neg (by simpa using h.2)]
norm_cast
rw [sign_eq_one_of_pos (by omega), Int.sub_eq_add_neg, ← Int.neg_add, natAbs_neg,
Int.sub_add_cancel, natAbs_neg, natAbs_natCast]
apply Nat.div_le_self
theorem fdiv_le_self {a : Int} (b : Int) (Ha : 0 ≤ a) : a.fdiv b ≤ a := by
have := Int.le_trans le_natAbs (ofNat_le.2 <| natAbs_fdiv_le_natAbs a b)
rwa [natAbs_of_nonneg Ha] at this
theorem dvd_fmod_sub_self {x m : Int} : m ∣ x.fmod m - x := by
rw [fmod_eq_emod]
have := dvd_emod_sub_self (x := x) (m := m)
split
· simpa
· have w : x % ↑m + ↑m - x = x % ↑m - x + ↑m := by omega
rw [w]
apply Int.dvd_add this (Int.dvd_refl ↑m)
theorem dvd_self_sub_fmod {x m : Int} : m ∣ x - x.fmod m :=
Int.dvd_neg.1 (by simpa only [Int.neg_sub] using dvd_fmod_sub_self)
theorem dvd_self_sub_of_fmod_eq {a b c : Int} (h : a.fmod b = c) :
(b : Int) ∣ a - c :=
h ▸ dvd_self_sub_fmod
theorem dvd_sub_self_of_fmod_eq {a b c : Int} (h : a.fmod b = c) :
(b : Int) ∣ c - a :=
h ▸ dvd_fmod_sub_self
@[simp] theorem neg_mul_fmod_right (a b : Int) : (-(a * b)).fmod a = 0 := by
rw [← dvd_iff_fmod_eq_zero, Int.dvd_neg]
exact Int.dvd_mul_right a b
@[simp] theorem neg_mul_fmod_left (a b : Int) : (-(a * b)).fmod b = 0 := by
rw [← dvd_iff_fmod_eq_zero, Int.dvd_neg]
exact Int.dvd_mul_left a b
@[simp] theorem fmod_one (a : Int) : a.fmod 1 = 0 := by
simp [fmod_def, Int.one_mul, Int.sub_self]
@[deprecated sub_fmod_right (since := "2025-04-12")]
theorem fmod_sub_cancel (x y : Int) : (x - y).fmod y = x.fmod y :=
sub_fmod_right _ _
@[simp] theorem add_neg_fmod_self (a b : Int) : (a + -b).fmod b = a.fmod b := by
rw [Int.add_neg_eq_sub, sub_fmod_right]
@[simp] theorem neg_add_fmod_self (a b : Int) : (-a + b).fmod a = b.fmod a := by
rw [Int.add_comm, add_neg_fmod_self]
@[deprecated dvd_self_sub_of_fmod_eq (since := "2025-04-12")]
theorem dvd_sub_of_fmod_eq {a b c : Int} (h : a.fmod b = c) : b ∣ a - c :=
dvd_self_sub_of_fmod_eq h
theorem fdiv_sign {a b : Int} : a.fdiv (sign b) = a * sign b := by
rw [fdiv_eq_ediv]
rcases sign_trichotomy b with h | h | h <;> simp [h]
protected theorem sign_eq_fdiv_abs (a : Int) : sign a = a.fdiv (natAbs a) :=
if az : a = 0 then by simp [az] else
(Int.fdiv_eq_of_eq_mul_left (ofNat_ne_zero.2 <| natAbs_ne_zero.2 az)
(sign_mul_natAbs _).symm).symm
/-! ### `fdiv` and ordering -/
-- Theorems about `fdiv` and ordering, whose `ediv` analogues are in `Bootstrap.lean`.
theorem mul_fdiv_self_le {x k : Int} (h : 0 < k) : k * (x.fdiv k) ≤ x := by
rw [fdiv_eq_ediv]
have := mul_ediv_self_le (x := x) (k := k)
split <;> simp <;> omega
theorem lt_mul_fdiv_self_add {x k : Int} (h : 0 < k) : x < k * (x.fdiv k) + k := by
rw [fdiv_eq_ediv]
have := lt_mul_ediv_self_add (x := x) h
split <;> simp <;> omega
-- We do not currently prove the theorems about `fdiv` and ordering,
-- whose `ediv` analogues are proved above.
/-! ### bmod -/
@[simp]
theorem emod_bmod (x : Int) (n : Nat) : Int.bmod (x%n) n = Int.bmod x n := by
simp [bmod, Int.emod_emod]
@[deprecated emod_bmod (since := "2025-04-11")]
theorem emod_bmod_congr (x : Int) (n : Nat) : Int.bmod (x%n) n = Int.bmod x n :=
emod_bmod ..
theorem bdiv_add_bmod (x : Int) (m : Nat) : m * bdiv x m + bmod x m = x := by
unfold bdiv bmod
split
· simp_all only [cast_ofNat_Int, Int.mul_zero, emod_zero, Int.zero_add, Int.sub_zero,
ite_self]
· dsimp only
split
· exact ediv_add_emod x m
· rw [Int.mul_add, Int.mul_one, Int.add_assoc, Int.add_comm m, Int.sub_add_cancel]
exact ediv_add_emod x m
theorem bmod_add_bdiv (x : Int) (m : Nat) : bmod x m + m * bdiv x m = x := by
rw [Int.add_comm]; exact bdiv_add_bmod x m
theorem bdiv_add_bmod' (x : Int) (m : Nat) : bdiv x m * m + bmod x m = x := by
rw [Int.mul_comm]; exact bdiv_add_bmod x m
theorem bmod_add_bdiv' (x : Int) (m : Nat) : bmod x m + bdiv x m * m = x := by
rw [Int.add_comm]; exact bdiv_add_bmod' x m
theorem bmod_eq_self_sub_mul_bdiv (x : Int) (m : Nat) : bmod x m = x - m * bdiv x m := by
rw [← Int.add_sub_cancel (bmod x m), bmod_add_bdiv]
theorem bmod_eq_self_sub_bdiv_mul (x : Int) (m : Nat) : bmod x m = x - bdiv x m * m := by
rw [← Int.add_sub_cancel (bmod x m), bmod_add_bdiv']
theorem bmod_pos (x : Int) (m : Nat) (p : x % m < (m + 1) / 2) : bmod x m = x % m := by
simp [bmod_def, p]
theorem bmod_neg (x : Int) (m : Nat) (p : x % m ≥ (m + 1) / 2) : bmod x m = (x % m) - m := by
simp [bmod_def, Int.not_lt.mpr p]
theorem bmod_eq_emod (x : Int) (m : Nat) : bmod x m = x % m - if x % m ≥ (m + 1) / 2 then m else 0 := by
split
· rwa [bmod_neg]
· rw [bmod_pos] <;> simp_all
@[simp]
theorem bmod_one (x : Int) : Int.bmod x 1 = 0 := by
simp [Int.bmod]
@[deprecated bmod_one (since := "2025-04-10")]
abbrev bmod_one_is_zero := @bmod_one
@[simp] theorem add_bmod_right (a : Int) (b : Nat) : (a + b).bmod b = a.bmod b := by
simp [bmod_def]
@[simp] theorem add_bmod_left (a : Nat) (b : Int) : (a + b).bmod a = b.bmod a := by
simp [bmod_def]
@[simp] theorem add_mul_bmod_self_right (a b : Int) (c : Nat) : (a + b * c).bmod c = a.bmod c := by
simp [bmod_def]
@[simp] theorem add_mul_bmod_self_left (a : Int) (b : Nat) (c : Int) : (a + b * c).bmod b = a.bmod b := by
simp [bmod_def]
@[simp] theorem mul_add_bmod_self_right (a : Int) (b : Nat) (c : Int) : (a * b + c).bmod b = c.bmod b := by
simp [bmod_def]
@[simp] theorem mul_add_bmod_self_left (a : Nat) (b c : Int) : (a * b + c).bmod a = c.bmod a := by
simp [bmod_def]
@[simp] theorem sub_bmod_right (a : Int) (b : Nat) : (a - b).bmod b = a.bmod b := by
simp [bmod_def]
@[simp] theorem sub_bmod_left (a : Nat) (b : Int) : (a - b).bmod a = (-b).bmod a := by
simp [bmod_def]
@[simp] theorem sub_mul_bmod_self_right (a b : Int) (c : Nat) : (a - b * c).bmod c = a.bmod c := by
simp [bmod_def]
@[simp] theorem sub_mul_bmod_self_left (a : Int) (b : Nat) (c : Int) : (a - b * c).bmod b = a.bmod b := by
simp [bmod_def]
@[simp] theorem mul_sub_bmod_self_right (a : Int) (b : Nat) (c : Int) : (a * b - c).bmod b = (-c).bmod b := by
simp [bmod_def]
@[simp] theorem mul_sub_bmod_self_left (a : Nat) (b c : Int) : (a * b - c).bmod a = (-c).bmod a := by
simp [bmod_def]
@[simp] theorem add_neg_mul_bmod_self_right (a b : Int) (c : Nat) : (a + -(b * c)).bmod c = a.bmod c := by
simp [bmod_def]
@[simp] theorem add_neg_mul_bmod_self_left (a : Int) (b : Nat) (c : Int) : (a + -(b * c)).bmod b = a.bmod b := by
simp [bmod_def]
@[deprecated add_bmod_right (since := "2025-04-10")]
theorem bmod_add_cancel {x : Int} {n : Nat} : Int.bmod (x + n) n = Int.bmod x n :=
add_bmod_right ..
@[deprecated add_mul_bmod_self_left (since := "2025-04-10")]
theorem bmod_add_mul_cancel (x : Int) (n : Nat) (k : Int) : Int.bmod (x + n * k) n = Int.bmod x n :=
add_mul_bmod_self_left ..
@[deprecated sub_bmod_right (since := "2025-04-10")]
theorem bmod_sub_cancel (x : Int) (n : Nat) : Int.bmod (x - n) n = Int.bmod x n :=
sub_bmod_right ..
@[deprecated sub_mul_bmod_self_left (since := "2025-04-10")]
theorem Int.bmod_sub_mul_cancel (x : Int) (n : Nat) (k : Int) : (x - n * k).bmod n = x.bmod n :=
sub_mul_bmod_self_left ..
@[simp]
theorem emod_add_bmod (x : Int) (n : Nat) : Int.bmod (x % n + y) n = Int.bmod (x + y) n := by
simp [Int.emod_def, Int.sub_eq_add_neg]
rw [←Int.mul_neg, Int.add_right_comm, Int.add_mul_bmod_self_left]
@[deprecated emod_add_bmod (since := "2025-04-11")]
theorem emod_add_bmod_congr (x : Int) (n : Nat) : Int.bmod (x % n + y) n = Int.bmod (x + y) n :=
emod_add_bmod ..
@[simp]
theorem emod_sub_bmod (x : Int) (n : Nat) : Int.bmod (x % n - y) n = Int.bmod (x - y) n := by
simp only [emod_def, Int.sub_eq_add_neg]
rw [←Int.mul_neg, Int.add_right_comm, Int.add_mul_bmod_self_left]
@[deprecated emod_sub_bmod (since := "2025-04-11")]
theorem emod_sub_bmod_congr (x : Int) (n : Nat) : Int.bmod (x % n - y) n = Int.bmod (x - y) n :=
emod_sub_bmod ..
@[simp]
theorem sub_emod_bmod (x : Int) (n : Nat) : Int.bmod (x - y % n) n = Int.bmod (x - y) n := by
simp only [emod_def]
rw [Int.sub_eq_add_neg, Int.neg_sub, Int.sub_eq_add_neg, ← Int.add_assoc, Int.add_right_comm,
Int.add_mul_bmod_self_left, Int.sub_eq_add_neg]
@[deprecated sub_emod_bmod (since := "2025-04-11")]
theorem sub_emod_bmod_congr (x : Int) (n : Nat) : Int.bmod (x - y % n) n = Int.bmod (x - y) n :=
sub_emod_bmod ..
@[simp]
theorem emod_mul_bmod (x : Int) (n : Nat) : Int.bmod (x % n * y) n = Int.bmod (x * y) n := by
simp [Int.emod_def, Int.sub_eq_add_neg]
rw [←Int.mul_neg, Int.add_mul, Int.mul_assoc, Int.add_mul_bmod_self_left]
@[deprecated emod_mul_bmod (since := "2025-04-11")]
theorem emod_mul_bmod_congr (x : Int) (n : Nat) : Int.bmod (x % n * y) n = Int.bmod (x * y) n :=
emod_mul_bmod ..
@[simp]
theorem bmod_add_bmod : Int.bmod (Int.bmod x n + y) n = Int.bmod (x + y) n := by
have := (@add_mul_bmod_self_left (Int.bmod x n + y) n (bdiv x n)).symm
rwa [Int.add_right_comm, bmod_add_bdiv] at this
@[deprecated bmod_add_bmod (since := "2025-04-11")]
theorem bmod_add_bmod_congr : Int.bmod (Int.bmod x n + y) n = Int.bmod (x + y) n :=
bmod_add_bmod ..
@[simp]
theorem bmod_sub_bmod : Int.bmod (Int.bmod x n - y) n = Int.bmod (x - y) n :=
@bmod_add_bmod x n (-y)
@[deprecated bmod_sub_bmod (since := "2025-04-11")]
theorem bmod_sub_bmod_congr : Int.bmod (Int.bmod x n - y) n = Int.bmod (x - y) n :=
bmod_sub_bmod ..
theorem add_bmod_eq_add_bmod_right (i : Int)
(H : bmod x n = bmod y n) : bmod (x + i) n = bmod (y + i) n := by
rw [← bmod_add_bmod, ← @bmod_add_bmod y, H]
theorem bmod_add_cancel_right (i : Int) : bmod (x + i) n = bmod (y + i) n ↔ bmod x n = bmod y n :=
⟨fun H => by
have := add_bmod_eq_add_bmod_right (-i) H
rwa [Int.add_neg_cancel_right, Int.add_neg_cancel_right] at this,
fun H => by rw [← bmod_add_bmod, H, bmod_add_bmod]⟩
theorem bmod_add_cancel_left (i : Int) : bmod (i + x) n = bmod (i + y) n ↔ bmod x n = bmod y n := by
rw [Int.add_comm i, Int.add_comm i, bmod_add_cancel_right]
theorem add_bmod_eq_add_bmod_left (i : Int) (h : bmod x n = bmod y n) :
bmod (i + x) n = bmod (i + y) n := by
simpa [bmod_add_cancel_left]
@[simp] theorem add_bmod_bmod : Int.bmod (x + Int.bmod y n) n = Int.bmod (x + y) n := by
rw [Int.add_comm x, Int.bmod_add_bmod, Int.add_comm y]
@[simp] theorem sub_bmod_bmod : Int.bmod (x - Int.bmod y n) n = Int.bmod (x - y) n := by
apply (bmod_add_cancel_right (bmod y n)).mp
rw [Int.sub_add_cancel, add_bmod_bmod, Int.sub_add_cancel]
@[simp]
theorem bmod_mul_bmod : Int.bmod (Int.bmod x n * y) n = Int.bmod (x * y) n := by
rw [bmod_def x n]
split
next p =>
simp
next p =>
rw [Int.sub_mul, Int.sub_eq_add_neg, ← Int.mul_neg, add_mul_bmod_self_left, emod_mul_bmod]
@[simp] theorem mul_bmod_bmod : Int.bmod (x * Int.bmod y n) n = Int.bmod (x * y) n := by
rw [Int.mul_comm x, bmod_mul_bmod, Int.mul_comm x]
@[simp] theorem add_emod_bmod (x : Int) (n : Nat) : (y + x % n).bmod n = (y + x).bmod n := by
rw [Int.add_comm, emod_add_bmod, Int.add_comm]
@[simp] theorem mul_emod_bmod (x : Int) (n : Nat) : (y * (x % n)).bmod n = (y * x).bmod n := by
rw [Int.mul_comm, emod_mul_bmod, Int.mul_comm]
@[simp] theorem mul_bmod_left (a : Int) (b : Nat) : (a * b).bmod b = 0 := by
simp [bmod_def]; omega
@[simp] theorem mul_bmod_right (a : Nat) (b : Int) : (a * b).bmod a = 0 := by
simp [bmod_def]; omega
theorem mul_bmod (a b : Int) (n : Nat) : (a * b).bmod n = (a.bmod n * b.bmod n).bmod n := by
simp
theorem add_bmod (a b : Int) (n : Nat) : (a + b).bmod n = (a.bmod n + b.bmod n).bmod n := by
simp
theorem sub_bmod (a b : Int) (n : Nat) : (a - b).bmod n = (a.bmod n - b.bmod n).bmod n := by
simp
@[simp] theorem bmod_bmod : bmod (bmod x m) m = bmod x m := by
rw [bmod, bmod_emod, bmod]
@[simp] theorem zero_bmod : Int.bmod 0 m = 0 := by
simp [bmod_def]; omega
@[simp] theorem bmod_zero : Int.bmod m 0 = m := by
simp [bmod_def]
@[simp] theorem bmod_self {a : Nat} : Int.bmod a a = 0 := by
simp [bmod_def]; omega
@[simp] theorem neg_bmod_self {a : Nat} : Int.bmod (-a) a = 0 := by
simp [← Int.zero_sub]
theorem dvd_bmod_sub_self {x : Int} {m : Nat} : (m : Int) ∣ bmod x m - x := by
dsimp [bmod]
split
· exact dvd_emod_sub_self
· rw [Int.sub_sub, Int.add_comm, ← Int.sub_sub]
exact Int.dvd_sub dvd_emod_sub_self (Int.dvd_refl _)
theorem dvd_self_sub_bmod {x : Int} {m : Nat} : (m : Int) ∣ x - bmod x m :=
Int.dvd_neg.1 (by simpa only [Int.neg_sub] using dvd_bmod_sub_self)
theorem dvd_of_bmod_eq_zero {a : Nat} {b : Int} (h : b.bmod a = 0) : (a : Int) ∣ b := by
simpa [h] using dvd_bmod_sub_self (x := b) (m := a)
theorem bmod_eq_zero_of_dvd : {a : Nat} → {b : Int} → (h : (a : Int) ∣ b) → b.bmod a = 0
| _, _, ⟨_, rfl⟩ => by simp
theorem dvd_iff_bmod_eq_zero {a : Nat} {b : Int} : (a : Int) ∣ b ↔ b.bmod a = 0 :=
⟨bmod_eq_zero_of_dvd, dvd_of_bmod_eq_zero⟩
theorem le_bmod {x : Int} {m : Nat} (h : 0 < m) : - (m/2) ≤ Int.bmod x m := by
dsimp [bmod]
have v : (m : Int) % 2 = 0 ∨ (m : Int) % 2 = 1 := emod_two_eq _
split <;> rename_i w
· refine Int.le_trans ?_ (Int.emod_nonneg _ ?_)
· exact Int.neg_nonpos_of_nonneg (Int.ediv_nonneg (Int.ofNat_nonneg _) (by decide))
· exact Int.ne_of_gt (ofNat_pos.mpr h)
· simp [Int.not_lt] at w
refine Int.le_trans ?_ (Int.sub_le_sub_right w _)
rw [← ediv_add_emod m 2]
generalize (m : Int) / 2 = q
generalize h : (m : Int) % 2 = r at *
rcases v with rfl | rfl
· rw [Int.add_zero, Int.mul_ediv_cancel_left, Int.add_ediv_of_dvd_left,
Int.mul_ediv_cancel_left, show (1 / 2 : Int) = 0 by decide, Int.add_zero,
Int.neg_eq_neg_one_mul]
conv => rhs; congr; rw [← Int.one_mul q]
rw [← Int.sub_mul, show (1 - 2 : Int) = -1 by decide]
apply Int.le_refl
all_goals try decide
all_goals apply Int.dvd_mul_right
· rw [Int.add_ediv_of_dvd_left, Int.mul_ediv_cancel_left,
show (1 / 2 : Int) = 0 by decide, Int.add_assoc, Int.add_ediv_of_dvd_left,
Int.mul_ediv_cancel_left, show ((1 + 1) / 2 : Int) = 1 by decide, ← Int.sub_sub,
Int.sub_eq_add_neg, Int.sub_eq_add_neg, Int.add_right_comm, Int.add_assoc q,
show (1 + -1 : Int) = 0 by decide, Int.add_zero, ← Int.neg_mul]
rw [Int.neg_eq_neg_one_mul]
conv => rhs; congr; rw [← Int.one_mul q]
rw [← Int.add_mul, show (1 + -2 : Int) = -1 by decide]
apply Int.le_refl
all_goals try decide
all_goals try apply Int.dvd_mul_right
theorem bmod_lt {x : Int} {m : Nat} (h : 0 < m) : bmod x m < (m + 1) / 2 := by
dsimp [bmod]
split
· assumption
· apply Int.lt_of_lt_of_le
· show _ < 0
have : x % m < m := emod_lt_of_pos x (ofNat_pos.mpr h)
exact Int.sub_neg_of_lt this
· exact Int.le.intro_sub _ rfl
theorem bmod_eq_iff {a : Int} {b : Nat} {c : Int} (hb : 0 < b) :
a.bmod b = c ↔ -(b / 2) ≤ c ∧ c < (b + 1) / 2 ∧ (b : Int) ∣ (c - a) := by
refine ⟨?_, ?_⟩
· rintro rfl
exact ⟨le_bmod hb, bmod_lt hb, dvd_bmod_sub_self⟩
· rintro ⟨h₁, h₂, h₃⟩
rw [← Int.sub_eq_zero]
have := dvd_bmod_sub_self (x := a) (m := b)
have hdvd := Int.dvd_sub this h₃
rw [(by omega : a.bmod b - a - (c - a) = a.bmod b - c)] at hdvd
apply eq_zero_of_dvd_of_natAbs_lt_natAbs hdvd
have := le_bmod (x := a) (m := b) hb
have := bmod_lt (x := a) (m := b) hb
omega
theorem bmod_eq_emod_of_lt {x : Int} {m : Nat} (hx : x % m < (m + 1) / 2) : bmod x m = x % m := by
simp [bmod, hx]
theorem bmod_eq_neg {n : Nat} {m : Int} (hm : 0 ≤ m) (hn : n = 2 * m) : m.bmod n = -m := by
by_cases h : m = 0
· subst h; simp
· rw [Int.bmod_def, hn, if_neg]
· rw [Int.emod_eq_of_lt hm] <;> omega
· simp only [Int.not_lt]
rw [Int.emod_eq_of_lt hm] <;> omega
theorem bmod_le {x : Int} {m : Nat} (h : 0 < m) : bmod x m ≤ (m - 1) / 2 := by
refine lt_add_one_iff.mp ?_
calc
bmod x m < (m + 1) / 2 := bmod_lt h
_ = ((m + 1 - 2) + 2)/2 := by simp
_ = (m - 1) / 2 + 1 := by
rw [add_ediv_of_dvd_right]
· simp +decide only [Int.ediv_self]
congr 2
rw [Int.add_sub_assoc, ← Int.sub_neg]
congr
· trivial
theorem bmod_natAbs_add_one (x : Int) (w : x ≠ -1) : x.bmod (x.natAbs + 1) = -x.sign := by
rw [bmod_eq_iff (by omega)]
obtain (hx|rfl|hx) := Int.lt_trichotomy x 0
· rw [sign_eq_neg_one_iff_neg.2 hx]
exact ⟨by omega, by omega, ⟨1, by omega⟩⟩
· simp
· rw [sign_eq_one_iff_pos.2 hx]
exact ⟨by omega, by omega, ⟨-1, by omega⟩⟩
@[deprecated bmod_natAbs_add_one (since := "2025-04-04")]
abbrev bmod_natAbs_plus_one := @bmod_natAbs_add_one
theorem bmod_self_add_one {x : Nat} : (x : Int).bmod (x + 1) = if x = 0 then 0 else -1 := by
have := bmod_natAbs_add_one x (by omega)
simp only [natAbs_natCast] at this
rw [this]
split <;> simp_all <;> omega
theorem one_bmod_two : Int.bmod 1 2 = -1 := by simp
theorem one_bmod {b : Nat} (h : 3 ≤ b) : Int.bmod 1 b = 1 := by
have hb : 1 % (b : Int) = 1 := by rw [one_emod]; omega
rw [bmod_pos _ _ (by omega), hb]
theorem bmod_two_eq (x : Int) : x.bmod 2 = -1 ∨ x.bmod 2 = 0 := by
have := le_bmod (x := x) (m := 2) (by omega)
have := bmod_lt (x := x) (m := 2) (by omega)
omega
theorem bmod_sub_cancel_right (i : Int) : bmod (x - i) n = bmod (y - i) n ↔ bmod x n = bmod y n := by
simp only [Int.sub_eq_add_neg, bmod_add_cancel_right]
theorem bmod_eq_bmod_iff_bmod_sub_eq_zero {m : Int} {n : Nat} {k : Int} : m.bmod n = k.bmod n ↔ (m - k).bmod n = 0 :=
(bmod_sub_cancel_right k).symm.trans <| by simp [Int.sub_self]
theorem bmod_sub_cancel_left (i : Int) : bmod (i - x) n = bmod (i - y) n ↔ bmod x n = bmod y n := by
simp only [bmod_eq_bmod_iff_bmod_sub_eq_zero, ← dvd_iff_bmod_eq_zero,
(by omega : i - x - (i - y) = -(x - y)), Int.dvd_neg]
theorem mod_bmod_mul_of_pos {a : Nat} (b : Int) (c : Nat) (h : 0 < a) (hce : 2 ∣ c) :
(a * b).bmod (a * c) = a * (b.bmod c) := by
refine (Nat.eq_zero_or_pos c).elim (by rintro rfl; simp) (fun hc => ?_)
rw [bmod_eq_iff (Nat.mul_pos h hc)]
refine ⟨?_, ?_, ?_⟩
· refine Int.le_trans ?_ (Int.mul_le_mul_of_nonneg_left (le_bmod hc) (by omega : 0 ≤ (a : Int)))
simp only [Int.natCast_mul, Int.mul_neg, Int.neg_le_neg_iff]
rw [Int.le_ediv_iff_mul_le (by omega), Int.mul_assoc]
exact Int.mul_le_mul_of_nonneg_left (by omega) (by omega)
· refine Int.lt_of_lt_of_le (Int.mul_lt_mul_of_pos_left (bmod_lt hc) (by omega)) ?_
rw [Int.natCast_mul, Int.le_ediv_iff_mul_le (by omega)]
obtain ⟨t, rfl⟩ := hce
simp only [Int.natCast_mul, cast_ofNat_Int]
rw [mul_add_ediv_left _ _ (by omega), ediv_eq_zero_of_lt (by omega) (by omega),
Int.add_zero, Int.mul_comm 2, Int.mul_assoc]
exact le.intro 1 rfl
· rw [Int.natCast_mul, ← Int.mul_sub, Int.mul_dvd_mul_iff_left (by omega)]
exact dvd_bmod_sub_self
@[simp]
theorem bmod_neg_bmod : bmod (-(bmod x n)) n = bmod (-x) n := by
apply (bmod_add_cancel_right x).mp
rw [Int.add_left_neg, ← add_bmod_bmod, Int.add_left_neg]
theorem neg_bmod {a : Int} {b : Nat} :
(-a).bmod b = if (b : Int) ∣ 2 * a then a.bmod b else -(a.bmod b) := by
refine (Nat.eq_zero_or_pos b).elim (by rintro rfl; split <;> simp_all <;> omega) (fun hb => ?_)
split <;> rename_i h
· rw [bmod_eq_bmod_iff_bmod_sub_eq_zero, ← dvd_iff_bmod_eq_zero]
simpa [(by omega : -a - a = -2 * a), Int.neg_mul] using h
· refine (bmod_eq_iff hb).2 ⟨?_, ?_, ?_⟩
· simp only [Int.neg_le_neg_iff]
have := bmod_le (x := a) hb
omega
· apply Int.neg_lt_of_neg_lt
rw [bmod_def]
split <;> rename_i h'
· exact Int.lt_of_lt_of_le (by omega) (Int.emod_nonneg _ (by omega))
· simp only [Int.not_lt] at h'
apply Int.lt_sub_left_of_add_lt
obtain ⟨c, (rfl|rfl)⟩ : ∃ c, b = 2 * c ∨ b = 2 * c + 1 := ⟨b / 2, by omega⟩
· simp only [Int.natCast_mul, cast_ofNat_Int]
rw [Int.mul_add_ediv_left _ _ (by omega), Int.ediv_eq_zero_of_lt (by omega) (by omega)]
simp only [Int.add_zero, ← Int.sub_eq_add_neg]
rw [(by omega : ∀ (i : Int), 2 * i - i = i)]
refine Decidable.by_contra (fun hc => h ?_)
simp only [gt_iff_lt, Nat.zero_lt_succ, Nat.mul_pos_iff_of_pos_left, Int.natCast_mul,
cast_ofNat_Int, Int.not_lt] at *
rw [Int.mul_dvd_mul_iff_left (by omega)]
have := ediv_add_emod a (2 * c)
rw [(by omega : a % (2 * c) = c)] at this
rw [← this]
apply Int.dvd_add _ (by simp)
rw [Int.mul_comm 2, Int.mul_assoc]
apply Int.dvd_mul_right
· omega
· simp only [Int.sub_neg, Int.add_comm, ← Int.sub_eq_add_neg]
rw [dvd_iff_bmod_eq_zero]
simp
-- There seems to be no good statement for `natAbs_bmod`.
@[simp] theorem neg_mul_bmod_left (a : Int) (b : Nat) : (-(a * b)).bmod b = 0 := by
simp [← Int.neg_mul]
@[simp] theorem neg_mul_bmod_right (a : Nat) (b : Int) : (-(a * b)).bmod a = 0 := by
simp [← Int.mul_neg]
@[simp] theorem add_neg_bmod_self (a : Int) (b : Nat) : (a + -b).bmod b = a.bmod b := by
simp [← Int.sub_eq_add_neg]
@[simp] theorem neg_add_bmod_self (a : Nat) (b : Int) : (-a + b).bmod a = b.bmod a := by
simp [Int.add_comm]
theorem dvd_self_sub_of_bmod_eq {a : Int} {b : Nat} {c : Int} (h : a.bmod b = c) :
(b : Int) ∣ a - c :=
h ▸ dvd_self_sub_bmod
theorem dvd_sub_self_of_bmod_eq {a : Int} {b : Nat} {c : Int} (h : a.bmod b = c) :
(b : Int) ∣ c - a :=
h ▸ dvd_bmod_sub_self
theorem bmod_neg_iff {m : Nat} {x : Int} (h2 : -m ≤ x) (h1 : x < m) :
(x.bmod m) < 0 ↔ (-(m / 2) ≤ x ∧ x < 0) ∨ ((m + 1) / 2 ≤ x) := by
simp only [Int.bmod_def]
by_cases xpos : 0 ≤ x
· rw [Int.emod_eq_of_lt xpos (by omega)]; omega
· rw [(Int.add_emod_right ..).symm, Int.emod_eq_of_lt (by omega) (by omega)]; omega
theorem bmod_eq_of_le {n : Int} {m : Nat} (hn' : -(m / 2) ≤ n) (hn : n < (m + 1) / 2) :
n.bmod m = n :=
(Nat.eq_zero_or_pos m).elim (by rintro rfl; simp) (fun hm => by simp_all [bmod_eq_iff])
@[deprecated bmod_eq_of_le (since := "2025-04-11")]
theorem bmod_eq_self_of_le {n : Int} {m : Nat} (hn' : -(m / 2) ≤ n) (hn : n < (m + 1) / 2) :
n.bmod m = n :=
bmod_eq_of_le hn' hn
theorem bmod_bmod_of_dvd {a : Int} {n m : Nat} (hnm : n ∣ m) :
(a.bmod m).bmod n = a.bmod n := by
rw [← Int.sub_eq_iff_eq_add.2 (bmod_add_bdiv a m).symm]
obtain ⟨k, rfl⟩ := hnm
simp [Int.mul_assoc]
theorem bmod_eq_of_le_mul_two {x : Int} {y : Nat} (hle : -y ≤ x * 2) (hlt : x * 2 < y) :
x.bmod y = x := by
apply bmod_eq_of_le (by omega) (by omega)
@[deprecated bmod_eq_of_le_mul_two (since := "2025-04-11")]
theorem bmod_eq_self_of_le_mul_two {x : Int} {y : Nat} (hle : -y ≤ x * 2) (hlt : x * 2 < y) :
x.bmod y = x :=
bmod_eq_of_le_mul_two hle hlt
/-! Helper theorems for `dvd` simproc -/
protected theorem dvd_eq_true_of_mod_eq_zero {a b : Int} (h : b % a == 0) : (a ∣ b) = True := by
simp [Int.dvd_of_emod_eq_zero, eq_of_beq h]
protected theorem dvd_eq_false_of_mod_ne_zero {a b : Int} (h : b % a != 0) : (a ∣ b) = False := by
simp [eq_of_beq] at h
simp [Int.dvd_iff_emod_eq_zero, h]
end Int