Parity of natural numbers

This file contains theorems about the Even and Odd predicates on the natural numbers.

Tags

even, odd

ink

@[simp]

theorem Nat.mod_two_ne_one {n : ℕ} : ¬n % 2 = 1 ↔ n % 2 = 0

ink

@[simp]

theorem Nat.mod_two_ne_zero {n : ℕ} : ¬n % 2 = 0 ↔ n % 2 = 1

ink

theorem Nat.even_iff {n : ℕ} : Even n ↔ n % 2 = 0

ink

instance Nat.instDecidablePredNatEvenInstAddNat : DecidablePred Even

Equations

• Nat.instDecidablePredNatEvenInstAddNat x = decidable_of_iff (x % 2 = 0) (_ : x % 2 = 0 ↔ Even x)

ink

theorem Nat.odd_iff {n : ℕ} : Odd n ↔ n % 2 = 1

ink

instance Nat.instDecidablePredNatOddSemiring : DecidablePred Odd

Equations

• Nat.instDecidablePredNatOddSemiring x = decidable_of_iff (x % 2 = 1) (_ : x % 2 = 1 ↔ Odd x)

ink

theorem Nat.not_even_iff {n : ℕ} : ¬Even n ↔ n % 2 = 1

ink

theorem Nat.not_odd_iff {n : ℕ} : ¬Odd n ↔ n % 2 = 0

ink

theorem Nat.even_iff_not_odd {n : ℕ} : Even n ↔ ¬Odd n

ink

@[simp]

theorem Nat.odd_iff_not_even {n : ℕ} : Odd n ↔ ¬Even n

ink

theorem Nat.isCompl_even_odd : IsCompl { n | Even n } { n | Odd n }

ink

theorem Nat.even_xor_odd (n : ℕ) : Xor' (Even n) (Odd n)

ink

theorem Nat.even_or_odd (n : ℕ) : Even n ∨ Odd n

ink

theorem Nat.even_or_odd' (n : ℕ) : ∃ k, n = 2 * k ∨ n = 2 * k + 1

ink

theorem Nat.even_xor_odd' (n : ℕ) : ∃ k, Xor' (n = 2 * k) (n = 2 * k + 1)

ink

@[simp]

theorem Nat.two_dvd_ne_zero {n : ℕ} : ¬2 ∣ n ↔ n % 2 = 1

ink

theorem Nat.mod_two_add_add_odd_mod_two (m : ℕ) {n : ℕ} (hn : Odd n) : m % 2 + (m + n) % 2 = 1

ink

@[simp]

theorem Nat.mod_two_add_succ_mod_two (m : ℕ) : m % 2 + (m + 1) % 2 = 1

ink

@[simp]

theorem Nat.succ_mod_two_add_mod_two (m : ℕ) : (m + 1) % 2 + m % 2 = 1

ink

@[simp]

theorem Nat.not_even_one : ¬Even 1

ink

theorem Nat.even_add {m : ℕ} {n : ℕ} : Even (m + n) ↔ (Even m ↔ Even n)

ink

theorem Nat.even_add' {m : ℕ} {n : ℕ} : Even (m + n) ↔ (Odd m ↔ Odd n)

ink

theorem Nat.even_add_one {n : ℕ} : Even (n + 1) ↔ ¬Even n

ink

@[simp]

theorem Nat.not_even_bit1 (n : ℕ) : ¬Even (bit1 n)

ink

theorem Nat.two_not_dvd_two_mul_add_one (n : ℕ) : ¬2 ∣ 2 * n + 1

ink

theorem Nat.two_not_dvd_two_mul_sub_one {n : ℕ} : 0 < n → ¬2 ∣ 2 * n - 1

ink

theorem Nat.even_sub {m : ℕ} {n : ℕ} (h : n ≤ m) : Even (m - n) ↔ (Even m ↔ Even n)

ink

theorem Nat.even_sub' {m : ℕ} {n : ℕ} (h : n ≤ m) : Even (m - n) ↔ (Odd m ↔ Odd n)

ink

theorem Nat.Odd.sub_odd {m : ℕ} {n : ℕ} (hm : Odd m) (hn : Odd n) : Even (m - n)

ink

theorem Nat.even_mul {m : ℕ} {n : ℕ} : Even (m * n) ↔ Even m ∨ Even n

ink

theorem Nat.odd_mul {m : ℕ} {n : ℕ} : Odd (m * n) ↔ Odd m ∧ Odd n

ink

theorem Nat.Odd.of_mul_left {m : ℕ} {n : ℕ} (h : Odd (m * n)) : Odd m

ink

theorem Nat.Odd.of_mul_right {m : ℕ} {n : ℕ} (h : Odd (m * n)) : Odd n

ink

theorem Nat.even_pow {m : ℕ} {n : ℕ} : Even (m ^ n) ↔ Even m ∧ n ≠ 0

If m and n are natural numbers, then the natural number m^n is even if and only if m is even and n is positive.

ink

theorem Nat.even_pow' {m : ℕ} {n : ℕ} (h : n ≠ 0) : Even (m ^ n) ↔ Even m

ink

theorem Nat.even_div {m : ℕ} {n : ℕ} : Even (m / n) ↔ m % (2 * n) / n = 0

ink

theorem Nat.odd_add {m : ℕ} {n : ℕ} : Odd (m + n) ↔ (Odd m ↔ Even n)

ink

