Basic operations on the integers

This file contains some basic lemmas about integers.

See note [foundational algebra order theory].

TODO

Split this file into:

• Data.Int.Init (or maybe Data.Int.Batteries?) for lemmas that could go to Batteries
• Data.Int.Basic for the lemmas that require mathlib definitions

theorem Int.one_pos : 0 < 1

theorem Int.one_nonneg : 0 ≤ 1

theorem Int.zero_le_ofNat (n : ℕ) : 0 ≤ Int.ofNat n

instance Int.instNontrivial : Nontrivial ℤ

Equations

• Int.instNontrivial = ⋯

@[simp]

theorem Int.ofNat_eq_natCast (n : ℕ) : Int.ofNat n = ↑n

@[deprecated Int.ofNat_eq_natCast]

theorem Int.natCast_eq_ofNat (n : ℕ) : ↑n = Int.ofNat n

theorem Int.natCast_inj {m : ℕ} {n : ℕ} : ↑m = ↑n ↔ m = n

@[simp]

theorem Int.natAbs_cast (n : ℕ) : (↑n).natAbs = n

theorem Int.natCast_sub {n : ℕ} {m : ℕ} : n ≤ m → ↑(m - n) = ↑m - ↑n

@[simp]

theorem Int.natCast_eq_zero {n : ℕ} : ↑n = 0 ↔ n = 0

theorem Int.natCast_ne_zero {n : ℕ} : ↑n ≠ 0 ↔ n ≠ 0

theorem Int.natCast_ne_zero_iff_pos {n : ℕ} : ↑n ≠ 0 ↔ 0 < n

@[simp]

theorem Int.natCast_pos {n : ℕ} : 0 < ↑n ↔ 0 < n

theorem Int.natCast_succ_pos (n : ℕ) : 0 < ↑n.succ

@[simp]

theorem Int.natCast_nonpos_iff {n : ℕ} : ↑n ≤ 0 ↔ n = 0

theorem Int.natCast_nonneg (n : ℕ) : 0 ≤ ↑n

@[simp]

theorem Int.sign_natCast_add_one (n : ℕ) : (↑n + 1).sign = 1

@[simp]

theorem Int.cast_id {n : ℤ} : ↑n = n

theorem Int.two_mul (n : ℤ) : 2 * n = n + n

@[deprecated]

theorem Int.ofNat_bit0 (n : ℕ) : ↑(bit0 n) = bit0 ↑n

@[deprecated]

theorem Int.ofNat_bit1 (n : ℕ) : ↑(bit1 n) = bit1 ↑n

succ and pred

def Int.succ (a : ℤ) : ℤ

Immediate successor of an integer: succ n = n + 1

Equations

• a.succ = a + 1

def Int.pred (a : ℤ) : ℤ

Immediate predecessor of an integer: pred n = n - 1

Equations

• a.pred = a - 1

theorem Int.natCast_succ (n : ℕ) : ↑n.succ = (↑n).succ

theorem Int.pred_succ (a : ℤ) : a.succ.pred = a

theorem Int.succ_pred (a : ℤ) : a.pred.succ = a

theorem Int.neg_succ (a : ℤ) : -a.succ = (-a).pred

theorem Int.succ_neg_succ (a : ℤ) : (-a.succ).succ = -a

theorem Int.neg_pred (a : ℤ) : -a.pred = (-a).succ

theorem Int.pred_neg_pred (a : ℤ) : (-a.pred).pred = -a

theorem Int.pred_nat_succ (n : ℕ) : (↑n.succ).pred = ↑n

theorem Int.neg_nat_succ (n : ℕ) : -↑n.succ = (-↑n).pred

theorem Int.succ_neg_natCast_succ (n : ℕ) : (-↑n.succ).succ = -↑n

theorem Int.natCast_pred_of_pos {n : ℕ} (h : 0 < n) : ↑(n - 1) = ↑n - 1

theorem Int.lt_succ_self (a : ℤ) : a < a.succ

theorem Int.pred_self_lt (a : ℤ) : a.pred < a

theorem Int.le_add_one_iff {m : ℤ} {n : ℤ} : m ≤ n + 1 ↔ m ≤ n ∨ m = n + 1

theorem Int.sub_one_lt_iff {m : ℤ} {n : ℤ} : m - 1 < n ↔ m ≤ n

theorem Int.le_sub_one_iff {m : ℤ} {n : ℤ} : m ≤ n - 1 ↔ m < n

theorem Int.induction_on {p : ℤ → Prop} (i : ℤ) (hz : p 0) (hp : ∀ (i : ℕ), p ↑i → p (↑i + 1)) (hn : ∀ (i : ℕ), p (-↑i) → p (-↑i - 1)) : p i

