mathlib3 documentation

data.nat.parity

Parity of natural numbers #

THIS FILE IS SYNCHRONIZED WITH MATHLIB4. Any changes to this file require a corresponding PR to mathlib4.

This file contains theorems about the even and odd predicates on the natural numbers.

Tags #

even, odd

@[simp]
theorem nat.mod_two_ne_one {n : } :
¬n % 2 = 1 n % 2 = 0
@[simp]
theorem nat.mod_two_ne_zero {n : } :
¬n % 2 = 0 n % 2 = 1
theorem nat.even_iff {n : } :
even n n % 2 = 0
theorem nat.odd_iff {n : } :
odd n n % 2 = 1
theorem nat.not_even_iff {n : } :
¬even n n % 2 = 1
theorem nat.not_odd_iff {n : } :
¬odd n n % 2 = 0
theorem nat.even_iff_not_odd {n : } :
@[simp]
theorem nat.odd_iff_not_even {n : } :
theorem nat.is_compl_even_odd  :
is_compl {n : | even n} {n : | odd n}
theorem nat.even_or_odd (n : ) :
theorem nat.even_or_odd' (n : ) :
(k : ), n = 2 * k n = 2 * k + 1
theorem nat.even_xor_odd (n : ) :
xor (even n) (odd n)
theorem nat.even_xor_odd' (n : ) :
(k : ), xor (n = 2 * k) (n = 2 * k + 1)
@[simp]
theorem nat.two_dvd_ne_zero {n : } :
¬2 n n % 2 = 1
@[protected, instance]
Equations
@[protected, instance]
Equations
theorem nat.mod_two_add_add_odd_mod_two (m : ) {n : } (hn : odd n) :
m % 2 + (m + n) % 2 = 1
@[simp]
theorem nat.mod_two_add_succ_mod_two (m : ) :
m % 2 + (m + 1) % 2 = 1
@[simp]
theorem nat.succ_mod_two_add_mod_two (m : ) :
(m + 1) % 2 + m % 2 = 1
@[simp]
theorem nat.not_even_one  :
theorem nat.even_add {m n : } :
even (m + n) (even m even n)
theorem nat.even_add' {m n : } :
even (m + n) (odd m odd n)
theorem nat.even_add_one {n : } :
even (n + 1) ¬even n
@[simp]
theorem nat.not_even_bit1 (n : ) :
theorem nat.two_not_dvd_two_mul_add_one (n : ) :
¬2 2 * n + 1
theorem nat.two_not_dvd_two_mul_sub_one {n : } (w : 0 < n) :
¬2 2 * n - 1
theorem nat.even_sub {m n : } (h : n m) :
even (m - n) (even m even n)
theorem nat.even_sub' {m n : } (h : n m) :
even (m - n) (odd m odd n)
theorem nat.odd.sub_odd {m n : } (hm : odd m) (hn : odd n) :
even (m - n)
theorem nat.even_mul {m n : } :
even (m * n) even m even n
theorem nat.odd_mul {m n : } :
odd (m * n) odd m odd n
theorem nat.odd.of_mul_left {m n : } (h : odd (m * n)) :
odd m
theorem nat.odd.of_mul_right {m n : } (h : odd (m * n)) :
odd n
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.

theorem nat.even_pow' {m n : } (h : n 0) :
even (m ^ n) even m
theorem nat.even_div {m n : } :
even (m / n) m % (2 * n) / n = 0
theorem nat.odd_add {m n : } :
odd (m + n) (odd m even n)
theorem nat.odd_add' {m n : } :
odd (m + n) (odd n even m)
theorem nat.ne_of_odd_add {m n : } (h : odd (m + n)) :
m n
theorem nat.odd_sub {m n : } (h : n m) :
odd (m - n) (odd m even n)
theorem nat.odd.sub_even {m n : } (h : n m) (hm : odd m) (hn : even n) :
odd (m - n)
theorem nat.odd_sub' {m n : } (h : n m) :
odd (m - n) (odd n even m)
theorem nat.even.sub_odd {m n : } (h : n m) (hm : even m) (hn : odd n) :
odd (m - n)
theorem nat.even_mul_succ_self (n : ) :
even (n * (n + 1))
theorem nat.even_mul_self_pred (n : ) :
even (n * (n - 1))
theorem nat.two_mul_div_two_of_even {n : } :
even n 2 * (n / 2) = n
theorem nat.div_two_mul_two_of_even {n : } :
even n n / 2 * 2 = n
theorem nat.two_mul_div_two_add_one_of_odd {n : } (h : odd n) :
2 * (n / 2) + 1 = n
theorem nat.div_two_mul_two_add_one_of_odd {n : } (h : odd n) :
n / 2 * 2 + 1 = n
theorem nat.one_add_div_two_mul_two_of_odd {n : } (h : odd n) :
1 + n / 2 * 2 = n
theorem nat.bit0_div_two {n : } :
bit0 n / 2 = n
theorem nat.bit1_div_two {n : } :
bit1 n / 2 = n
@[simp]
theorem nat.bit0_div_bit0 {m n : } :
bit0 n / bit0 m = n / m
@[simp]
theorem nat.bit1_div_bit0 {m n : } :
bit1 n / bit0 m = n / m
@[simp]
theorem nat.bit0_mod_bit0 {m n : } :
bit0 n % bit0 m = bit0 (n % m)
@[simp]
theorem nat.bit1_mod_bit0 {m n : } :
bit1 n % bit0 m = bit1 (n % m)
theorem function.involutive.iterate_bit0 {α : Type u_1} {f : α α} (hf : function.involutive f) (n : ) :
theorem function.involutive.iterate_bit1 {α : Type u_1} {f : α α} (hf : function.involutive f) (n : ) :
f^[bit1 n] = f
theorem function.involutive.iterate_even {α : Type u_1} {f : α α} {n : } (hf : function.involutive f) (hn : even n) :
f^[n] = id
theorem function.involutive.iterate_odd {α : Type u_1} {f : α α} {n : } (hf : function.involutive f) (hn : odd n) :
f^[n] = f
theorem function.involutive.iterate_eq_self {α : Type u_1} {f : α α} {n : } (hf : function.involutive f) (hne : f id) :
f^[n] = f odd n
theorem function.involutive.iterate_eq_id {α : Type u_1} {f : α α} {n : } (hf : function.involutive f) (hne : f id) :
theorem neg_one_pow_eq_one_iff_even {R : Type u_1} [monoid R] [has_distrib_neg R] {n : } (h : -1 1) :
(-1) ^ n = 1 even n
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.

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.

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.

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.

theorem odd.of_dvd_nat {m n : } (hn : odd n) (hm : m n) :
odd m
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.