theorem Nat.odd_add' {m : ℕ} {n : ℕ} : Odd (m + n) ↔ (Odd n ↔ Even m)

ink

theorem Nat.ne_of_odd_add {m : ℕ} {n : ℕ} (h : Odd (m + n)) : m ≠ n

ink

theorem Nat.odd_sub {m : ℕ} {n : ℕ} (h : n ≤ m) : Odd (m - n) ↔ (Odd m ↔ Even n)

ink

theorem Nat.Odd.sub_even {m : ℕ} {n : ℕ} (h : n ≤ m) (hm : Odd m) (hn : Even n) : Odd (m - n)

ink

theorem Nat.odd_sub' {m : ℕ} {n : ℕ} (h : n ≤ m) : Odd (m - n) ↔ (Odd n ↔ Even m)

ink

theorem Nat.Even.sub_odd {m : ℕ} {n : ℕ} (h : n ≤ m) (hm : Even m) (hn : Odd n) : Odd (m - n)

ink

theorem Nat.even_mul_succ_self (n : ℕ) : Even (n * (n + 1))

ink

theorem Nat.even_mul_self_pred (n : ℕ) : Even (n * (n - 1))

ink

theorem Nat.two_mul_div_two_of_even {n : ℕ} : Even n → 2 * (n / 2) = n

ink

theorem Nat.div_two_mul_two_of_even {n : ℕ} : Even n → n / 2 * 2 = n

ink

theorem Nat.two_mul_div_two_add_one_of_odd {n : ℕ} (h : Odd n) : 2 * (n / 2) + 1 = n

ink

theorem Nat.div_two_mul_two_add_one_of_odd {n : ℕ} (h : Odd n) : n / 2 * 2 + 1 = n

ink

theorem Nat.one_add_div_two_mul_two_of_odd {n : ℕ} (h : Odd n) : 1 + n / 2 * 2 = n

ink

theorem Nat.bit0_div_two {n : ℕ} : bit0 n / 2 = n

ink

theorem Nat.bit1_div_two {n : ℕ} : bit1 n / 2 = n

ink

@[simp]

theorem Nat.bit0_div_bit0 {m : ℕ} {n : ℕ} : bit0 n / bit0 m = n / m

ink

@[simp]

theorem Nat.bit1_div_bit0 {m : ℕ} {n : ℕ} : bit1 n / bit0 m = n / m

ink

@[simp]

theorem Nat.bit0_mod_bit0 {m : ℕ} {n : ℕ} : bit0 n % bit0 m = bit0 (n % m)

ink

@[simp]

theorem Nat.bit1_mod_bit0 {m : ℕ} {n : ℕ} : bit1 n % bit0 m = bit1 (n % m)

ink

theorem Function.Involutive.iterate_bit0 {α : Type u_1} {f : α → α} (hf : Function.Involutive f) (n : ℕ) : f^[bit0 n] = id

ink

theorem Function.Involutive.iterate_bit1 {α : Type u_1} {f : α → α} (hf : Function.Involutive f) (n : ℕ) : f^[bit1 n] = f

ink

theorem Function.Involutive.iterate_two_mul {α : Type u_1} {f : α → α} (hf : Function.Involutive f) (n : ℕ) : f^[2 * n] = id

ink

theorem Function.Involutive.iterate_even {α : Type u_1} {f : α → α} {n : ℕ} (hf : Function.Involutive f) (hn : Even n) : f^[n] = id

ink

theorem Function.Involutive.iterate_odd {α : Type u_1} {f : α → α} {n : ℕ} (hf : Function.Involutive f) (hn : Odd n) : f^[n] = f

ink

theorem Function.Involutive.iterate_eq_self {α : Type u_1} {f : α → α} {n : ℕ} (hf : Function.Involutive f) (hne : f ≠ id) : f^[n] = f ↔ Odd n

ink

theorem Function.Involutive.iterate_eq_id {α : Type u_1} {f : α → α} {n : ℕ} (hf : Function.Involutive f) (hne : f ≠ id) : f^[n] = id ↔ Even n

ink

theorem neg_one_pow_eq_one_iff_even {R : Type u_1} [inst : Monoid R] [inst : HasDistribNeg R] {n : ℕ} (h : -1 ≠ 1) : (-1) ^ n = 1 ↔ Even n

ink

theorem Odd.mod_even_iff {n : ℕ} {a : ℕ} (ha : Even a) : Odd (n % a) ↔ Odd n

If a is even, then n is odd iff n % a is odd.

ink

theorem Even.mod_even_iff {n : ℕ} {a : ℕ} (ha : Even a) : Even (n % a) ↔ Even n

If a is even, then n is even iff n % a is even.

ink

theorem Odd.mod_even {n : ℕ} {a : ℕ} (hn : Odd n) (ha : Even a) : Odd (n % a)

If n is odd and a is even, then n % a is odd.

ink

theorem Even.mod_even {n : ℕ} {a : ℕ} (hn : Even n) (ha : Even a) : Even (n % a)

If n is even and a is even, then n % a is even.

ink

theorem Odd.of_dvd_nat {m : ℕ} {n : ℕ} (hn : Odd n) (hm : m ∣ n) : Odd m

ink

theorem Odd.ne_two_of_dvd_nat {m : ℕ} {n : ℕ} (hn : Odd n) (hm : m ∣ n) : m ≠ 2

2 is not a factor of an odd natural number.