def Int.inductionOn' {C : ℤ → Sort u_1} (z : ℤ) (b : ℤ) (H0 : C b) (Hs : (k : ℤ) → b ≤ k → C k → C (k + 1)) (Hp : (k : ℤ) → k ≤ b → C k → C (k - 1)) : C z

Inductively define a function on ℤ by defining it at b, for the succ of a number greater than b, and the pred of a number less than b.

Equations

• z.inductionOn' b H0 Hs Hp = ⋯.mpr (⋯.mpr (match z - b with | Int.ofNat n => Int.inductionOn'.pos b H0 Hs n | Int.negSucc n => Int.inductionOn'.neg b H0 Hp n))

def Int.inductionOn'.pos {C : ℤ → Sort u_1} (b : ℤ) (H0 : C b) (Hs : (k : ℤ) → b ≤ k → C k → C (k + 1)) (n : ℕ) : C (b + ↑n)

The positive case of Int.inductionOn'.

Equations

• Int.inductionOn'.pos b H0 Hs 0 = cast ⋯ H0
• Int.inductionOn'.pos b H0 Hs n.succ = cast ⋯ (Hs (b + ↑n) ⋯ (Int.inductionOn'.pos b H0 Hs n))

def Int.inductionOn'.neg {C : ℤ → Sort u_1} (b : ℤ) (H0 : C b) (Hp : (k : ℤ) → k ≤ b → C k → C (k - 1)) (n : ℕ) : C (b + Int.negSucc n)

The negative case of Int.inductionOn'.

Equations

• Int.inductionOn'.neg b H0 Hp 0 = Hp b ⋯ H0
• Int.inductionOn'.neg b H0 Hp n.succ = cast ⋯ (Hp (b + Int.negSucc n) ⋯ (Int.inductionOn'.neg b H0 Hp n))

def Int.negInduction {C : ℤ → Sort u_1} (nat : (n : ℕ) → C ↑n) (neg : (n : ℕ) → C ↑n → C (-↑n)) (n : ℤ) : C n

Inductively define a function on ℤ by defining it on ℕ and extending it from n to -n.

Equations

• Int.negInduction nat neg x = match x with | Int.ofNat n => nat n | Int.negSucc n => neg (n + 1) (nat (n + 1))

theorem Int.le_induction {P : ℤ → Prop} {m : ℤ} (h0 : P m) (h1 : ∀ (n : ℤ), m ≤ n → P n → P (n + 1)) (n : ℤ) : m ≤ n → P n

See Int.inductionOn' for an induction in both directions.

theorem Int.le_induction_down {P : ℤ → Prop} {m : ℤ} (h0 : P m) (h1 : ∀ (n : ℤ), n ≤ m → P n → P (n - 1)) (n : ℤ) : n ≤ m → P n

See Int.inductionOn' for an induction in both directions.

nat abs

@[simp]

theorem Int.natAbs_ofNat' (n : ℕ) : (Int.ofNat n).natAbs = n

theorem Int.natAbs_add_of_nonneg {a : ℤ} {b : ℤ} : 0 ≤ a → 0 ≤ b → (a + b).natAbs = a.natAbs + b.natAbs

theorem Int.natAbs_add_of_nonpos {a : ℤ} {b : ℤ} (ha : a ≤ 0) (hb : b ≤ 0) : (a + b).natAbs = a.natAbs + b.natAbs

theorem Int.natAbs_surjective : Function.Surjective Int.natAbs

@[deprecated Int.natAbs_ne_zero]

theorem Int.natAbs_ne_zero_of_ne_zero {a : ℤ} : a ≠ 0 → a.natAbs ≠ 0

theorem Int.natAbs_sq (x : ℤ) : ↑x.natAbs ^ 2 = x ^ 2

theorem Int.natAbs_pow_two (x : ℤ) : ↑x.natAbs ^ 2 = x ^ 2

Alias of Int.natAbs_sq.

/

@[simp]

theorem Int.natCast_div (m : ℕ) (n : ℕ) : ↑(m / n) = ↑m / ↑n

theorem Int.natCast_ediv (m : ℕ) (n : ℕ) : ↑(m / n) = (↑m).ediv ↑n

theorem Int.ediv_of_neg_of_pos {a : ℤ} {b : ℤ} (Ha : a < 0) (Hb : 0 < b) : a.ediv b = -((-a - 1) / b + 1)

mod

@[simp]

theorem Int.natCast_mod (m : ℕ) (n : ℕ) : ↑(m % n) = ↑m % ↑n

theorem Int.add_emod_eq_add_mod_right {m : ℤ} {n : ℤ} {k : ℤ} (i : ℤ) (H : m % n = k % n) : (m + i) % n = (k + i) % n

@[simp]

theorem Int.neg_emod_two (i : ℤ) : -i % 2 = i % 2

properties of / and %

theorem Int.emod_two_eq_zero_or_one (n : ℤ) : n % 2 = 0 ∨ n % 2 = 1

dvd

theorem Int.ediv_dvd_ediv {a : ℤ} {b : ℤ} {c : ℤ} : a ∣ b → b ∣ c → b / a ∣ c / a

theorem Int.exists_lt_and_lt_iff_not_dvd {n : ℤ} (m : ℤ) (hn : 0 < n) : (∃ (k : ℤ), n * k < m ∧ m < n * (k + 1)) ↔ ¬n ∣ m

If n > 0 then m is not divisible by n iff it is between n * k and n * (k + 1) for some k.

theorem Int.natCast_dvd_natCast {m : ℕ} {n : ℕ} : ↑m ∣ ↑n ↔ m ∣ n

theorem Int.natCast_dvd {n : ℤ} {m : ℕ} : ↑m ∣ n ↔ m ∣ n.natAbs

theorem Int.dvd_natCast {m : ℤ} {n : ℕ} : m ∣ ↑n ↔ m.natAbs ∣ n

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

theorem Int.dvd_of_mul_dvd_mul_left {a : ℤ} {m : ℤ} {n : ℤ} (ha : a ≠ 0) (h : a * m ∣ a * n) : m ∣ n

theorem Int.dvd_of_mul_dvd_mul_right {a : ℤ} {m : ℤ} {n : ℤ} (ha : a ≠ 0) (h : m * a ∣ n * a) : m ∣ n

theorem Int.eq_mul_div_of_mul_eq_mul_of_dvd_left {a : ℤ} {b : ℤ} {c : ℤ} {d : ℤ} (hb : b ≠ 0) (hbc : b ∣ c) (h : b * a = c * d) : a = c / b * d

theorem Int.eq_zero_of_dvd_of_natAbs_lt_natAbs {m : ℤ} {n : ℤ} (hmn : m ∣ n) (hnm : n.natAbs < m.natAbs) : n = 0

If an integer with larger absolute value divides an integer, it is zero.

theorem Int.eq_zero_of_dvd_of_nonneg_of_lt {m : ℤ} {n : ℤ} (hm : 0 ≤ m) (hmn : m < n) (hnm : n ∣ m) : m = 0

theorem Int.eq_of_mod_eq_of_natAbs_sub_lt_natAbs {a : ℤ} {b : ℤ} {c : ℤ} (h1 : a % b = c) (h2 : (a - c).natAbs < b.natAbs) : a = c

If two integers are congruent to a sufficiently large modulus, they are equal.

theorem Int.ofNat_add_negSucc_of_ge {m : ℕ} {n : ℕ} (h : n.succ ≤ m) : Int.ofNat m + Int.negSucc n = Int.ofNat (m - n.succ)

theorem Int.natAbs_le_of_dvd_ne_zero {m : ℤ} {n : ℤ} (hmn : m ∣ n) (hn : n ≠ 0) : m.natAbs ≤ n.natAbs

@[deprecated Int.natCast_dvd_natCast]

theorem Int.coe_nat_dvd {m : ℕ} {n : ℕ} : ↑m ∣ ↑n ↔ m ∣ n

Alias of Int.natCast_dvd_natCast.

@[deprecated Int.dvd_natCast]

theorem Int.coe_nat_dvd_right {m : ℤ} {n : ℕ} : m ∣ ↑n ↔ m.natAbs ∣ n

Alias of Int.dvd_natCast.

@[deprecated Int.natCast_dvd]

theorem Int.coe_nat_dvd_left {n : ℤ} {m : ℕ} : ↑m ∣ n ↔ m ∣ n.natAbs

Alias of Int.natCast_dvd.

/ and ordering

theorem Int.natAbs_eq_of_dvd_dvd {m : ℤ} {n : ℤ} (hmn : m ∣ n) (hnm : n ∣ m) : m.natAbs = n.natAbs

theorem Int.ediv_dvd_of_dvd {m : ℤ} {n : ℤ} (hmn : m ∣ n) : n / m ∣ n

sign

theorem Int.sign_natCast_of_ne_zero {n : ℕ} (hn : n ≠ 0) : (↑n).sign = 1

theorem Int.sign_add_eq_of_sign_eq {m : ℤ} {n : ℤ} : m.sign = n.sign → (m + n).sign = n.sign

toNat

@[simp]

theorem Int.toNat_natCast (n : ℕ) : (↑n).toNat = n

@[simp]

theorem Int.toNat_natCast_add_one {n : ℕ} : (↑n + 1).toNat = n + 1

@[simp]

theorem Int.toNat_le {m : ℤ} {n : ℕ} : m.toNat ≤ n ↔ m ≤ ↑n

@[simp]

theorem Int.lt_toNat {n : ℤ} {m : ℕ} : m < n.toNat ↔ ↑m < n

theorem Int.toNat_le_toNat {a : ℤ} {b : ℤ} (h : a ≤ b) : a.toNat ≤ b.toNat

theorem Int.toNat_lt_toNat {a : ℤ} {b : ℤ} (hb : 0 < b) : a.toNat < b.toNat ↔ a < b

theorem Int.lt_of_toNat_lt {a : ℤ} {b : ℤ} (h : a.toNat < b.toNat) : a < b

@[simp]

theorem Int.toNat_pred_coe_of_pos {i : ℤ} (h : 0 < i) : ↑(i.toNat - 1) = i - 1

@[simp]

theorem Int.toNat_eq_zero {n : ℤ} : n.toNat = 0 ↔ n ≤ 0

@[simp]

theorem Int.toNat_sub_of_le {a : ℤ} {b : ℤ} (h : b ≤ a) : ↑(a - b).toNat = a - b

@[deprecated Int.natCast_pos]

theorem Int.coe_nat_pos {n : ℕ} : 0 < ↑n ↔ 0 < n

Alias of Int.natCast_pos.

@[deprecated Int.natCast_succ_pos]

theorem Int.coe_nat_succ_pos (n : ℕ) : 0 < ↑n.succ

Alias of Int.natCast_succ_pos.

theorem Int.toNat_lt' {m : ℤ} {n : ℕ} (hn : n ≠ 0) : m.toNat < n ↔ m < ↑n

theorem Int.natMod_lt {m : ℤ} {n : ℕ} (hn : n ≠ 0) : m.natMod ↑n < n

@[simp]

theorem Int.coe_nat_pow (m : ℕ) (n : ℕ) : ↑(m ^ n) = ↑m ^ n

@[simp]

theorem Int.pow_eq (m : ℤ) (n : ℕ) : m.pow n = m ^ n

@[deprecated Int.ofNat_eq_natCast]

theorem Int.ofNat_eq_cast (n : ℕ) : Int.ofNat n = ↑n

Alias of Int.ofNat_eq_natCast.

@[deprecated Int.natCast_inj]

theorem Int.cast_eq_cast_iff_Nat {m : ℕ} {n : ℕ} : ↑m = ↑n ↔ m = n

Alias of Int.natCast_inj.

@[deprecated Int.natCast_sub]

theorem Int.coe_nat_sub {n : ℕ} {m : ℕ} : n ≤ m → ↑(m - n) = ↑m - ↑n

Alias of Int.natCast_sub.

@[deprecated Int.natCast_nonneg]

theorem Int.coe_nat_nonneg (n : ℕ) : 0 ≤ ↑n

Alias of Int.natCast_nonneg.

@[deprecated Int.sign_natCast_add_one]

theorem Int.sign_coe_add_one (n : ℕ) : (↑n + 1).sign = 1

Alias of Int.sign_natCast_add_one.

@[deprecated Int.natCast_succ]

theorem Int.nat_succ_eq_int_succ (n : ℕ) : ↑n.succ = (↑n).succ

Alias of Int.natCast_succ.

@[deprecated Int.succ_neg_natCast_succ]

theorem Int.succ_neg_nat_succ (n : ℕ) : (-↑n.succ).succ = -↑n

Alias of Int.succ_neg_natCast_succ.

@[deprecated Int.natCast_pred_of_pos]

theorem Int.coe_pred_of_pos {n : ℕ} (h : 0 < n) : ↑(n - 1) = ↑n - 1

Alias of Int.natCast_pred_of_pos.

@[deprecated Int.natCast_div]

theorem Int.coe_nat_div (m : ℕ) (n : ℕ) : ↑(m / n) = ↑m / ↑n

Alias of Int.natCast_div.

@[deprecated Int.natCast_ediv]

theorem Int.coe_nat_ediv (m : ℕ) (n : ℕ) : ↑(m / n) = (↑m).ediv ↑n

Alias of Int.natCast_ediv.

@[deprecated Int.sign_natCast_of_ne_zero]

theorem Int.sign_coe_nat_of_nonzero {n : ℕ} (hn : n ≠ 0) : (↑n).sign = 1

Alias of Int.sign_natCast_of_ne_zero.

@[deprecated Int.toNat_natCast]

theorem Int.toNat_coe_nat (n : ℕ) : (↑n).toNat = n

Alias of Int.toNat_natCast.

@[deprecated Int.toNat_natCast_add_one]

theorem Int.toNat_coe_nat_add_one {n : ℕ} : (↑n + 1).toNat = n + 1

Alias of Int.toNat_natCast_add_one.