number_theory.divisors
⟷
Mathlib.NumberTheory.Divisors
The following section lists changes to this file in mathlib3 and mathlib4 that occured after the initial port. Most recent changes are shown first. Hovering over a commit will show all commits associated with the same mathlib3 commit.
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(last sync)
A few convenience shortcuts for dvd
along with some simple nat
lemmas. Also
neg_dvd_of_dvd
/dvd_of_neg_dvd
/dvd_neg_of_dvd
/dvd_of_dvd_neg
in favor of the aforementioned shortcuts.dvd_neg
/neg_dvd
.int.of_nat_dvd_of_dvd_nat_abs
/int.dvd_nat_abs_of_of_nat_dvd
because they are the two directions of int.coe_nat_dvd_left
.group_with_zero.to_cancel_monoid_with_zero
from algebra.group_with_zero.units.basic
back to algebra.group_with_zero.basic
. It was erroneously moved during the Great Splits.@@ -185,7 +185,7 @@ lemma divisors_antidiagonal_zero : divisors_antidiagonal 0 = ∅ := by { ext, si
@[simp]
lemma divisors_antidiagonal_one : divisors_antidiagonal 1 = {(1,1)} :=
-by { ext, simp [nat.mul_eq_one_iff, prod.ext_iff], }
+by { ext, simp [mul_eq_one, prod.ext_iff], }
@[simp] lemma swap_mem_divisors_antidiagonal {x : ℕ × ℕ} :
x.swap ∈ divisors_antidiagonal n ↔ x ∈ divisors_antidiagonal n :=
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(first ported)
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -101,7 +101,7 @@ theorem properDivisors.not_self_mem : ¬n ∈ properDivisors n := by simp [prope
theorem mem_properDivisors {m : ℕ} : n ∈ properDivisors m ↔ n ∣ m ∧ n < m :=
by
rcases eq_or_ne m 0 with (rfl | hm); · simp [proper_divisors]
- simp only [and_comm', ← filter_dvd_eq_proper_divisors hm, mem_filter, mem_range]
+ simp only [and_comm, ← filter_dvd_eq_proper_divisors hm, mem_filter, mem_range]
#align nat.mem_proper_divisors Nat.mem_properDivisors
-/
@@ -156,7 +156,7 @@ theorem mem_divisorsAntidiagonal {x : ℕ × ℕ} :
x ∈ divisorsAntidiagonal n ↔ x.fst * x.snd = n ∧ n ≠ 0 :=
by
simp only [divisors_antidiagonal, Finset.mem_Ico, Ne.def, Finset.mem_filter, Finset.mem_product]
- rw [and_comm']
+ rw [and_comm]
apply and_congr_right
rintro rfl
constructor <;> intro h
@@ -506,7 +506,7 @@ theorem mem_properDivisors_prime_pow {p : ℕ} (pp : p.Prime) (k : ℕ) {x : ℕ
x ∈ properDivisors (p ^ k) ↔ ∃ (j : ℕ) (H : j < k), x = p ^ j :=
by
rw [mem_proper_divisors, Nat.dvd_prime_pow pp, ← exists_and_right]
- simp only [exists_prop, and_assoc']
+ simp only [exists_prop, and_assoc]
apply exists_congr
intro a
constructor <;> intro h
@@ -574,7 +574,7 @@ theorem prime_divisors_eq_to_filter_divisors_prime (n : ℕ) :
rcases n.eq_zero_or_pos with (rfl | hn)
· simp
· ext q
- simpa [hn, hn.ne', mem_factors] using and_comm' (Prime q) (q ∣ n)
+ simpa [hn, hn.ne', mem_factors] using and_comm (Prime q) (q ∣ n)
#align nat.prime_divisors_eq_to_filter_divisors_prime Nat.prime_divisors_eq_to_filter_divisors_prime
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -3,7 +3,7 @@ Copyright (c) 2020 Aaron Anderson. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Aaron Anderson
-/
-import Algebra.BigOperators.Order
+import Algebra.Order.BigOperators.Group.Finset
import Data.Nat.Interval
import Data.Nat.Factors
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -162,7 +162,7 @@ theorem mem_divisorsAntidiagonal {x : ℕ × ℕ} :
constructor <;> intro h
· contrapose! h; simp [h]
· rw [Nat.lt_add_one_iff, Nat.lt_add_one_iff]
- rw [mul_eq_zero, Decidable.not_or_iff_and_not] at h
+ rw [mul_eq_zero, Decidable.not_or_iff_and_not] at h
simp only [succ_le_of_lt (Nat.pos_of_ne_zero h.1), succ_le_of_lt (Nat.pos_of_ne_zero h.2),
true_and_iff]
exact
@@ -235,7 +235,7 @@ theorem properDivisors_one : properDivisors 1 = ∅ := by rw [proper_divisors, I
theorem pos_of_mem_divisors {m : ℕ} (h : m ∈ n.divisors) : 0 < m :=
by
cases m
- · rw [mem_divisors, zero_dvd_iff] at h ; cases h.2 h.1
+ · rw [mem_divisors, zero_dvd_iff] at h; cases h.2 h.1
apply Nat.succ_pos
#align nat.pos_of_mem_divisors Nat.pos_of_mem_divisors
-/
@@ -276,7 +276,7 @@ theorem swap_mem_divisorsAntidiagonal {x : ℕ × ℕ} :
#print Nat.fst_mem_divisors_of_mem_antidiagonal /-
theorem fst_mem_divisors_of_mem_antidiagonal {x : ℕ × ℕ} (h : x ∈ divisorsAntidiagonal n) :
x.fst ∈ divisors n := by
- rw [mem_divisors_antidiagonal] at h
+ rw [mem_divisors_antidiagonal] at h
simp [Dvd.intro _ h.1, h.2]
#align nat.fst_mem_divisors_of_mem_antidiagonal Nat.fst_mem_divisors_of_mem_antidiagonal
-/
@@ -284,7 +284,7 @@ theorem fst_mem_divisors_of_mem_antidiagonal {x : ℕ × ℕ} (h : x ∈ divisor
#print Nat.snd_mem_divisors_of_mem_antidiagonal /-
theorem snd_mem_divisors_of_mem_antidiagonal {x : ℕ × ℕ} (h : x ∈ divisorsAntidiagonal n) :
x.snd ∈ divisors n := by
- rw [mem_divisors_antidiagonal] at h
+ rw [mem_divisors_antidiagonal] at h
simp [Dvd.intro_left _ h.1, h.2]
#align nat.snd_mem_divisors_of_mem_antidiagonal Nat.snd_mem_divisors_of_mem_antidiagonal
-/
@@ -414,7 +414,7 @@ theorem eq_properDivisors_of_subset_of_sum_eq_sum {s : Finset ℕ} (hsub : s ⊆
∑ x in s, x = ∑ x in n.properDivisors, x → s = n.properDivisors :=
by
cases n
- · rw [proper_divisors_zero, subset_empty] at hsub
+ · rw [proper_divisors_zero, subset_empty] at hsub
simp [hsub]
classical
rw [← sum_sdiff hsub]
@@ -422,12 +422,12 @@ theorem eq_properDivisors_of_subset_of_sum_eq_sum {s : Finset ℕ} (hsub : s ⊆
apply subset.antisymm hsub
rw [← sdiff_eq_empty_iff_subset]
contrapose h
- rw [← Ne.def, ← nonempty_iff_ne_empty] at h
+ rw [← Ne.def, ← nonempty_iff_ne_empty] at h
apply ne_of_lt
rw [← zero_add (∑ x in s, x), ← add_assoc, add_zero]
apply add_lt_add_right
have hlt := sum_lt_sum_of_nonempty h fun x hx => pos_of_mem_proper_divisors (sdiff_subset _ _ hx)
- simp only [sum_const_zero] at hlt
+ simp only [sum_const_zero] at hlt
apply hlt
#align nat.eq_proper_divisors_of_subset_of_sum_eq_sum Nat.eq_properDivisors_of_subset_of_sum_eq_sum
-/
@@ -475,7 +475,7 @@ theorem Prime.prod_divisors {α : Type _} [CommMonoid α] {p : ℕ} {f : ℕ →
theorem properDivisors_eq_singleton_one_iff_prime : n.properDivisors = {1} ↔ n.Prime :=
⟨fun h => by
have h1 := mem_singleton.2 rfl
- rw [← h, mem_proper_divisors] at h1
+ rw [← h, mem_proper_divisors] at h1
refine' nat.prime_def_lt''.mpr ⟨h1.2, fun m hdvd => _⟩
rw [← mem_singleton, ← h, mem_proper_divisors]
have hle := Nat.le_of_dvd (lt_trans (Nat.succ_pos _) h1.2) hdvd
@@ -511,7 +511,7 @@ theorem mem_properDivisors_prime_pow {p : ℕ} (pp : p.Prime) (k : ℕ) {x : ℕ
intro a
constructor <;> intro h
· rcases h with ⟨h_left, rfl, h_right⟩
- rwa [pow_lt_pow_iff pp.one_lt] at h_right
+ rwa [pow_lt_pow_iff pp.one_lt] at h_right
simpa
· rcases h with ⟨h_left, rfl⟩
rwa [pow_lt_pow_iff pp.one_lt]
@@ -607,7 +607,7 @@ theorem prod_div_divisors {α : Type _} [CommMonoid α] (n : ℕ) (f : ℕ →
rw [← prod_image]
· exact prod_congr (image_div_divisors_eq_divisors n) (by simp)
· intro x hx y hy h
- rw [mem_divisors] at hx hy
+ rw [mem_divisors] at hx hy
exact (div_eq_iff_eq_of_dvd_dvd hn hx.1 hy.1).mp h
#align nat.prod_div_divisors Nat.prod_div_divisors
#align nat.sum_div_divisors Nat.sum_div_divisors
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -417,6 +417,18 @@ theorem eq_properDivisors_of_subset_of_sum_eq_sum {s : Finset ℕ} (hsub : s ⊆
· rw [proper_divisors_zero, subset_empty] at hsub
simp [hsub]
classical
+ rw [← sum_sdiff hsub]
+ intro h
+ apply subset.antisymm hsub
+ rw [← sdiff_eq_empty_iff_subset]
+ contrapose h
+ rw [← Ne.def, ← nonempty_iff_ne_empty] at h
+ apply ne_of_lt
+ rw [← zero_add (∑ x in s, x), ← add_assoc, add_zero]
+ apply add_lt_add_right
+ have hlt := sum_lt_sum_of_nonempty h fun x hx => pos_of_mem_proper_divisors (sdiff_subset _ _ hx)
+ simp only [sum_const_zero] at hlt
+ apply hlt
#align nat.eq_proper_divisors_of_subset_of_sum_eq_sum Nat.eq_properDivisors_of_subset_of_sum_eq_sum
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -417,18 +417,6 @@ theorem eq_properDivisors_of_subset_of_sum_eq_sum {s : Finset ℕ} (hsub : s ⊆
· rw [proper_divisors_zero, subset_empty] at hsub
simp [hsub]
classical
- rw [← sum_sdiff hsub]
- intro h
- apply subset.antisymm hsub
- rw [← sdiff_eq_empty_iff_subset]
- contrapose h
- rw [← Ne.def, ← nonempty_iff_ne_empty] at h
- apply ne_of_lt
- rw [← zero_add (∑ x in s, x), ← add_assoc, add_zero]
- apply add_lt_add_right
- have hlt := sum_lt_sum_of_nonempty h fun x hx => pos_of_mem_proper_divisors (sdiff_subset _ _ hx)
- simp only [sum_const_zero] at hlt
- apply hlt
#align nat.eq_proper_divisors_of_subset_of_sum_eq_sum Nat.eq_properDivisors_of_subset_of_sum_eq_sum
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -441,7 +441,7 @@ theorem sum_properDivisors_dvd (h : ∑ x in n.properDivisors, x ∣ n) :
cases n
· contrapose! h
simp
- rw [or_iff_not_imp_right]
+ rw [Classical.or_iff_not_imp_right]
intro ne_n
have hlt : ∑ x in n.succ.succ.proper_divisors, x < n.succ.succ :=
lt_of_le_of_ne (Nat.le_of_dvd (Nat.succ_pos _) h) ne_n
mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451
@@ -3,9 +3,9 @@ Copyright (c) 2020 Aaron Anderson. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Aaron Anderson
-/
-import Mathbin.Algebra.BigOperators.Order
-import Mathbin.Data.Nat.Interval
-import Mathbin.Data.Nat.Factors
+import Algebra.BigOperators.Order
+import Data.Nat.Interval
+import Data.Nat.Factors
#align_import number_theory.divisors from "leanprover-community/mathlib"@"e8638a0fcaf73e4500469f368ef9494e495099b3"
mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345
@@ -2,16 +2,13 @@
Copyright (c) 2020 Aaron Anderson. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Aaron Anderson
-
-! This file was ported from Lean 3 source module number_theory.divisors
-! leanprover-community/mathlib commit e8638a0fcaf73e4500469f368ef9494e495099b3
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
-/
import Mathbin.Algebra.BigOperators.Order
import Mathbin.Data.Nat.Interval
import Mathbin.Data.Nat.Factors
+#align_import number_theory.divisors from "leanprover-community/mathlib"@"e8638a0fcaf73e4500469f368ef9494e495099b3"
+
/-!
# Divisor finsets
mathlib commit https://github.com/leanprover-community/mathlib/commit/9fb8964792b4237dac6200193a0d533f1b3f7423
@@ -73,6 +73,7 @@ def divisorsAntidiagonal : Finset (ℕ × ℕ) :=
variable {n}
+#print Nat.filter_dvd_eq_divisors /-
@[simp]
theorem filter_dvd_eq_divisors (h : n ≠ 0) : (Finset.range n.succ).filterₓ (· ∣ n) = n.divisors :=
by
@@ -80,7 +81,9 @@ theorem filter_dvd_eq_divisors (h : n ≠ 0) : (Finset.range n.succ).filterₓ (
simp only [divisors, mem_filter, mem_range, mem_Ico, and_congr_left_iff, iff_and_self]
exact fun ha _ => succ_le_iff.mpr (pos_of_dvd_of_pos ha h.bot_lt)
#align nat.filter_dvd_eq_divisors Nat.filter_dvd_eq_divisors
+-/
+#print Nat.filter_dvd_eq_properDivisors /-
@[simp]
theorem filter_dvd_eq_properDivisors (h : n ≠ 0) :
(Finset.range n).filterₓ (· ∣ n) = n.properDivisors :=
@@ -89,6 +92,7 @@ theorem filter_dvd_eq_properDivisors (h : n ≠ 0) :
simp only [proper_divisors, mem_filter, mem_range, mem_Ico, and_congr_left_iff, iff_and_self]
exact fun ha _ => succ_le_iff.mpr (pos_of_dvd_of_pos ha h.bot_lt)
#align nat.filter_dvd_eq_proper_divisors Nat.filter_dvd_eq_properDivisors
+-/
#print Nat.properDivisors.not_self_mem /-
theorem properDivisors.not_self_mem : ¬n ∈ properDivisors n := by simp [proper_divisors]
@@ -104,10 +108,12 @@ theorem mem_properDivisors {m : ℕ} : n ∈ properDivisors m ↔ n ∣ m ∧ n
#align nat.mem_proper_divisors Nat.mem_properDivisors
-/
+#print Nat.insert_self_properDivisors /-
theorem insert_self_properDivisors (h : n ≠ 0) : insert n (properDivisors n) = divisors n := by
rw [divisors, proper_divisors, Ico_succ_right_eq_insert_Ico (one_le_iff_ne_zero.2 h),
Finset.filter_insert, if_pos (dvd_refl n)]
#align nat.insert_self_proper_divisors Nat.insert_self_properDivisors
+-/
#print Nat.cons_self_properDivisors /-
theorem cons_self_properDivisors (h : n ≠ 0) :
@@ -298,17 +304,21 @@ theorem map_swap_divisorsAntidiagonal :
#align nat.map_swap_divisors_antidiagonal Nat.map_swap_divisorsAntidiagonal
-/
+#print Nat.image_fst_divisorsAntidiagonal /-
@[simp]
theorem image_fst_divisorsAntidiagonal : (divisorsAntidiagonal n).image Prod.fst = divisors n := by
ext; simp [Dvd.Dvd, @eq_comm _ n (_ * _)]
#align nat.image_fst_divisors_antidiagonal Nat.image_fst_divisorsAntidiagonal
+-/
+#print Nat.image_snd_divisorsAntidiagonal /-
@[simp]
theorem image_snd_divisorsAntidiagonal : (divisorsAntidiagonal n).image Prod.snd = divisors n :=
by
rw [← map_swap_divisors_antidiagonal, map_eq_image, image_image]
exact image_fst_divisors_antidiagonal
#align nat.image_snd_divisors_antidiagonal Nat.image_snd_divisorsAntidiagonal
+-/
#print Nat.map_div_right_divisors /-
theorem map_div_right_divisors :
@@ -380,11 +390,13 @@ theorem mem_divisors_prime_pow {p : ℕ} (pp : p.Prime) (k : ℕ) {x : ℕ} :
#align nat.mem_divisors_prime_pow Nat.mem_divisors_prime_pow
-/
+#print Nat.Prime.divisors /-
theorem Prime.divisors {p : ℕ} (pp : p.Prime) : divisors p = {1, p} :=
by
ext
rw [mem_divisors, dvd_prime pp, and_iff_left pp.ne_zero, Finset.mem_insert, Finset.mem_singleton]
#align nat.prime.divisors Nat.Prime.divisors
+-/
#print Nat.Prime.properDivisors /-
theorem Prime.properDivisors {p : ℕ} (pp : p.Prime) : properDivisors p = {1} := by
@@ -453,12 +465,14 @@ theorem Prime.prod_properDivisors {α : Type _} [CommMonoid α] {p : ℕ} {f :
#align nat.prime.sum_proper_divisors Nat.Prime.sum_properDivisors
-/
+#print Nat.Prime.prod_divisors /-
@[simp, to_additive]
theorem Prime.prod_divisors {α : Type _} [CommMonoid α] {p : ℕ} {f : ℕ → α} (h : p.Prime) :
∏ x in p.divisors, f x = f p * f 1 := by
rw [← cons_self_proper_divisors h.ne_zero, prod_cons, h.prod_proper_divisors]
#align nat.prime.prod_divisors Nat.Prime.prod_divisors
#align nat.prime.sum_divisors Nat.Prime.sum_divisors
+-/
#print Nat.properDivisors_eq_singleton_one_iff_prime /-
theorem properDivisors_eq_singleton_one_iff_prime : n.properDivisors = {1} ↔ n.Prime :=
@@ -555,6 +569,7 @@ theorem prod_divisorsAntidiagonal' {M : Type _} [CommMonoid M] (f : ℕ → ℕ
#align nat.sum_divisors_antidiagonal' Nat.sum_divisorsAntidiagonal'
-/
+#print Nat.prime_divisors_eq_to_filter_divisors_prime /-
/-- The factors of `n` are the prime divisors -/
theorem prime_divisors_eq_to_filter_divisors_prime (n : ℕ) :
n.factors.toFinset = (divisors n).filterₓ Prime :=
@@ -564,7 +579,9 @@ theorem prime_divisors_eq_to_filter_divisors_prime (n : ℕ) :
· ext q
simpa [hn, hn.ne', mem_factors] using and_comm' (Prime q) (q ∣ n)
#align nat.prime_divisors_eq_to_filter_divisors_prime Nat.prime_divisors_eq_to_filter_divisors_prime
+-/
+#print Nat.image_div_divisors_eq_divisors /-
@[simp]
theorem image_div_divisors_eq_divisors (n : ℕ) :
image (fun x : ℕ => n / x) n.divisors = n.divisors :=
@@ -582,6 +599,7 @@ theorem image_div_divisors_eq_divisors (n : ℕ) :
rintro ⟨h1, -⟩
exact ⟨n / a, mem_divisors.mpr ⟨div_dvd_of_dvd h1, hn⟩, Nat.div_div_self h1 hn⟩
#align nat.image_div_divisors_eq_divisors Nat.image_div_divisors_eq_divisors
+-/
#print Nat.prod_div_divisors /-
@[simp, to_additive sum_div_divisors]
mathlib commit https://github.com/leanprover-community/mathlib/commit/a3e83f0fa4391c8740f7d773a7a9b74e311ae2a3
@@ -340,7 +340,7 @@ theorem map_div_left_divisors :
#print Nat.sum_divisors_eq_sum_properDivisors_add_self /-
theorem sum_divisors_eq_sum_properDivisors_add_self :
- (∑ i in divisors n, i) = (∑ i in properDivisors n, i) + n :=
+ ∑ i in divisors n, i = ∑ i in properDivisors n, i + n :=
by
rcases Decidable.eq_or_ne n 0 with (rfl | hn)
· simp
@@ -352,19 +352,19 @@ theorem sum_divisors_eq_sum_properDivisors_add_self :
/-- `n : ℕ` is perfect if and only the sum of the proper divisors of `n` is `n` and `n`
is positive. -/
def Perfect (n : ℕ) : Prop :=
- (∑ i in properDivisors n, i) = n ∧ 0 < n
+ ∑ i in properDivisors n, i = n ∧ 0 < n
#align nat.perfect Nat.Perfect
-/
#print Nat.perfect_iff_sum_properDivisors /-
-theorem perfect_iff_sum_properDivisors (h : 0 < n) : Perfect n ↔ (∑ i in properDivisors n, i) = n :=
+theorem perfect_iff_sum_properDivisors (h : 0 < n) : Perfect n ↔ ∑ i in properDivisors n, i = n :=
and_iff_left h
#align nat.perfect_iff_sum_proper_divisors Nat.perfect_iff_sum_properDivisors
-/
#print Nat.perfect_iff_sum_divisors_eq_two_mul /-
theorem perfect_iff_sum_divisors_eq_two_mul (h : 0 < n) :
- Perfect n ↔ (∑ i in divisors n, i) = 2 * n :=
+ Perfect n ↔ ∑ i in divisors n, i = 2 * n :=
by
rw [perfect_iff_sum_proper_divisors h, sum_divisors_eq_sum_proper_divisors_add_self, two_mul]
constructor <;> intro h
@@ -402,7 +402,7 @@ theorem divisors_prime_pow {p : ℕ} (pp : p.Prime) (k : ℕ) :
#print Nat.eq_properDivisors_of_subset_of_sum_eq_sum /-
theorem eq_properDivisors_of_subset_of_sum_eq_sum {s : Finset ℕ} (hsub : s ⊆ n.properDivisors) :
- ((∑ x in s, x) = ∑ x in n.properDivisors, x) → s = n.properDivisors :=
+ ∑ x in s, x = ∑ x in n.properDivisors, x → s = n.properDivisors :=
by
cases n
· rw [proper_divisors_zero, subset_empty] at hsub
@@ -424,8 +424,8 @@ theorem eq_properDivisors_of_subset_of_sum_eq_sum {s : Finset ℕ} (hsub : s ⊆
-/
#print Nat.sum_properDivisors_dvd /-
-theorem sum_properDivisors_dvd (h : (∑ x in n.properDivisors, x) ∣ n) :
- (∑ x in n.properDivisors, x) = 1 ∨ (∑ x in n.properDivisors, x) = n :=
+theorem sum_properDivisors_dvd (h : ∑ x in n.properDivisors, x ∣ n) :
+ ∑ x in n.properDivisors, x = 1 ∨ ∑ x in n.properDivisors, x = n :=
by
cases n
· simp
@@ -434,7 +434,7 @@ theorem sum_properDivisors_dvd (h : (∑ x in n.properDivisors, x) ∣ n) :
simp
rw [or_iff_not_imp_right]
intro ne_n
- have hlt : (∑ x in n.succ.succ.proper_divisors, x) < n.succ.succ :=
+ have hlt : ∑ x in n.succ.succ.proper_divisors, x < n.succ.succ :=
lt_of_le_of_ne (Nat.le_of_dvd (Nat.succ_pos _) h) ne_n
symm
rw [← mem_singleton,
@@ -448,14 +448,14 @@ theorem sum_properDivisors_dvd (h : (∑ x in n.properDivisors, x) ∣ n) :
#print Nat.Prime.prod_properDivisors /-
@[simp, to_additive]
theorem Prime.prod_properDivisors {α : Type _} [CommMonoid α] {p : ℕ} {f : ℕ → α} (h : p.Prime) :
- (∏ x in p.properDivisors, f x) = f 1 := by simp [h.proper_divisors]
+ ∏ x in p.properDivisors, f x = f 1 := by simp [h.proper_divisors]
#align nat.prime.prod_proper_divisors Nat.Prime.prod_properDivisors
#align nat.prime.sum_proper_divisors Nat.Prime.sum_properDivisors
-/
@[simp, to_additive]
theorem Prime.prod_divisors {α : Type _} [CommMonoid α] {p : ℕ} {f : ℕ → α} (h : p.Prime) :
- (∏ x in p.divisors, f x) = f p * f 1 := by
+ ∏ x in p.divisors, f x = f p * f 1 := by
rw [← cons_self_proper_divisors h.ne_zero, prod_cons, h.prod_proper_divisors]
#align nat.prime.prod_divisors Nat.Prime.prod_divisors
#align nat.prime.sum_divisors Nat.Prime.sum_divisors
@@ -473,7 +473,7 @@ theorem properDivisors_eq_singleton_one_iff_prime : n.properDivisors = {1} ↔ n
-/
#print Nat.sum_properDivisors_eq_one_iff_prime /-
-theorem sum_properDivisors_eq_one_iff_prime : (∑ x in n.properDivisors, x) = 1 ↔ n.Prime :=
+theorem sum_properDivisors_eq_one_iff_prime : ∑ x in n.properDivisors, x = 1 ↔ n.Prime :=
by
cases n
· simp [Nat.not_prime_zero]
@@ -518,7 +518,7 @@ theorem properDivisors_prime_pow {p : ℕ} (pp : p.Prime) (k : ℕ) :
#print Nat.prod_properDivisors_prime_pow /-
@[simp, to_additive]
theorem prod_properDivisors_prime_pow {α : Type _} [CommMonoid α] {k p : ℕ} {f : ℕ → α}
- (h : p.Prime) : (∏ x in (p ^ k).properDivisors, f x) = ∏ x in range k, f (p ^ x) := by
+ (h : p.Prime) : ∏ x in (p ^ k).properDivisors, f x = ∏ x in range k, f (p ^ x) := by
simp [h, proper_divisors_prime_pow]
#align nat.prod_proper_divisors_prime_pow Nat.prod_properDivisors_prime_pow
#align nat.sum_proper_divisors_prime_nsmul Nat.sum_properDivisors_prime_nsmul
@@ -527,7 +527,7 @@ theorem prod_properDivisors_prime_pow {α : Type _} [CommMonoid α] {k p : ℕ}
#print Nat.prod_divisors_prime_pow /-
@[simp, to_additive sum_divisors_prime_pow]
theorem prod_divisors_prime_pow {α : Type _} [CommMonoid α] {k p : ℕ} {f : ℕ → α} (h : p.Prime) :
- (∏ x in (p ^ k).divisors, f x) = ∏ x in range (k + 1), f (p ^ x) := by
+ ∏ x in (p ^ k).divisors, f x = ∏ x in range (k + 1), f (p ^ x) := by
simp [h, divisors_prime_pow]
#align nat.prod_divisors_prime_pow Nat.prod_divisors_prime_pow
#align nat.sum_divisors_prime_pow Nat.sum_divisors_prime_pow
@@ -536,7 +536,7 @@ theorem prod_divisors_prime_pow {α : Type _} [CommMonoid α] {k p : ℕ} {f :
#print Nat.prod_divisorsAntidiagonal /-
@[to_additive]
theorem prod_divisorsAntidiagonal {M : Type _} [CommMonoid M] (f : ℕ → ℕ → M) {n : ℕ} :
- (∏ i in n.divisorsAntidiagonal, f i.1 i.2) = ∏ i in n.divisors, f i (n / i) :=
+ ∏ i in n.divisorsAntidiagonal, f i.1 i.2 = ∏ i in n.divisors, f i (n / i) :=
by
rw [← map_div_right_divisors, Finset.prod_map]
rfl
@@ -547,7 +547,7 @@ theorem prod_divisorsAntidiagonal {M : Type _} [CommMonoid M] (f : ℕ → ℕ
#print Nat.prod_divisorsAntidiagonal' /-
@[to_additive]
theorem prod_divisorsAntidiagonal' {M : Type _} [CommMonoid M] (f : ℕ → ℕ → M) {n : ℕ} :
- (∏ i in n.divisorsAntidiagonal, f i.1 i.2) = ∏ i in n.divisors, f (n / i) i :=
+ ∏ i in n.divisorsAntidiagonal, f i.1 i.2 = ∏ i in n.divisors, f (n / i) i :=
by
rw [← map_swap_divisors_antidiagonal, Finset.prod_map]
exact prod_divisors_antidiagonal fun i j => f j i
@@ -586,7 +586,7 @@ theorem image_div_divisors_eq_divisors (n : ℕ) :
#print Nat.prod_div_divisors /-
@[simp, to_additive sum_div_divisors]
theorem prod_div_divisors {α : Type _} [CommMonoid α] (n : ℕ) (f : ℕ → α) :
- (∏ d in n.divisors, f (n / d)) = n.divisors.Prod f :=
+ ∏ d in n.divisors, f (n / d) = n.divisors.Prod f :=
by
by_cases hn : n = 0; · simp [hn]
rw [← prod_image]
mathlib commit https://github.com/leanprover-community/mathlib/commit/5f25c089cb34db4db112556f23c50d12da81b297
@@ -408,19 +408,18 @@ theorem eq_properDivisors_of_subset_of_sum_eq_sum {s : Finset ℕ} (hsub : s ⊆
· rw [proper_divisors_zero, subset_empty] at hsub
simp [hsub]
classical
- rw [← sum_sdiff hsub]
- intro h
- apply subset.antisymm hsub
- rw [← sdiff_eq_empty_iff_subset]
- contrapose h
- rw [← Ne.def, ← nonempty_iff_ne_empty] at h
- apply ne_of_lt
- rw [← zero_add (∑ x in s, x), ← add_assoc, add_zero]
- apply add_lt_add_right
- have hlt :=
- sum_lt_sum_of_nonempty h fun x hx => pos_of_mem_proper_divisors (sdiff_subset _ _ hx)
- simp only [sum_const_zero] at hlt
- apply hlt
+ rw [← sum_sdiff hsub]
+ intro h
+ apply subset.antisymm hsub
+ rw [← sdiff_eq_empty_iff_subset]
+ contrapose h
+ rw [← Ne.def, ← nonempty_iff_ne_empty] at h
+ apply ne_of_lt
+ rw [← zero_add (∑ x in s, x), ← add_assoc, add_zero]
+ apply add_lt_add_right
+ have hlt := sum_lt_sum_of_nonempty h fun x hx => pos_of_mem_proper_divisors (sdiff_subset _ _ hx)
+ simp only [sum_const_zero] at hlt
+ apply hlt
#align nat.eq_proper_divisors_of_subset_of_sum_eq_sum Nat.eq_properDivisors_of_subset_of_sum_eq_sum
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/cca40788df1b8755d5baf17ab2f27dacc2e17acb
@@ -159,7 +159,7 @@ theorem mem_divisorsAntidiagonal {x : ℕ × ℕ} :
constructor <;> intro h
· contrapose! h; simp [h]
· rw [Nat.lt_add_one_iff, Nat.lt_add_one_iff]
- rw [mul_eq_zero, Decidable.not_or_iff_and_not] at h
+ rw [mul_eq_zero, Decidable.not_or_iff_and_not] at h
simp only [succ_le_of_lt (Nat.pos_of_ne_zero h.1), succ_le_of_lt (Nat.pos_of_ne_zero h.2),
true_and_iff]
exact
@@ -232,7 +232,7 @@ theorem properDivisors_one : properDivisors 1 = ∅ := by rw [proper_divisors, I
theorem pos_of_mem_divisors {m : ℕ} (h : m ∈ n.divisors) : 0 < m :=
by
cases m
- · rw [mem_divisors, zero_dvd_iff] at h; cases h.2 h.1
+ · rw [mem_divisors, zero_dvd_iff] at h ; cases h.2 h.1
apply Nat.succ_pos
#align nat.pos_of_mem_divisors Nat.pos_of_mem_divisors
-/
@@ -273,7 +273,7 @@ theorem swap_mem_divisorsAntidiagonal {x : ℕ × ℕ} :
#print Nat.fst_mem_divisors_of_mem_antidiagonal /-
theorem fst_mem_divisors_of_mem_antidiagonal {x : ℕ × ℕ} (h : x ∈ divisorsAntidiagonal n) :
x.fst ∈ divisors n := by
- rw [mem_divisors_antidiagonal] at h
+ rw [mem_divisors_antidiagonal] at h
simp [Dvd.intro _ h.1, h.2]
#align nat.fst_mem_divisors_of_mem_antidiagonal Nat.fst_mem_divisors_of_mem_antidiagonal
-/
@@ -281,7 +281,7 @@ theorem fst_mem_divisors_of_mem_antidiagonal {x : ℕ × ℕ} (h : x ∈ divisor
#print Nat.snd_mem_divisors_of_mem_antidiagonal /-
theorem snd_mem_divisors_of_mem_antidiagonal {x : ℕ × ℕ} (h : x ∈ divisorsAntidiagonal n) :
x.snd ∈ divisors n := by
- rw [mem_divisors_antidiagonal] at h
+ rw [mem_divisors_antidiagonal] at h
simp [Dvd.intro_left _ h.1, h.2]
#align nat.snd_mem_divisors_of_mem_antidiagonal Nat.snd_mem_divisors_of_mem_antidiagonal
-/
@@ -375,7 +375,7 @@ theorem perfect_iff_sum_divisors_eq_two_mul (h : 0 < n) :
#print Nat.mem_divisors_prime_pow /-
theorem mem_divisors_prime_pow {p : ℕ} (pp : p.Prime) (k : ℕ) {x : ℕ} :
- x ∈ divisors (p ^ k) ↔ ∃ (j : ℕ)(H : j ≤ k), x = p ^ j := by
+ x ∈ divisors (p ^ k) ↔ ∃ (j : ℕ) (H : j ≤ k), x = p ^ j := by
rw [mem_divisors, Nat.dvd_prime_pow pp, and_iff_left (ne_of_gt (pow_pos pp.pos k))]
#align nat.mem_divisors_prime_pow Nat.mem_divisors_prime_pow
-/
@@ -405,7 +405,7 @@ theorem eq_properDivisors_of_subset_of_sum_eq_sum {s : Finset ℕ} (hsub : s ⊆
((∑ x in s, x) = ∑ x in n.properDivisors, x) → s = n.properDivisors :=
by
cases n
- · rw [proper_divisors_zero, subset_empty] at hsub
+ · rw [proper_divisors_zero, subset_empty] at hsub
simp [hsub]
classical
rw [← sum_sdiff hsub]
@@ -413,13 +413,13 @@ theorem eq_properDivisors_of_subset_of_sum_eq_sum {s : Finset ℕ} (hsub : s ⊆
apply subset.antisymm hsub
rw [← sdiff_eq_empty_iff_subset]
contrapose h
- rw [← Ne.def, ← nonempty_iff_ne_empty] at h
+ rw [← Ne.def, ← nonempty_iff_ne_empty] at h
apply ne_of_lt
rw [← zero_add (∑ x in s, x), ← add_assoc, add_zero]
apply add_lt_add_right
have hlt :=
sum_lt_sum_of_nonempty h fun x hx => pos_of_mem_proper_divisors (sdiff_subset _ _ hx)
- simp only [sum_const_zero] at hlt
+ simp only [sum_const_zero] at hlt
apply hlt
#align nat.eq_proper_divisors_of_subset_of_sum_eq_sum Nat.eq_properDivisors_of_subset_of_sum_eq_sum
-/
@@ -465,7 +465,7 @@ theorem Prime.prod_divisors {α : Type _} [CommMonoid α] {p : ℕ} {f : ℕ →
theorem properDivisors_eq_singleton_one_iff_prime : n.properDivisors = {1} ↔ n.Prime :=
⟨fun h => by
have h1 := mem_singleton.2 rfl
- rw [← h, mem_proper_divisors] at h1
+ rw [← h, mem_proper_divisors] at h1
refine' nat.prime_def_lt''.mpr ⟨h1.2, fun m hdvd => _⟩
rw [← mem_singleton, ← h, mem_proper_divisors]
have hle := Nat.le_of_dvd (lt_trans (Nat.succ_pos _) h1.2) hdvd
@@ -493,7 +493,7 @@ theorem sum_properDivisors_eq_one_iff_prime : (∑ x in n.properDivisors, x) = 1
#print Nat.mem_properDivisors_prime_pow /-
theorem mem_properDivisors_prime_pow {p : ℕ} (pp : p.Prime) (k : ℕ) {x : ℕ} :
- x ∈ properDivisors (p ^ k) ↔ ∃ (j : ℕ)(H : j < k), x = p ^ j :=
+ x ∈ properDivisors (p ^ k) ↔ ∃ (j : ℕ) (H : j < k), x = p ^ j :=
by
rw [mem_proper_divisors, Nat.dvd_prime_pow pp, ← exists_and_right]
simp only [exists_prop, and_assoc']
@@ -501,7 +501,7 @@ theorem mem_properDivisors_prime_pow {p : ℕ} (pp : p.Prime) (k : ℕ) {x : ℕ
intro a
constructor <;> intro h
· rcases h with ⟨h_left, rfl, h_right⟩
- rwa [pow_lt_pow_iff pp.one_lt] at h_right
+ rwa [pow_lt_pow_iff pp.one_lt] at h_right
simpa
· rcases h with ⟨h_left, rfl⟩
rwa [pow_lt_pow_iff pp.one_lt]
@@ -593,7 +593,7 @@ theorem prod_div_divisors {α : Type _} [CommMonoid α] (n : ℕ) (f : ℕ →
rw [← prod_image]
· exact prod_congr (image_div_divisors_eq_divisors n) (by simp)
· intro x hx y hy h
- rw [mem_divisors] at hx hy
+ rw [mem_divisors] at hx hy
exact (div_eq_iff_eq_of_dvd_dvd hn hx.1 hy.1).mp h
#align nat.prod_div_divisors Nat.prod_div_divisors
#align nat.sum_div_divisors Nat.sum_div_divisors
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -37,9 +37,9 @@ divisors, perfect numbers
-/
-open Classical
+open scoped Classical
-open BigOperators
+open scoped BigOperators
open Finset
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -73,12 +73,6 @@ def divisorsAntidiagonal : Finset (ℕ × ℕ) :=
variable {n}
-/- warning: nat.filter_dvd_eq_divisors -> Nat.filter_dvd_eq_divisors is a dubious translation:
-lean 3 declaration is
- forall {n : Nat}, (Ne.{1} Nat n (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero)))) -> (Eq.{1} (Finset.{0} Nat) (Finset.filter.{0} Nat (fun (_x : Nat) => Dvd.Dvd.{0} Nat Nat.hasDvd _x n) (fun (a : Nat) => Nat.decidableDvd a n) (Finset.range (Nat.succ n))) (Nat.divisors n))
-but is expected to have type
- forall {n : Nat}, (Ne.{1} Nat n (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))) -> (Eq.{1} (Finset.{0} Nat) (Finset.filter.{0} Nat (fun (_x : Nat) => Dvd.dvd.{0} Nat Nat.instDvdNat _x n) (fun (a : Nat) => Nat.decidable_dvd a n) (Finset.range (Nat.succ n))) (Nat.divisors n))
-Case conversion may be inaccurate. Consider using '#align nat.filter_dvd_eq_divisors Nat.filter_dvd_eq_divisorsₓ'. -/
@[simp]
theorem filter_dvd_eq_divisors (h : n ≠ 0) : (Finset.range n.succ).filterₓ (· ∣ n) = n.divisors :=
by
@@ -87,12 +81,6 @@ theorem filter_dvd_eq_divisors (h : n ≠ 0) : (Finset.range n.succ).filterₓ (
exact fun ha _ => succ_le_iff.mpr (pos_of_dvd_of_pos ha h.bot_lt)
#align nat.filter_dvd_eq_divisors Nat.filter_dvd_eq_divisors
-/- warning: nat.filter_dvd_eq_proper_divisors -> Nat.filter_dvd_eq_properDivisors is a dubious translation:
-lean 3 declaration is
- forall {n : Nat}, (Ne.{1} Nat n (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero)))) -> (Eq.{1} (Finset.{0} Nat) (Finset.filter.{0} Nat (fun (_x : Nat) => Dvd.Dvd.{0} Nat Nat.hasDvd _x n) (fun (a : Nat) => Nat.decidableDvd a n) (Finset.range n)) (Nat.properDivisors n))
-but is expected to have type
- forall {n : Nat}, (Ne.{1} Nat n (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))) -> (Eq.{1} (Finset.{0} Nat) (Finset.filter.{0} Nat (fun (_x : Nat) => Dvd.dvd.{0} Nat Nat.instDvdNat _x n) (fun (a : Nat) => Nat.decidable_dvd a n) (Finset.range n)) (Nat.properDivisors n))
-Case conversion may be inaccurate. Consider using '#align nat.filter_dvd_eq_proper_divisors Nat.filter_dvd_eq_properDivisorsₓ'. -/
@[simp]
theorem filter_dvd_eq_properDivisors (h : n ≠ 0) :
(Finset.range n).filterₓ (· ∣ n) = n.properDivisors :=
@@ -116,12 +104,6 @@ theorem mem_properDivisors {m : ℕ} : n ∈ properDivisors m ↔ n ∣ m ∧ n
#align nat.mem_proper_divisors Nat.mem_properDivisors
-/
-/- warning: nat.insert_self_proper_divisors -> Nat.insert_self_properDivisors is a dubious translation:
-lean 3 declaration is
- forall {n : Nat}, (Ne.{1} Nat n (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero)))) -> (Eq.{1} (Finset.{0} Nat) (Insert.insert.{0, 0} Nat (Finset.{0} Nat) (Finset.hasInsert.{0} Nat (fun (a : Nat) (b : Nat) => Nat.decidableEq a b)) n (Nat.properDivisors n)) (Nat.divisors n))
-but is expected to have type
- forall {n : Nat}, (Ne.{1} Nat n (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))) -> (Eq.{1} (Finset.{0} Nat) (Insert.insert.{0, 0} Nat (Finset.{0} Nat) (Finset.instInsertFinset.{0} Nat (fun (a : Nat) (b : Nat) => instDecidableEqNat a b)) n (Nat.properDivisors n)) (Nat.divisors n))
-Case conversion may be inaccurate. Consider using '#align nat.insert_self_proper_divisors Nat.insert_self_properDivisorsₓ'. -/
theorem insert_self_properDivisors (h : n ≠ 0) : insert n (properDivisors n) = divisors n := by
rw [divisors, proper_divisors, Ico_succ_right_eq_insert_Ico (one_le_iff_ne_zero.2 h),
Finset.filter_insert, if_pos (dvd_refl n)]
@@ -316,23 +298,11 @@ theorem map_swap_divisorsAntidiagonal :
#align nat.map_swap_divisors_antidiagonal Nat.map_swap_divisorsAntidiagonal
-/
-/- warning: nat.image_fst_divisors_antidiagonal -> Nat.image_fst_divisorsAntidiagonal is a dubious translation:
-lean 3 declaration is
- forall {n : Nat}, Eq.{1} (Finset.{0} Nat) (Finset.image.{0, 0} (Prod.{0, 0} Nat Nat) Nat (fun (a : Nat) (b : Nat) => Nat.decidableEq a b) (Prod.fst.{0, 0} Nat Nat) (Nat.divisorsAntidiagonal n)) (Nat.divisors n)
-but is expected to have type
- forall {n : Nat}, Eq.{1} (Finset.{0} Nat) (Finset.image.{0, 0} (Prod.{0, 0} Nat Nat) Nat (fun (a : Nat) (b : Nat) => instDecidableEqNat a b) (Prod.fst.{0, 0} Nat Nat) (Nat.divisorsAntidiagonal n)) (Nat.divisors n)
-Case conversion may be inaccurate. Consider using '#align nat.image_fst_divisors_antidiagonal Nat.image_fst_divisorsAntidiagonalₓ'. -/
@[simp]
theorem image_fst_divisorsAntidiagonal : (divisorsAntidiagonal n).image Prod.fst = divisors n := by
ext; simp [Dvd.Dvd, @eq_comm _ n (_ * _)]
#align nat.image_fst_divisors_antidiagonal Nat.image_fst_divisorsAntidiagonal
-/- warning: nat.image_snd_divisors_antidiagonal -> Nat.image_snd_divisorsAntidiagonal is a dubious translation:
-lean 3 declaration is
- forall {n : Nat}, Eq.{1} (Finset.{0} Nat) (Finset.image.{0, 0} (Prod.{0, 0} Nat Nat) Nat (fun (a : Nat) (b : Nat) => Nat.decidableEq a b) (Prod.snd.{0, 0} Nat Nat) (Nat.divisorsAntidiagonal n)) (Nat.divisors n)
-but is expected to have type
- forall {n : Nat}, Eq.{1} (Finset.{0} Nat) (Finset.image.{0, 0} (Prod.{0, 0} Nat Nat) Nat (fun (a : Nat) (b : Nat) => instDecidableEqNat a b) (Prod.snd.{0, 0} Nat Nat) (Nat.divisorsAntidiagonal n)) (Nat.divisors n)
-Case conversion may be inaccurate. Consider using '#align nat.image_snd_divisors_antidiagonal Nat.image_snd_divisorsAntidiagonalₓ'. -/
@[simp]
theorem image_snd_divisorsAntidiagonal : (divisorsAntidiagonal n).image Prod.snd = divisors n :=
by
@@ -410,12 +380,6 @@ theorem mem_divisors_prime_pow {p : ℕ} (pp : p.Prime) (k : ℕ) {x : ℕ} :
#align nat.mem_divisors_prime_pow Nat.mem_divisors_prime_pow
-/
-/- warning: nat.prime.divisors -> Nat.Prime.divisors is a dubious translation:
-lean 3 declaration is
- forall {p : Nat}, (Nat.Prime p) -> (Eq.{1} (Finset.{0} Nat) (Nat.divisors p) (Insert.insert.{0, 0} Nat (Finset.{0} Nat) (Finset.hasInsert.{0} Nat (fun (a : Nat) (b : Nat) => Nat.decidableEq a b)) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))) (Singleton.singleton.{0, 0} Nat (Finset.{0} Nat) (Finset.hasSingleton.{0} Nat) p)))
-but is expected to have type
- forall {p : Nat}, (Nat.Prime p) -> (Eq.{1} (Finset.{0} Nat) (Nat.divisors p) (Insert.insert.{0, 0} Nat (Finset.{0} Nat) (Finset.instInsertFinset.{0} Nat (fun (a : Nat) (b : Nat) => instDecidableEqNat a b)) (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1)) (Singleton.singleton.{0, 0} Nat (Finset.{0} Nat) (Finset.instSingletonFinset.{0} Nat) p)))
-Case conversion may be inaccurate. Consider using '#align nat.prime.divisors Nat.Prime.divisorsₓ'. -/
theorem Prime.divisors {p : ℕ} (pp : p.Prime) : divisors p = {1, p} :=
by
ext
@@ -490,12 +454,6 @@ theorem Prime.prod_properDivisors {α : Type _} [CommMonoid α] {p : ℕ} {f :
#align nat.prime.sum_proper_divisors Nat.Prime.sum_properDivisors
-/
-/- warning: nat.prime.prod_divisors -> Nat.Prime.prod_divisors is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} [_inst_1 : CommMonoid.{u1} α] {p : Nat} {f : Nat -> α}, (Nat.Prime p) -> (Eq.{succ u1} α (Finset.prod.{u1, 0} α Nat _inst_1 (Nat.divisors p) (fun (x : Nat) => f x)) (HMul.hMul.{u1, u1, u1} α α α (instHMul.{u1} α (MulOneClass.toHasMul.{u1} α (Monoid.toMulOneClass.{u1} α (CommMonoid.toMonoid.{u1} α _inst_1)))) (f p) (f (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))))))
-but is expected to have type
- forall {α : Type.{u1}} [_inst_1 : CommMonoid.{u1} α] {p : Nat} {f : Nat -> α}, (Nat.Prime p) -> (Eq.{succ u1} α (Finset.prod.{u1, 0} α Nat _inst_1 (Nat.divisors p) (fun (x : Nat) => f x)) (HMul.hMul.{u1, u1, u1} α α α (instHMul.{u1} α (MulOneClass.toMul.{u1} α (Monoid.toMulOneClass.{u1} α (CommMonoid.toMonoid.{u1} α _inst_1)))) (f p) (f (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1)))))
-Case conversion may be inaccurate. Consider using '#align nat.prime.prod_divisors Nat.Prime.prod_divisorsₓ'. -/
@[simp, to_additive]
theorem Prime.prod_divisors {α : Type _} [CommMonoid α] {p : ℕ} {f : ℕ → α} (h : p.Prime) :
(∏ x in p.divisors, f x) = f p * f 1 := by
@@ -598,12 +556,6 @@ theorem prod_divisorsAntidiagonal' {M : Type _} [CommMonoid M] (f : ℕ → ℕ
#align nat.sum_divisors_antidiagonal' Nat.sum_divisorsAntidiagonal'
-/
-/- warning: nat.prime_divisors_eq_to_filter_divisors_prime -> Nat.prime_divisors_eq_to_filter_divisors_prime is a dubious translation:
-lean 3 declaration is
- forall (n : Nat), Eq.{1} (Finset.{0} Nat) (List.toFinset.{0} Nat (fun (a : Nat) (b : Nat) => Nat.decidableEq a b) (Nat.factors n)) (Finset.filter.{0} Nat Nat.Prime (fun (a : Nat) => Nat.decidablePrime a) (Nat.divisors n))
-but is expected to have type
- forall (n : Nat), Eq.{1} (Finset.{0} Nat) (List.toFinset.{0} Nat (fun (a : Nat) (b : Nat) => instDecidableEqNat a b) (Nat.factors n)) (Finset.filter.{0} Nat Nat.Prime (fun (a : Nat) => Nat.decidablePrime a) (Nat.divisors n))
-Case conversion may be inaccurate. Consider using '#align nat.prime_divisors_eq_to_filter_divisors_prime Nat.prime_divisors_eq_to_filter_divisors_primeₓ'. -/
/-- The factors of `n` are the prime divisors -/
theorem prime_divisors_eq_to_filter_divisors_prime (n : ℕ) :
n.factors.toFinset = (divisors n).filterₓ Prime :=
@@ -614,12 +566,6 @@ theorem prime_divisors_eq_to_filter_divisors_prime (n : ℕ) :
simpa [hn, hn.ne', mem_factors] using and_comm' (Prime q) (q ∣ n)
#align nat.prime_divisors_eq_to_filter_divisors_prime Nat.prime_divisors_eq_to_filter_divisors_prime
-/- warning: nat.image_div_divisors_eq_divisors -> Nat.image_div_divisors_eq_divisors is a dubious translation:
-lean 3 declaration is
- forall (n : Nat), Eq.{1} (Finset.{0} Nat) (Finset.image.{0, 0} Nat Nat (fun (a : Nat) (b : Nat) => Nat.decidableEq a b) (fun (x : Nat) => HDiv.hDiv.{0, 0, 0} Nat Nat Nat (instHDiv.{0} Nat Nat.hasDiv) n x) (Nat.divisors n)) (Nat.divisors n)
-but is expected to have type
- forall (n : Nat), Eq.{1} (Finset.{0} Nat) (Finset.image.{0, 0} Nat Nat (fun (a : Nat) (b : Nat) => instDecidableEqNat a b) (fun (x : Nat) => HDiv.hDiv.{0, 0, 0} Nat Nat Nat (instHDiv.{0} Nat Nat.instDivNat) n x) (Nat.divisors n)) (Nat.divisors n)
-Case conversion may be inaccurate. Consider using '#align nat.image_div_divisors_eq_divisors Nat.image_div_divisors_eq_divisorsₓ'. -/
@[simp]
theorem image_div_divisors_eq_divisors (n : ℕ) :
image (fun x : ℕ => n / x) n.divisors = n.divisors :=
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -175,8 +175,7 @@ theorem mem_divisorsAntidiagonal {x : ℕ × ℕ} :
apply and_congr_right
rintro rfl
constructor <;> intro h
- · contrapose! h
- simp [h]
+ · contrapose! h; simp [h]
· rw [Nat.lt_add_one_iff, Nat.lt_add_one_iff]
rw [mul_eq_zero, Decidable.not_or_iff_and_not] at h
simp only [succ_le_of_lt (Nat.pos_of_ne_zero h.1), succ_le_of_lt (Nat.pos_of_ne_zero h.2),
@@ -219,18 +218,13 @@ theorem divisors_subset_properDivisors {m : ℕ} (hzero : n ≠ 0) (h : m ∣ n)
#print Nat.divisors_zero /-
@[simp]
-theorem divisors_zero : divisors 0 = ∅ := by
- ext
- simp
+theorem divisors_zero : divisors 0 = ∅ := by ext; simp
#align nat.divisors_zero Nat.divisors_zero
-/
#print Nat.properDivisors_zero /-
@[simp]
-theorem properDivisors_zero : properDivisors 0 = ∅ :=
- by
- ext
- simp
+theorem properDivisors_zero : properDivisors 0 = ∅ := by ext; simp
#align nat.proper_divisors_zero Nat.properDivisors_zero
-/
@@ -242,9 +236,7 @@ theorem properDivisors_subset_divisors : properDivisors n ⊆ divisors n :=
#print Nat.divisors_one /-
@[simp]
-theorem divisors_one : divisors 1 = {1} := by
- ext
- simp
+theorem divisors_one : divisors 1 = {1} := by ext; simp
#align nat.divisors_one Nat.divisors_one
-/
@@ -258,8 +250,7 @@ theorem properDivisors_one : properDivisors 1 = ∅ := by rw [proper_divisors, I
theorem pos_of_mem_divisors {m : ℕ} (h : m ∈ n.divisors) : 0 < m :=
by
cases m
- · rw [mem_divisors, zero_dvd_iff] at h
- cases h.2 h.1
+ · rw [mem_divisors, zero_dvd_iff] at h; cases h.2 h.1
apply Nat.succ_pos
#align nat.pos_of_mem_divisors Nat.pos_of_mem_divisors
-/
@@ -278,18 +269,13 @@ theorem one_mem_properDivisors_iff_one_lt : 1 ∈ n.properDivisors ↔ 1 < n :=
#print Nat.divisorsAntidiagonal_zero /-
@[simp]
-theorem divisorsAntidiagonal_zero : divisorsAntidiagonal 0 = ∅ :=
- by
- ext
- simp
+theorem divisorsAntidiagonal_zero : divisorsAntidiagonal 0 = ∅ := by ext; simp
#align nat.divisors_antidiagonal_zero Nat.divisorsAntidiagonal_zero
-/
#print Nat.divisorsAntidiagonal_one /-
@[simp]
-theorem divisorsAntidiagonal_one : divisorsAntidiagonal 1 = {(1, 1)} :=
- by
- ext
+theorem divisorsAntidiagonal_one : divisorsAntidiagonal 1 = {(1, 1)} := by ext;
simp [mul_eq_one, Prod.ext_iff]
#align nat.divisors_antidiagonal_one Nat.divisorsAntidiagonal_one
-/
@@ -337,10 +323,8 @@ but is expected to have type
forall {n : Nat}, Eq.{1} (Finset.{0} Nat) (Finset.image.{0, 0} (Prod.{0, 0} Nat Nat) Nat (fun (a : Nat) (b : Nat) => instDecidableEqNat a b) (Prod.fst.{0, 0} Nat Nat) (Nat.divisorsAntidiagonal n)) (Nat.divisors n)
Case conversion may be inaccurate. Consider using '#align nat.image_fst_divisors_antidiagonal Nat.image_fst_divisorsAntidiagonalₓ'. -/
@[simp]
-theorem image_fst_divisorsAntidiagonal : (divisorsAntidiagonal n).image Prod.fst = divisors n :=
- by
- ext
- simp [Dvd.Dvd, @eq_comm _ n (_ * _)]
+theorem image_fst_divisorsAntidiagonal : (divisorsAntidiagonal n).image Prod.fst = divisors n := by
+ ext; simp [Dvd.Dvd, @eq_comm _ n (_ * _)]
#align nat.image_fst_divisors_antidiagonal Nat.image_fst_divisorsAntidiagonal
/- warning: nat.image_snd_divisors_antidiagonal -> Nat.image_snd_divisorsAntidiagonal is a dubious translation:
@@ -447,9 +431,7 @@ theorem Prime.properDivisors {p : ℕ} (pp : p.Prime) : properDivisors p = {1} :
#print Nat.divisors_prime_pow /-
theorem divisors_prime_pow {p : ℕ} (pp : p.Prime) (k : ℕ) :
- divisors (p ^ k) = (Finset.range (k + 1)).map ⟨pow p, pow_right_injective pp.two_le⟩ :=
- by
- ext
+ divisors (p ^ k) = (Finset.range (k + 1)).map ⟨pow p, pow_right_injective pp.two_le⟩ := by ext;
simp [mem_divisors_prime_pow, pp, Nat.lt_succ_iff, @eq_comm _ a]
#align nat.divisors_prime_pow Nat.divisors_prime_pow
-/
@@ -571,9 +553,7 @@ theorem mem_properDivisors_prime_pow {p : ℕ} (pp : p.Prime) (k : ℕ) {x : ℕ
#print Nat.properDivisors_prime_pow /-
theorem properDivisors_prime_pow {p : ℕ} (pp : p.Prime) (k : ℕ) :
- properDivisors (p ^ k) = (Finset.range k).map ⟨pow p, pow_right_injective pp.two_le⟩ :=
- by
- ext
+ properDivisors (p ^ k) = (Finset.range k).map ⟨pow p, pow_right_injective pp.two_le⟩ := by ext;
simp [mem_proper_divisors_prime_pow, pp, Nat.lt_succ_iff, @eq_comm _ a]
#align nat.proper_divisors_prime_pow Nat.properDivisors_prime_pow
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/06a655b5fcfbda03502f9158bbf6c0f1400886f9
@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
Authors: Aaron Anderson
! This file was ported from Lean 3 source module number_theory.divisors
-! leanprover-community/mathlib commit 68d1483e8a718ec63219f0e227ca3f0140361086
+! leanprover-community/mathlib commit e8638a0fcaf73e4500469f368ef9494e495099b3
! Please do not edit these lines, except to modify the commit id
! if you have ported upstream changes.
-/
@@ -290,7 +290,7 @@ theorem divisorsAntidiagonal_zero : divisorsAntidiagonal 0 = ∅ :=
theorem divisorsAntidiagonal_one : divisorsAntidiagonal 1 = {(1, 1)} :=
by
ext
- simp [Nat.mul_eq_one_iff, Prod.ext_iff]
+ simp [mul_eq_one, Prod.ext_iff]
#align nat.divisors_antidiagonal_one Nat.divisorsAntidiagonal_one
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc
These are changes from #11997, the latest adaptation PR for nightly-2024-04-07, which can be made directly on master.
Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Ruben Van de Velde <65514131+Ruben-VandeVelde@users.noreply.github.com>
@@ -405,7 +405,7 @@ theorem eq_properDivisors_of_subset_of_sum_eq_sum {s : Finset ℕ} (hsub : s ⊆
apply Subset.antisymm hsub
rw [← sdiff_eq_empty_iff_subset]
contrapose h
- rw [← Ne.def, ← nonempty_iff_ne_empty] at h
+ rw [← Ne, ← nonempty_iff_ne_empty] at h
apply ne_of_lt
rw [← zero_add (∑ x in s, x), ← add_assoc, add_zero]
apply add_lt_add_right
All these are about some code (now commented out) which performs a (now) redundant binder information update. I don't see how this is useful information going forward, hence propose simply deleting them.
@@ -145,9 +145,6 @@ lemma right_ne_zero_of_mem_divisorsAntidiagonal {p : ℕ × ℕ} (hp : p ∈ n.d
p.2 ≠ 0 :=
(ne_zero_of_mem_divisorsAntidiagonal hp).2
--- Porting note: Redundant binder annotation update
--- variable {n}
-
theorem divisor_le {m : ℕ} : n ∈ divisors m → n ≤ m := by
cases' m with m
· simp
Take the content of
Algebra.BigOperators.List.Basic
Algebra.BigOperators.List.Lemmas
Algebra.BigOperators.Multiset.Basic
Algebra.BigOperators.Multiset.Lemmas
Algebra.BigOperators.Multiset.Order
Algebra.BigOperators.Order
and sort it into six files:
Algebra.Order.BigOperators.Group.List
. I credit Yakov for https://github.com/leanprover-community/mathlib/pull/8543.Algebra.Order.BigOperators.Group.Multiset
. Copyright inherited from Algebra.BigOperators.Multiset.Order
.Algebra.Order.BigOperators.Group.Finset
. Copyright inherited from Algebra.BigOperators.Order
.Algebra.Order.BigOperators.Ring.List
. I credit Stuart for https://github.com/leanprover-community/mathlib/pull/10184.Algebra.Order.BigOperators.Ring.Multiset
. I credit Ruben for https://github.com/leanprover-community/mathlib/pull/8787.Algebra.Order.BigOperators.Ring.Finset
. I credit Floris for https://github.com/leanprover-community/mathlib/pull/1294.Here are the design decisions at play:
Data.Nat.Order.Basic
in a few List
files.Algebra.Order.BigOperators
instead of Algebra.BigOperators.Order
because algebraic order theory is more of a theory than big operators algebra. Another reason is that algebraic order theory is the only way to mix pure order and pure algebra, while there are more ways to mix pure finiteness and pure algebra than just big operators.Algebra.Order.BigOperators.Group
should be additivisable (except a few Nat
- or Int
-specific lemmas). In contrast, things under Algebra.Order.BigOperators.Ring
are more prone to having heavy imports.List
vs Multiset
vs Finset
. This is not strictly necessary, and can be relaxed in cases where there aren't that many lemmas to be had. As an example, I could split out the AbsoluteValue
lemmas from Algebra.Order.BigOperators.Ring.Finset
to a file Algebra.Order.BigOperators.Ring.AbsoluteValue
and it could stay this way until too many lemmas are in this file (or a split is needed for import reasons), in which case we would need files Algebra.Order.BigOperators.Ring.AbsoluteValue.Finset
, Algebra.Order.BigOperators.Ring.AbsoluteValue.Multiset
, etc...Finsupp
big operator and finprod
/finsum
order lemmas also belong in Algebra.Order.BigOperators
. I haven't done so in this PR because the diff is big enough like that.@@ -3,8 +3,8 @@ Copyright (c) 2020 Aaron Anderson. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Aaron Anderson
-/
-import Mathlib.Algebra.BigOperators.Order
import Mathlib.Algebra.GroupPower.Order
+import Mathlib.Algebra.Order.BigOperators.Group.Finset
import Mathlib.Data.Nat.Factors
import Mathlib.Data.Nat.Interval
This PR adds a new file NumberTheory.LSeries.Dirichlet
that contains results on L-series of specific functions:
1
as a special caseζ
(which has the same L-series as the constant function 1
)It also adds (L-series of zero and of the indicator function of {1}
) and removes (convergence of the L-series of the constant function 1
/ of ζ
; this is moved to the new file) some material to/from NumberTheory.LSeries.Basic
.
See this thread on Zulip.
@@ -132,6 +132,19 @@ theorem mem_divisorsAntidiagonal {x : ℕ × ℕ} :
Nat.le_mul_of_pos_left _ (Nat.pos_of_ne_zero h.1)⟩
#align nat.mem_divisors_antidiagonal Nat.mem_divisorsAntidiagonal
+lemma ne_zero_of_mem_divisorsAntidiagonal {p : ℕ × ℕ} (hp : p ∈ n.divisorsAntidiagonal) :
+ p.1 ≠ 0 ∧ p.2 ≠ 0 := by
+ obtain ⟨hp₁, hp₂⟩ := Nat.mem_divisorsAntidiagonal.mp hp
+ exact mul_ne_zero_iff.mp (hp₁.symm ▸ hp₂)
+
+lemma left_ne_zero_of_mem_divisorsAntidiagonal {p : ℕ × ℕ} (hp : p ∈ n.divisorsAntidiagonal) :
+ p.1 ≠ 0 :=
+ (ne_zero_of_mem_divisorsAntidiagonal hp).1
+
+lemma right_ne_zero_of_mem_divisorsAntidiagonal {p : ℕ × ℕ} (hp : p ∈ n.divisorsAntidiagonal) :
+ p.2 ≠ 0 :=
+ (ne_zero_of_mem_divisorsAntidiagonal hp).2
+
-- Porting note: Redundant binder annotation update
-- variable {n}
@@ -95,7 +95,7 @@ theorem cons_self_properDivisors (h : n ≠ 0) :
@[simp]
theorem mem_divisors {m : ℕ} : n ∈ divisors m ↔ n ∣ m ∧ m ≠ 0 := by
rcases eq_or_ne m 0 with (rfl | hm); · simp [divisors]
- simp only [hm, Ne.def, not_false_iff, and_true_iff, ← filter_dvd_eq_divisors hm, mem_filter,
+ simp only [hm, Ne, not_false_iff, and_true_iff, ← filter_dvd_eq_divisors hm, mem_filter,
mem_range, and_iff_right_iff_imp, Nat.lt_succ_iff]
exact le_of_dvd hm.bot_lt
#align nat.mem_divisors Nat.mem_divisors
@@ -116,7 +116,7 @@ theorem dvd_of_mem_divisors {m : ℕ} (h : n ∈ divisors m) : n ∣ m := by
@[simp]
theorem mem_divisorsAntidiagonal {x : ℕ × ℕ} :
x ∈ divisorsAntidiagonal n ↔ x.fst * x.snd = n ∧ n ≠ 0 := by
- simp only [divisorsAntidiagonal, Finset.mem_Ico, Ne.def, Finset.mem_filter, Finset.mem_product]
+ simp only [divisorsAntidiagonal, Finset.mem_Ico, Ne, Finset.mem_filter, Finset.mem_product]
rw [and_comm]
apply and_congr_right
rintro rfl
@@ -138,7 +138,7 @@ theorem mem_divisorsAntidiagonal {x : ℕ × ℕ} :
theorem divisor_le {m : ℕ} : n ∈ divisors m → n ≤ m := by
cases' m with m
· simp
- · simp only [mem_divisors, Nat.succ_ne_zero m, and_true_iff, Ne.def, not_false_iff]
+ · simp only [mem_divisors, Nat.succ_ne_zero m, and_true_iff, Ne, not_false_iff]
exact Nat.le_of_dvd (Nat.succ_pos m)
#align nat.divisor_le Nat.divisor_le
These will be caught by the linter in a future lean version.
@@ -410,8 +410,7 @@ theorem sum_properDivisors_dvd (h : (∑ x in n.properDivisors, x) ∣ n) :
cases' n with n
· simp
· cases' n with n
- · contrapose! h
- simp
+ · simp at h
· rw [or_iff_not_imp_right]
intro ne_n
have hlt : ∑ x in n.succ.succ.properDivisors, x < n.succ.succ :=
open Classical
(#11199)
We remove all but one open Classical
s, instead preferring to use open scoped Classical
. The only real side-effect this led to is moving a couple declarations to use Exists.choose
instead of Classical.choose
.
The first few commits are explicitly labelled regex replaces for ease of review.
@@ -32,7 +32,8 @@ divisors, perfect numbers
-/
-open BigOperators Classical Finset
+open scoped Classical
+open BigOperators Finset
namespace Nat
refine
s (#10762)
I replaced a few "terminal" refine/refine'
s with exact
.
The strategy was very simple-minded: essentially any refine
whose following line had smaller indentation got replaced by exact
and then I cleaned up the mess.
This PR certainly leaves some further terminal refine
s, but maybe the current change is beneficial.
@@ -418,7 +418,7 @@ theorem sum_properDivisors_dvd (h : (∑ x in n.properDivisors, x) ∣ n) :
symm
rw [← mem_singleton, eq_properDivisors_of_subset_of_sum_eq_sum (singleton_subset_iff.2
(mem_properDivisors.2 ⟨h, hlt⟩)) (sum_singleton _ _), mem_properDivisors]
- refine' ⟨one_dvd _, Nat.succ_lt_succ (Nat.succ_pos _)⟩
+ exact ⟨one_dvd _, Nat.succ_lt_succ (Nat.succ_pos _)⟩
#align nat.sum_proper_divisors_dvd Nat.sum_properDivisors_dvd
@[to_additive (attr := simp)]
@@ -95,7 +95,7 @@ theorem cons_self_properDivisors (h : n ≠ 0) :
theorem mem_divisors {m : ℕ} : n ∈ divisors m ↔ n ∣ m ∧ m ≠ 0 := by
rcases eq_or_ne m 0 with (rfl | hm); · simp [divisors]
simp only [hm, Ne.def, not_false_iff, and_true_iff, ← filter_dvd_eq_divisors hm, mem_filter,
- mem_range, and_iff_right_iff_imp, lt_succ_iff]
+ mem_range, and_iff_right_iff_imp, Nat.lt_succ_iff]
exact le_of_dvd hm.bot_lt
#align nat.mem_divisors Nat.mem_divisors
positivity
extensions (#10140)
The goal here is to have access to positivity
earlier in the import hierarchy
@@ -4,8 +4,9 @@ Released under Apache 2.0 license as described in the file LICENSE.
Authors: Aaron Anderson
-/
import Mathlib.Algebra.BigOperators.Order
-import Mathlib.Data.Nat.Interval
+import Mathlib.Algebra.GroupPower.Order
import Mathlib.Data.Nat.Factors
+import Mathlib.Data.Nat.Interval
#align_import number_theory.divisors from "leanprover-community/mathlib"@"e8638a0fcaf73e4500469f368ef9494e495099b3"
@@ -126,7 +126,8 @@ theorem mem_divisorsAntidiagonal {x : ℕ × ℕ} :
simp only [succ_le_of_lt (Nat.pos_of_ne_zero h.1), succ_le_of_lt (Nat.pos_of_ne_zero h.2),
true_and_iff]
exact
- ⟨le_mul_of_pos_right (Nat.pos_of_ne_zero h.2), le_mul_of_pos_left (Nat.pos_of_ne_zero h.1)⟩
+ ⟨Nat.le_mul_of_pos_right _ (Nat.pos_of_ne_zero h.2),
+ Nat.le_mul_of_pos_left _ (Nat.pos_of_ne_zero h.1)⟩
#align nat.mem_divisors_antidiagonal Nat.mem_divisorsAntidiagonal
-- Porting note: Redundant binder annotation update
@@ -172,6 +172,14 @@ theorem properDivisors_zero : properDivisors 0 = ∅ := by
simp
#align nat.proper_divisors_zero Nat.properDivisors_zero
+@[simp]
+lemma nonempty_divisors : (divisors n).Nonempty ↔ n ≠ 0 :=
+ ⟨fun ⟨m, hm⟩ hn ↦ by simp [hn] at hm, fun hn ↦ ⟨1, one_mem_divisors.2 hn⟩⟩
+
+@[simp]
+lemma divisors_eq_empty : divisors n = ∅ ↔ n = 0 :=
+ not_nonempty_iff_eq_empty.symm.trans nonempty_divisors.not_left
+
theorem properDivisors_subset_divisors : properDivisors n ⊆ divisors n :=
filter_subset_filter _ <| Ico_subset_Ico_right n.le_succ
#align nat.proper_divisors_subset_divisors Nat.properDivisors_subset_divisors
@@ -208,6 +216,32 @@ lemma sup_divisors_id (n : ℕ) : n.divisors.sup id = n := by
· apply zero_le
· exact Finset.le_sup (f := id) <| mem_divisors_self n hn
+lemma one_lt_of_mem_properDivisors {m n : ℕ} (h : m ∈ n.properDivisors) : 1 < n :=
+ lt_of_le_of_lt (pos_of_mem_properDivisors h) (mem_properDivisors.1 h).2
+
+lemma one_lt_div_of_mem_properDivisors {m n : ℕ} (h : m ∈ n.properDivisors) :
+ 1 < n / m := by
+ obtain ⟨h_dvd, h_lt⟩ := mem_properDivisors.mp h
+ rwa [Nat.lt_div_iff_mul_lt h_dvd, mul_one]
+
+/-- See also `Nat.mem_properDivisors`. -/
+lemma mem_properDivisors_iff_exists {m n : ℕ} (hn : n ≠ 0) :
+ m ∈ n.properDivisors ↔ ∃ k > 1, n = m * k := by
+ refine ⟨fun h ↦ ⟨n / m, one_lt_div_of_mem_properDivisors h, ?_⟩, ?_⟩
+ · exact (Nat.mul_div_cancel' (mem_properDivisors.mp h).1).symm
+ · rintro ⟨k, hk, rfl⟩
+ rw [mul_ne_zero_iff] at hn
+ exact mem_properDivisors.mpr ⟨⟨k, rfl⟩, lt_mul_of_one_lt_right (Nat.pos_of_ne_zero hn.1) hk⟩
+
+@[simp]
+lemma nonempty_properDivisors : n.properDivisors.Nonempty ↔ 1 < n :=
+ ⟨fun ⟨_m, hm⟩ ↦ one_lt_of_mem_properDivisors hm, fun hn ↦
+ ⟨1, one_mem_properDivisors_iff_one_lt.2 hn⟩⟩
+
+@[simp]
+lemma properDivisors_eq_empty : n.properDivisors = ∅ ↔ n ≤ 1 := by
+ rw [← not_nonempty_iff_eq_empty, nonempty_properDivisors, not_lt]
+
@[simp]
theorem divisorsAntidiagonal_zero : divisorsAntidiagonal 0 = ∅ := by
ext
@@ -288,8 +288,9 @@ theorem map_div_left_divisors :
n.divisors.map ⟨fun d => (n / d, d), fun p₁ p₂ => congr_arg Prod.snd⟩ =
n.divisorsAntidiagonal := by
apply Finset.map_injective (Equiv.prodComm _ _).toEmbedding
+ ext
rw [map_swap_divisorsAntidiagonal, ← map_div_right_divisors, Finset.map_map]
- rfl
+ simp
#align nat.map_div_left_divisors Nat.map_div_left_divisors
theorem sum_divisors_eq_sum_properDivisors_add_self :
@@ -344,7 +345,7 @@ theorem divisors_injective : Function.Injective divisors :=
@[simp]
theorem divisors_inj {a b : ℕ} : a.divisors = b.divisors ↔ a = b :=
- ⟨fun x => divisors_injective x, congrArg divisors⟩
+ divisors_injective.eq_iff
theorem eq_properDivisors_of_subset_of_sum_eq_sum {s : Finset ℕ} (hsub : s ⊆ n.properDivisors) :
((∑ x in s, x) = ∑ x in n.properDivisors, x) → s = n.properDivisors := by
The names for lemmas about monotonicity of (a ^ ·)
and (· ^ n)
were a mess. This PR tidies up everything related by following the naming convention for (a * ·)
and (· * b)
. Namely, (a ^ ·)
is pow_right
and (· ^ n)
is pow_left
in lemma names. All lemma renames follow the corresponding multiplication lemma names closely.
Algebra.GroupPower.Order
pow_mono
→ pow_right_mono
pow_le_pow
→ pow_le_pow_right
pow_le_pow_of_le_left
→ pow_le_pow_left
pow_lt_pow_of_lt_left
→ pow_lt_pow_left
strictMonoOn_pow
→ pow_left_strictMonoOn
pow_strictMono_right
→ pow_right_strictMono
pow_lt_pow
→ pow_lt_pow_right
pow_lt_pow_iff
→ pow_lt_pow_iff_right
pow_le_pow_iff
→ pow_le_pow_iff_right
self_lt_pow
→ lt_self_pow
strictAnti_pow
→ pow_right_strictAnti
pow_lt_pow_iff_of_lt_one
→ pow_lt_pow_iff_right_of_lt_one
pow_lt_pow_of_lt_one
→ pow_lt_pow_right_of_lt_one
lt_of_pow_lt_pow
→ lt_of_pow_lt_pow_left
le_of_pow_le_pow
→ le_of_pow_le_pow_left
pow_lt_pow₀
→ pow_lt_pow_right₀
Algebra.GroupPower.CovariantClass
pow_le_pow_of_le_left'
→ pow_le_pow_left'
nsmul_le_nsmul_of_le_right
→ nsmul_le_nsmul_right
pow_lt_pow'
→ pow_lt_pow_right'
nsmul_lt_nsmul
→ nsmul_lt_nsmul_left
pow_strictMono_left
→ pow_right_strictMono'
nsmul_strictMono_right
→ nsmul_left_strictMono
StrictMono.pow_right'
→ StrictMono.pow_const
StrictMono.nsmul_left
→ StrictMono.const_nsmul
pow_strictMono_right'
→ pow_left_strictMono
nsmul_strictMono_left
→ nsmul_right_strictMono
Monotone.pow_right
→ Monotone.pow_const
Monotone.nsmul_left
→ Monotone.const_nsmul
lt_of_pow_lt_pow'
→ lt_of_pow_lt_pow_left'
lt_of_nsmul_lt_nsmul
→ lt_of_nsmul_lt_nsmul_right
pow_le_pow'
→ pow_le_pow_right'
nsmul_le_nsmul
→ nsmul_le_nsmul_left
pow_le_pow_of_le_one'
→ pow_le_pow_right_of_le_one'
nsmul_le_nsmul_of_nonpos
→ nsmul_le_nsmul_left_of_nonpos
le_of_pow_le_pow'
→ le_of_pow_le_pow_left'
le_of_nsmul_le_nsmul'
→ le_of_nsmul_le_nsmul_right'
pow_le_pow_iff'
→ pow_le_pow_iff_right'
nsmul_le_nsmul_iff
→ nsmul_le_nsmul_iff_left
pow_lt_pow_iff'
→ pow_lt_pow_iff_right'
nsmul_lt_nsmul_iff
→ nsmul_lt_nsmul_iff_left
Data.Nat.Pow
Nat.pow_lt_pow_of_lt_left
→ Nat.pow_lt_pow_left
Nat.pow_le_iff_le_left
→ Nat.pow_le_pow_iff_left
Nat.pow_lt_iff_lt_left
→ Nat.pow_lt_pow_iff_left
pow_le_pow_iff_left
pow_lt_pow_iff_left
pow_right_injective
pow_right_inj
Nat.pow_le_pow_left
to have the correct name since Nat.pow_le_pow_of_le_left
is in Std.Nat.pow_le_pow_right
to have the correct name since Nat.pow_le_pow_of_le_right
is in Std.self_le_pow
was a duplicate of le_self_pow
.Nat.pow_lt_pow_of_lt_right
is defeq to pow_lt_pow_right
.Nat.pow_right_strictMono
is defeq to pow_right_strictMono
.Nat.pow_le_iff_le_right
is defeq to pow_le_pow_iff_right
.Nat.pow_lt_iff_lt_right
is defeq to pow_lt_pow_iff_right
.0 < n
or 1 ≤ n
to n ≠ 0
.Nat
lemmas have been protected
.@@ -333,7 +333,7 @@ theorem Prime.properDivisors {p : ℕ} (pp : p.Prime) : properDivisors p = {1} :
#align nat.prime.proper_divisors Nat.Prime.properDivisors
theorem divisors_prime_pow {p : ℕ} (pp : p.Prime) (k : ℕ) :
- divisors (p ^ k) = (Finset.range (k + 1)).map ⟨(p ^ ·), pow_right_injective pp.two_le⟩ := by
+ divisors (p ^ k) = (Finset.range (k + 1)).map ⟨(p ^ ·), Nat.pow_right_injective pp.two_le⟩ := by
ext a
rw [mem_divisors_prime_pow pp]
simp [Nat.lt_succ, eq_comm]
@@ -438,15 +438,15 @@ theorem mem_properDivisors_prime_pow {p : ℕ} (pp : p.Prime) (k : ℕ) {x : ℕ
intro a
constructor <;> intro h
· rcases h with ⟨_h_left, rfl, h_right⟩
- rw [pow_lt_pow_iff pp.one_lt] at h_right
+ rw [pow_lt_pow_iff_right pp.one_lt] at h_right
exact ⟨h_right, by rfl⟩
· rcases h with ⟨h_left, rfl⟩
- rw [pow_lt_pow_iff pp.one_lt]
+ rw [pow_lt_pow_iff_right pp.one_lt]
simp [h_left, le_of_lt]
#align nat.mem_proper_divisors_prime_pow Nat.mem_properDivisors_prime_pow
theorem properDivisors_prime_pow {p : ℕ} (pp : p.Prime) (k : ℕ) :
- properDivisors (p ^ k) = (Finset.range k).map ⟨HPow.hPow p, pow_right_injective pp.two_le⟩ := by
+ properDivisors (p ^ k) = (Finset.range k).map ⟨(p ^ ·), Nat.pow_right_injective pp.two_le⟩ := by
ext a
simp only [mem_properDivisors, Nat.isUnit_iff, mem_map, mem_range, Function.Embedding.coeFn_mk,
pow_eq]
@@ -445,9 +445,8 @@ theorem mem_properDivisors_prime_pow {p : ℕ} (pp : p.Prime) (k : ℕ) {x : ℕ
simp [h_left, le_of_lt]
#align nat.mem_proper_divisors_prime_pow Nat.mem_properDivisors_prime_pow
--- Porting note: Specified pow to Nat.pow
theorem properDivisors_prime_pow {p : ℕ} (pp : p.Prime) (k : ℕ) :
- properDivisors (p ^ k) = (Finset.range k).map ⟨Nat.pow p, pow_right_injective pp.two_le⟩ := by
+ properDivisors (p ^ k) = (Finset.range k).map ⟨HPow.hPow p, pow_right_injective pp.two_le⟩ := by
ext a
simp only [mem_properDivisors, Nat.isUnit_iff, mem_map, mem_range, Function.Embedding.coeFn_mk,
pow_eq]
@@ -409,7 +409,7 @@ theorem properDivisors_eq_singleton_one_iff_prime : n.properDivisors = {1} ↔ n
have := Nat.le_of_dvd ?_ hdvd
· simp [hdvd, this]
exact (le_iff_eq_or_lt.mp this).symm
- · by_contra'
+ · by_contra!
simp only [nonpos_iff_eq_zero.mp this, this] at h
contradiction
· exact fun h => Prime.properDivisors h
∃ j ≤ k, _
instead of ∃ j (_ : j ≤ k)
in Nat.mem_divisors_prime_pow
;Nat.divisors_prime_pow
.@@ -318,9 +318,8 @@ theorem perfect_iff_sum_divisors_eq_two_mul (h : 0 < n) :
#align nat.perfect_iff_sum_divisors_eq_two_mul Nat.perfect_iff_sum_divisors_eq_two_mul
theorem mem_divisors_prime_pow {p : ℕ} (pp : p.Prime) (k : ℕ) {x : ℕ} :
- x ∈ divisors (p ^ k) ↔ ∃ (j : ℕ) (_ : j ≤ k), x = p ^ j := by
+ x ∈ divisors (p ^ k) ↔ ∃ j ≤ k, x = p ^ j := by
rw [mem_divisors, Nat.dvd_prime_pow pp, and_iff_left (ne_of_gt (pow_pos pp.pos k))]
- simp
#align nat.mem_divisors_prime_pow Nat.mem_divisors_prime_pow
theorem Prime.divisors {p : ℕ} (pp : p.Prime) : divisors p = {1, p} := by
@@ -333,18 +332,11 @@ theorem Prime.properDivisors {p : ℕ} (pp : p.Prime) : properDivisors p = {1} :
pp.divisors, pair_comm, erase_insert fun con => pp.ne_one (mem_singleton.1 con)]
#align nat.prime.proper_divisors Nat.Prime.properDivisors
--- Porting note: Specified pow to Nat.pow
theorem divisors_prime_pow {p : ℕ} (pp : p.Prime) (k : ℕ) :
- divisors (p ^ k) = (Finset.range (k + 1)).map ⟨Nat.pow p, pow_right_injective pp.two_le⟩ := by
+ divisors (p ^ k) = (Finset.range (k + 1)).map ⟨(p ^ ·), pow_right_injective pp.two_le⟩ := by
ext a
- simp only [mem_divisors, mem_map, mem_range, lt_succ_iff, Function.Embedding.coeFn_mk, Nat.pow_eq,
- mem_divisors_prime_pow pp k]
- have := mem_divisors_prime_pow pp k (x := a)
- rw [mem_divisors] at this
- rw [this]
- refine ⟨?_, ?_⟩
- · intro h; rcases h with ⟨x, hx, hap⟩; use x; tauto
- · tauto
+ rw [mem_divisors_prime_pow pp]
+ simp [Nat.lt_succ, eq_comm]
#align nat.divisors_prime_pow Nat.divisors_prime_pow
theorem divisors_injective : Function.Injective divisors :=
The function Nat.divisors
as a multiplicative homomorphism ℕ →* Finset ℕ
.
This result is in a new file Data/Finset/NatDivisors
, to avoid adding imports and/or lengthening existing files.
Co-authored-by: Yury G. Kudryashov <urkud@urkud.name>
@@ -201,6 +201,13 @@ theorem one_mem_properDivisors_iff_one_lt : 1 ∈ n.properDivisors ↔ 1 < n :=
rw [mem_properDivisors, and_iff_right (one_dvd _)]
#align nat.one_mem_proper_divisors_iff_one_lt Nat.one_mem_properDivisors_iff_one_lt
+@[simp]
+lemma sup_divisors_id (n : ℕ) : n.divisors.sup id = n := by
+ refine le_antisymm (Finset.sup_le fun _ ↦ divisor_le) ?_
+ rcases Decidable.eq_or_ne n 0 with rfl | hn
+ · apply zero_le
+ · exact Finset.le_sup (f := id) <| mem_divisors_self n hn
+
@[simp]
theorem divisorsAntidiagonal_zero : divisorsAntidiagonal 0 = ∅ := by
ext
@@ -340,6 +347,13 @@ theorem divisors_prime_pow {p : ℕ} (pp : p.Prime) (k : ℕ) :
· tauto
#align nat.divisors_prime_pow Nat.divisors_prime_pow
+theorem divisors_injective : Function.Injective divisors :=
+ Function.LeftInverse.injective sup_divisors_id
+
+@[simp]
+theorem divisors_inj {a b : ℕ} : a.divisors = b.divisors ↔ a = b :=
+ ⟨fun x => divisors_injective x, congrArg divisors⟩
+
theorem eq_properDivisors_of_subset_of_sum_eq_sum {s : Finset ℕ} (hsub : s ⊆ n.properDivisors) :
((∑ x in s, x) = ∑ x in n.properDivisors, x) → s = n.properDivisors := by
cases n
This is the supremum of
along with some minor fixes from failures on nightly-testing as Mathlib master
is merged into it.
Note that some PRs for changes that are already compatible with the current toolchain and will be necessary have already been split out: #8380.
I am hopeful that in future we will be able to progressively merge adaptation PRs into a bump/v4.X.0
branch, so we never end up with a "big merge" like this. However one of these adaptation PRs (#8056) predates my new scheme for combined CI, and it wasn't possible to keep that PR viable in the meantime.
In particular this includes adjustments for the Lean PRs
We can get rid of all the
local macro_rules | `($x ^ $y) => `(HPow.hPow $x $y) -- Porting note: See issue [lean4#2220](https://github.com/leanprover/lean4/pull/2220)
macros across Mathlib (and in any projects that want to write natural number powers of reals).
Changes the default behaviour of simp
to (config := {decide := false})
. This makes simp
(and consequentially norm_num
) less powerful, but also more consistent, and less likely to blow up in long failures. This requires a variety of changes: changing some previously by simp
or norm_num
to decide
or rfl
, or adding (config := {decide := true})
.
This changed the behaviour of simp
so that simp [f]
will only unfold "fully applied" occurrences of f
. The old behaviour can be recovered with simp (config := { unfoldPartialApp := true })
. We may in future add a syntax for this, e.g. simp [!f]
; please provide feedback! In the meantime, we have made the following changes:
(config := { unfoldPartialApp := true })
in some places, to recover the old behaviour@[eqns]
to manually adjust the equation lemmas for a particular definition, recovering the old behaviour just for that definition. See #8371, where we do this for Function.comp
and Function.flip
.This change in Lean may require further changes down the line (e.g. adding the !f
syntax, and/or upstreaming the special treatment for Function.comp
and Function.flip
, and/or removing this special treatment). Please keep an open and skeptical mind about these changes!
Co-authored-by: leanprover-community-mathlib4-bot <leanprover-community-mathlib4-bot@users.noreply.github.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Mauricio Collares <mauricio@collares.org>
@@ -404,7 +404,8 @@ theorem properDivisors_eq_singleton_one_iff_prime : n.properDivisors = {1} ↔ n
· simp [hdvd, this]
exact (le_iff_eq_or_lt.mp this).symm
· by_contra'
- simp [nonpos_iff_eq_zero.mp this, this] at h
+ simp only [nonpos_iff_eq_zero.mp this, this] at h
+ contradiction
· exact fun h => Prime.properDivisors h
#align nat.proper_divisors_eq_singleton_one_iff_prime Nat.properDivisors_eq_singleton_one_iff_prime
Also fix implicitness of arguments to Finset.sum_singleton
.
@@ -373,10 +373,8 @@ theorem sum_properDivisors_dvd (h : (∑ x in n.properDivisors, x) ∣ n) :
have hlt : ∑ x in n.succ.succ.properDivisors, x < n.succ.succ :=
lt_of_le_of_ne (Nat.le_of_dvd (Nat.succ_pos _) h) ne_n
symm
- rw [← mem_singleton,
- eq_properDivisors_of_subset_of_sum_eq_sum
- (singleton_subset_iff.2 (mem_properDivisors.2 ⟨h, hlt⟩)) sum_singleton,
- mem_properDivisors]
+ rw [← mem_singleton, eq_properDivisors_of_subset_of_sum_eq_sum (singleton_subset_iff.2
+ (mem_properDivisors.2 ⟨h, hlt⟩)) (sum_singleton _ _), mem_properDivisors]
refine' ⟨one_dvd _, Nat.succ_lt_succ (Nat.succ_pos _)⟩
#align nat.sum_proper_divisors_dvd Nat.sum_properDivisors_dvd
@@ -416,13 +414,13 @@ theorem sum_properDivisors_eq_one_iff_prime : ∑ x in n.properDivisors, x = 1
· cases n
· simp [Nat.not_prime_one]
· rw [← properDivisors_eq_singleton_one_iff_prime]
- refine' ⟨fun h => _, fun h => h.symm ▸ sum_singleton⟩
+ refine' ⟨fun h => _, fun h => h.symm ▸ sum_singleton _ _⟩
rw [@eq_comm (Finset ℕ) _ _]
apply
eq_properDivisors_of_subset_of_sum_eq_sum
(singleton_subset_iff.2
(one_mem_properDivisors_iff_one_lt.2 (succ_lt_succ (Nat.succ_pos _))))
- (Eq.trans sum_singleton h.symm)
+ ((sum_singleton _ _).trans h.symm)
#align nat.sum_proper_divisors_eq_one_iff_prime Nat.sum_properDivisors_eq_one_iff_prime
theorem mem_properDivisors_prime_pow {p : ℕ} (pp : p.Prime) (k : ℕ) {x : ℕ} :
Add lemmas about filtering the Finset
s of divisors or factors by divisibility. These two results came up while developing API for the Finset
of tuples with a fixed product n
.
@@ -154,6 +154,12 @@ theorem divisors_subset_properDivisors {m : ℕ} (hzero : n ≠ 0) (h : m ∣ n)
(lt_of_le_of_ne (divisor_le (Nat.mem_divisors.2 ⟨h, hzero⟩)) hdiff)⟩
#align nat.divisors_subset_proper_divisors Nat.divisors_subset_properDivisors
+lemma divisors_filter_dvd_of_dvd {n m : ℕ} (hn : n ≠ 0) (hm : m ∣ n) :
+ (n.divisors.filter (· ∣ m)) = m.divisors := by
+ ext k
+ simp_rw [mem_filter, mem_divisors]
+ exact ⟨fun ⟨_, hkm⟩ ↦ ⟨hkm, ne_zero_of_dvd_ne_zero hn hm⟩, fun ⟨hk, _⟩ ↦ ⟨⟨hk.trans hm, hn⟩, hk⟩⟩
+
@[simp]
theorem divisors_zero : divisors 0 = ∅ := by
ext
@@ -487,6 +493,11 @@ theorem prime_divisors_eq_to_filter_divisors_prime (n : ℕ) :
simpa [hn, hn.ne', mem_factors] using and_comm
#align nat.prime_divisors_eq_to_filter_divisors_prime Nat.prime_divisors_eq_to_filter_divisors_prime
+lemma prime_divisors_filter_dvd_of_dvd {m n : ℕ} (hn : n ≠ 0) (hmn : m ∣ n) :
+ n.factors.toFinset.filter (· ∣ m) = m.factors.toFinset := by
+ simp_rw [prime_divisors_eq_to_filter_divisors_prime, filter_comm,
+ divisors_filter_dvd_of_dvd hn hmn]
+
@[simp]
theorem image_div_divisors_eq_divisors (n : ℕ) :
image (fun x : ℕ => n / x) n.divisors = n.divisors := by
Type _
and Sort _
(#6499)
We remove all possible occurences of Type _
and Sort _
in favor of Type*
and Sort*
.
This has nice performance benefits.
@@ -375,13 +375,13 @@ theorem sum_properDivisors_dvd (h : (∑ x in n.properDivisors, x) ∣ n) :
#align nat.sum_proper_divisors_dvd Nat.sum_properDivisors_dvd
@[to_additive (attr := simp)]
-theorem Prime.prod_properDivisors {α : Type _} [CommMonoid α] {p : ℕ} {f : ℕ → α} (h : p.Prime) :
+theorem Prime.prod_properDivisors {α : Type*} [CommMonoid α] {p : ℕ} {f : ℕ → α} (h : p.Prime) :
∏ x in p.properDivisors, f x = f 1 := by simp [h.properDivisors]
#align nat.prime.prod_proper_divisors Nat.Prime.prod_properDivisors
#align nat.prime.sum_proper_divisors Nat.Prime.sum_properDivisors
@[to_additive (attr := simp)]
-theorem Prime.prod_divisors {α : Type _} [CommMonoid α] {p : ℕ} {f : ℕ → α} (h : p.Prime) :
+theorem Prime.prod_divisors {α : Type*} [CommMonoid α] {p : ℕ} {f : ℕ → α} (h : p.Prime) :
∏ x in p.divisors, f x = f p * f 1 := by
rw [← cons_self_properDivisors h.ne_zero, prod_cons, h.prod_properDivisors]
#align nat.prime.prod_divisors Nat.Prime.prod_divisors
@@ -449,21 +449,21 @@ theorem properDivisors_prime_pow {p : ℕ} (pp : p.Prime) (k : ℕ) :
#align nat.proper_divisors_prime_pow Nat.properDivisors_prime_pow
@[to_additive (attr := simp)]
-theorem prod_properDivisors_prime_pow {α : Type _} [CommMonoid α] {k p : ℕ} {f : ℕ → α}
+theorem prod_properDivisors_prime_pow {α : Type*} [CommMonoid α] {k p : ℕ} {f : ℕ → α}
(h : p.Prime) : (∏ x in (p ^ k).properDivisors, f x) = ∏ x in range k, f (p ^ x) := by
simp [h, properDivisors_prime_pow]
#align nat.prod_proper_divisors_prime_pow Nat.prod_properDivisors_prime_pow
#align nat.sum_proper_divisors_prime_nsmul Nat.sum_properDivisors_prime_nsmul
@[to_additive (attr := simp) sum_divisors_prime_pow]
-theorem prod_divisors_prime_pow {α : Type _} [CommMonoid α] {k p : ℕ} {f : ℕ → α} (h : p.Prime) :
+theorem prod_divisors_prime_pow {α : Type*} [CommMonoid α] {k p : ℕ} {f : ℕ → α} (h : p.Prime) :
(∏ x in (p ^ k).divisors, f x) = ∏ x in range (k + 1), f (p ^ x) := by
simp [h, divisors_prime_pow]
#align nat.prod_divisors_prime_pow Nat.prod_divisors_prime_pow
#align nat.sum_divisors_prime_pow Nat.sum_divisors_prime_pow
@[to_additive]
-theorem prod_divisorsAntidiagonal {M : Type _} [CommMonoid M] (f : ℕ → ℕ → M) {n : ℕ} :
+theorem prod_divisorsAntidiagonal {M : Type*} [CommMonoid M] (f : ℕ → ℕ → M) {n : ℕ} :
∏ i in n.divisorsAntidiagonal, f i.1 i.2 = ∏ i in n.divisors, f i (n / i) := by
rw [← map_div_right_divisors, Finset.prod_map]
rfl
@@ -471,7 +471,7 @@ theorem prod_divisorsAntidiagonal {M : Type _} [CommMonoid M] (f : ℕ → ℕ
#align nat.sum_divisors_antidiagonal Nat.sum_divisorsAntidiagonal
@[to_additive]
-theorem prod_divisorsAntidiagonal' {M : Type _} [CommMonoid M] (f : ℕ → ℕ → M) {n : ℕ} :
+theorem prod_divisorsAntidiagonal' {M : Type*} [CommMonoid M] (f : ℕ → ℕ → M) {n : ℕ} :
∏ i in n.divisorsAntidiagonal, f i.1 i.2 = ∏ i in n.divisors, f (n / i) i := by
rw [← map_swap_divisorsAntidiagonal, Finset.prod_map]
exact prod_divisorsAntidiagonal fun i j => f j i
@@ -509,7 +509,7 @@ theorem image_div_divisors_eq_divisors (n : ℕ) :
Left-hand side does not simplify, when using the simp lemma on itself.
This usually means that it will never apply. -/
@[to_additive sum_div_divisors]
-theorem prod_div_divisors {α : Type _} [CommMonoid α] (n : ℕ) (f : ℕ → α) :
+theorem prod_div_divisors {α : Type*} [CommMonoid α] (n : ℕ) (f : ℕ → α) :
(∏ d in n.divisors, f (n / d)) = n.divisors.prod f := by
by_cases hn : n = 0; · simp [hn]
rw [← prod_image]
@@ -2,16 +2,13 @@
Copyright (c) 2020 Aaron Anderson. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Aaron Anderson
-
-! This file was ported from Lean 3 source module number_theory.divisors
-! leanprover-community/mathlib commit e8638a0fcaf73e4500469f368ef9494e495099b3
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
-/
import Mathlib.Algebra.BigOperators.Order
import Mathlib.Data.Nat.Interval
import Mathlib.Data.Nat.Factors
+#align_import number_theory.divisors from "leanprover-community/mathlib"@"e8638a0fcaf73e4500469f368ef9494e495099b3"
+
/-!
# Divisor Finsets
∑'
precedence (#5615)
∑
, ∏
and variants).([^a-zA-Zα-ωΑ-Ω'𝓝ℳ₀𝕂ₛ)]) \(([∑∏][^()∑∏]*,[^()∑∏:]*)\) ([⊂⊆=<≤])
replaced by $1 $2 $3
@@ -283,7 +283,7 @@ theorem map_div_left_divisors :
#align nat.map_div_left_divisors Nat.map_div_left_divisors
theorem sum_divisors_eq_sum_properDivisors_add_self :
- (∑ i in divisors n, i) = (∑ i in properDivisors n, i) + n := by
+ ∑ i in divisors n, i = (∑ i in properDivisors n, i) + n := by
rcases Decidable.eq_or_ne n 0 with (rfl | hn)
· simp
· rw [← cons_self_properDivisors hn, Finset.sum_cons, add_comm]
@@ -292,15 +292,15 @@ theorem sum_divisors_eq_sum_properDivisors_add_self :
/-- `n : ℕ` is perfect if and only the sum of the proper divisors of `n` is `n` and `n`
is positive. -/
def Perfect (n : ℕ) : Prop :=
- (∑ i in properDivisors n, i) = n ∧ 0 < n
+ ∑ i in properDivisors n, i = n ∧ 0 < n
#align nat.perfect Nat.Perfect
-theorem perfect_iff_sum_properDivisors (h : 0 < n) : Perfect n ↔ (∑ i in properDivisors n, i) = n :=
+theorem perfect_iff_sum_properDivisors (h : 0 < n) : Perfect n ↔ ∑ i in properDivisors n, i = n :=
and_iff_left h
#align nat.perfect_iff_sum_proper_divisors Nat.perfect_iff_sum_properDivisors
theorem perfect_iff_sum_divisors_eq_two_mul (h : 0 < n) :
- Perfect n ↔ (∑ i in divisors n, i) = 2 * n := by
+ Perfect n ↔ ∑ i in divisors n, i = 2 * n := by
rw [perfect_iff_sum_properDivisors h, sum_divisors_eq_sum_properDivisors_add_self, two_mul]
constructor <;> intro h
· rw [h]
@@ -359,7 +359,7 @@ theorem eq_properDivisors_of_subset_of_sum_eq_sum {s : Finset ℕ} (hsub : s ⊆
#align nat.eq_proper_divisors_of_subset_of_sum_eq_sum Nat.eq_properDivisors_of_subset_of_sum_eq_sum
theorem sum_properDivisors_dvd (h : (∑ x in n.properDivisors, x) ∣ n) :
- (∑ x in n.properDivisors, x) = 1 ∨ (∑ x in n.properDivisors, x) = n := by
+ ∑ x in n.properDivisors, x = 1 ∨ ∑ x in n.properDivisors, x = n := by
cases' n with n
· simp
· cases' n with n
@@ -367,7 +367,7 @@ theorem sum_properDivisors_dvd (h : (∑ x in n.properDivisors, x) ∣ n) :
simp
· rw [or_iff_not_imp_right]
intro ne_n
- have hlt : (∑ x in n.succ.succ.properDivisors, x) < n.succ.succ :=
+ have hlt : ∑ x in n.succ.succ.properDivisors, x < n.succ.succ :=
lt_of_le_of_ne (Nat.le_of_dvd (Nat.succ_pos _) h) ne_n
symm
rw [← mem_singleton,
@@ -379,13 +379,13 @@ theorem sum_properDivisors_dvd (h : (∑ x in n.properDivisors, x) ∣ n) :
@[to_additive (attr := simp)]
theorem Prime.prod_properDivisors {α : Type _} [CommMonoid α] {p : ℕ} {f : ℕ → α} (h : p.Prime) :
- (∏ x in p.properDivisors, f x) = f 1 := by simp [h.properDivisors]
+ ∏ x in p.properDivisors, f x = f 1 := by simp [h.properDivisors]
#align nat.prime.prod_proper_divisors Nat.Prime.prod_properDivisors
#align nat.prime.sum_proper_divisors Nat.Prime.sum_properDivisors
@[to_additive (attr := simp)]
theorem Prime.prod_divisors {α : Type _} [CommMonoid α] {p : ℕ} {f : ℕ → α} (h : p.Prime) :
- (∏ x in p.divisors, f x) = f p * f 1 := by
+ ∏ x in p.divisors, f x = f p * f 1 := by
rw [← cons_self_properDivisors h.ne_zero, prod_cons, h.prod_properDivisors]
#align nat.prime.prod_divisors Nat.Prime.prod_divisors
#align nat.prime.sum_divisors Nat.Prime.sum_divisors
@@ -407,7 +407,7 @@ theorem properDivisors_eq_singleton_one_iff_prime : n.properDivisors = {1} ↔ n
· exact fun h => Prime.properDivisors h
#align nat.proper_divisors_eq_singleton_one_iff_prime Nat.properDivisors_eq_singleton_one_iff_prime
-theorem sum_properDivisors_eq_one_iff_prime : (∑ x in n.properDivisors, x) = 1 ↔ n.Prime := by
+theorem sum_properDivisors_eq_one_iff_prime : ∑ x in n.properDivisors, x = 1 ↔ n.Prime := by
cases' n with n
· simp [Nat.not_prime_zero]
· cases n
@@ -467,7 +467,7 @@ theorem prod_divisors_prime_pow {α : Type _} [CommMonoid α] {k p : ℕ} {f :
@[to_additive]
theorem prod_divisorsAntidiagonal {M : Type _} [CommMonoid M] (f : ℕ → ℕ → M) {n : ℕ} :
- (∏ i in n.divisorsAntidiagonal, f i.1 i.2) = ∏ i in n.divisors, f i (n / i) := by
+ ∏ i in n.divisorsAntidiagonal, f i.1 i.2 = ∏ i in n.divisors, f i (n / i) := by
rw [← map_div_right_divisors, Finset.prod_map]
rfl
#align nat.prod_divisors_antidiagonal Nat.prod_divisorsAntidiagonal
@@ -475,7 +475,7 @@ theorem prod_divisorsAntidiagonal {M : Type _} [CommMonoid M] (f : ℕ → ℕ
@[to_additive]
theorem prod_divisorsAntidiagonal' {M : Type _} [CommMonoid M] (f : ℕ → ℕ → M) {n : ℕ} :
- (∏ i in n.divisorsAntidiagonal, f i.1 i.2) = ∏ i in n.divisors, f (n / i) i := by
+ ∏ i in n.divisorsAntidiagonal, f i.1 i.2 = ∏ i in n.divisors, f (n / i) i := by
rw [← map_swap_divisorsAntidiagonal, Finset.prod_map]
exact prod_divisorsAntidiagonal fun i j => f j i
#align nat.prod_divisors_antidiagonal' Nat.prod_divisorsAntidiagonal'
SProd
to implement overloaded notation · ×ˢ ·
(#4200)
Currently, the following notations are changed from · ×ˢ ·
because Lean 4 can't deal with ambiguous notations.
| Definition | Notation |
| :
Co-authored-by: Jeremy Tan Jie Rui <reddeloostw@gmail.com> Co-authored-by: Kyle Miller <kmill31415@gmail.com> Co-authored-by: Chris Hughes <chrishughes24@gmail.com>
@@ -54,7 +54,7 @@ def properDivisors : Finset ℕ :=
/-- `divisorsAntidiagonal n` is the `Finset` of pairs `(x,y)` such that `x * y = n`.
As a special case, `divisorsAntidiagonal 0 = ∅`. -/
def divisorsAntidiagonal : Finset (ℕ × ℕ) :=
- Finset.filter (fun x => x.fst * x.snd = n) (Ico 1 (n + 1) ×ᶠ Ico 1 (n + 1))
+ Finset.filter (fun x => x.fst * x.snd = n) (Ico 1 (n + 1) ×ˢ Ico 1 (n + 1))
#align nat.divisors_antidiagonal Nat.divisorsAntidiagonal
variable {n}
fix-comments.py
on all files.@@ -23,7 +23,7 @@ Let `n : ℕ`. All of the following definitions are in the `Nat` namespace:
* `divisors n` is the `Finset` of natural numbers that divide `n`.
* `properDivisors n` is the `Finset` of natural numbers that divide `n`, other than `n`.
* `divisorsAntidiagonal n` is the `Finset` of pairs `(x,y)` such that `x * y = n`.
- * `perfect n` is true when `n` is positive and the sum of `properDivisors n` is `n`.
+ * `Perfect n` is true when `n` is positive and the sum of `properDivisors n` is `n`.
## Implementation details
* `divisors 0`, `properDivisors 0`, and `divisorsAntidiagonal 0` are defined to be `∅`.
This PR fixes two things:
align
statements for definitions and theorems and instances that are separated by two newlines from the relevant declaration (s/\n\n#align/\n#align
). This is often seen in the mathport output after ending calc
blocks.#align
statements. (This was needed for a script I wrote for #3630.)@@ -287,9 +287,7 @@ theorem sum_divisors_eq_sum_properDivisors_add_self :
rcases Decidable.eq_or_ne n 0 with (rfl | hn)
· simp
· rw [← cons_self_properDivisors hn, Finset.sum_cons, add_comm]
-#align
- nat.sum_divisors_eq_sum_proper_divisors_add_self
- Nat.sum_divisors_eq_sum_properDivisors_add_self
+#align nat.sum_divisors_eq_sum_proper_divisors_add_self Nat.sum_divisors_eq_sum_properDivisors_add_self
/-- `n : ℕ` is perfect if and only the sum of the proper divisors of `n` is `n` and `n`
is positive. -/
Match https://github.com/leanprover-community/mathlib/pull/18698 and a bit of https://github.com/leanprover-community/mathlib/pull/18785.
algebra.divisibility.basic
@70d50ecfd4900dd6d328da39ab7ebd516abe4025
..e8638a0fcaf73e4500469f368ef9494e495099b3
algebra.euclidean_domain.basic
@655994e298904d7e5bbd1e18c95defd7b543eb94
..e8638a0fcaf73e4500469f368ef9494e495099b3
algebra.group.units
@369525b73f229ccd76a6ec0e0e0bf2be57599768
..e8638a0fcaf73e4500469f368ef9494e495099b3
algebra.group_with_zero.basic
@2196ab363eb097c008d4497125e0dde23fb36db2
..e8638a0fcaf73e4500469f368ef9494e495099b3
algebra.group_with_zero.divisibility
@f1a2caaf51ef593799107fe9a8d5e411599f3996
..e8638a0fcaf73e4500469f368ef9494e495099b3
algebra.group_with_zero.units.basic
@70d50ecfd4900dd6d328da39ab7ebd516abe4025
..df5e9937a06fdd349fc60106f54b84d47b1434f0
algebra.order.monoid.canonical.defs
@de87d5053a9fe5cbde723172c0fb7e27e7436473
..e8638a0fcaf73e4500469f368ef9494e495099b3
algebra.ring.divisibility
@f1a2caaf51ef593799107fe9a8d5e411599f3996
..e8638a0fcaf73e4500469f368ef9494e495099b3
data.int.dvd.basic
@e1bccd6e40ae78370f01659715d3c948716e3b7e
..e8638a0fcaf73e4500469f368ef9494e495099b3
data.int.dvd.pow
@b3f25363ae62cb169e72cd6b8b1ac97bacf21ca7
..e8638a0fcaf73e4500469f368ef9494e495099b3
data.int.order.basic
@728baa2f54e6062c5879a3e397ac6bac323e506f
..e8638a0fcaf73e4500469f368ef9494e495099b3
data.nat.gcd.basic
@a47cda9662ff3925c6df271090b5808adbca5b46
..e8638a0fcaf73e4500469f368ef9494e495099b3
data.nat.order.basic
@26f081a2fb920140ed5bc5cc5344e84bcc7cb2b2
..e8638a0fcaf73e4500469f368ef9494e495099b3
data.nat.order.lemmas
@2258b40dacd2942571c8ce136215350c702dc78f
..e8638a0fcaf73e4500469f368ef9494e495099b3
group_theory.perm.cycle.basic
@92ca63f0fb391a9ca5f22d2409a6080e786d99f7
..e8638a0fcaf73e4500469f368ef9494e495099b3
number_theory.divisors
@f7fc89d5d5ff1db2d1242c7bb0e9062ce47ef47c
..e8638a0fcaf73e4500469f368ef9494e495099b3
number_theory.pythagorean_triples
@70fd9563a21e7b963887c9360bd29b2393e6225a
..e8638a0fcaf73e4500469f368ef9494e495099b3
number_theory.zsqrtd.basic
@7ec294687917cbc5c73620b4414ae9b5dd9ae1b4
..e8638a0fcaf73e4500469f368ef9494e495099b3
ring_theory.multiplicity
@ceb887ddf3344dab425292e497fa2af91498437c
..e8638a0fcaf73e4500469f368ef9494e495099b3
Co-authored-by: Jeremy Tan Jie Rui <reddeloostw@gmail.com>
@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
Authors: Aaron Anderson
! This file was ported from Lean 3 source module number_theory.divisors
-! leanprover-community/mathlib commit f7fc89d5d5ff1db2d1242c7bb0e9062ce47ef47c
+! leanprover-community/mathlib commit e8638a0fcaf73e4500469f368ef9494e495099b3
! Please do not edit these lines, except to modify the commit id
! if you have ported upstream changes.
-/
@@ -207,7 +207,7 @@ theorem divisorsAntidiagonal_zero : divisorsAntidiagonal 0 = ∅ := by
@[simp]
theorem divisorsAntidiagonal_one : divisorsAntidiagonal 1 = {(1, 1)} := by
ext
- simp [Nat.mul_eq_one_iff, Prod.ext_iff]
+ simp [mul_eq_one, Prod.ext_iff]
#align nat.divisors_antidiagonal_one Nat.divisorsAntidiagonal_one
/- Porting note: simpnf linter; added aux lemma below
@@ -19,7 +19,7 @@ This file defines sets of divisors of a natural number. This is particularly use
for defining Dirichlet convolution.
## Main Definitions
-Let `n : ℕ`. All of the following definitions are in the `nat` namespace:
+Let `n : ℕ`. All of the following definitions are in the `Nat` namespace:
* `divisors n` is the `Finset` of natural numbers that divide `n`.
* `properDivisors n` is the `Finset` of natural numbers that divide `n`, other than `n`.
* `divisorsAntidiagonal n` is the `Finset` of pairs `(x,y)` such that `x * y = n`.
@@ -34,11 +34,7 @@ divisors, perfect numbers
-/
-open Classical
-
-open BigOperators
-
-open Finset
+open BigOperators Classical Finset
namespace Nat
@@ -447,7 +443,8 @@ theorem mem_properDivisors_prime_pow {p : ℕ} (pp : p.Prime) (k : ℕ) {x : ℕ
theorem properDivisors_prime_pow {p : ℕ} (pp : p.Prime) (k : ℕ) :
properDivisors (p ^ k) = (Finset.range k).map ⟨Nat.pow p, pow_right_injective pp.two_le⟩ := by
ext a
- simp [pp, Nat.lt_succ_iff]
+ simp only [mem_properDivisors, Nat.isUnit_iff, mem_map, mem_range, Function.Embedding.coeFn_mk,
+ pow_eq]
have := mem_properDivisors_prime_pow pp k (x := a)
rw [mem_properDivisors] at this
rw [this]
@@ -498,7 +495,8 @@ theorem prime_divisors_eq_to_filter_divisors_prime (n : ℕ) :
@[simp]
theorem image_div_divisors_eq_divisors (n : ℕ) :
image (fun x : ℕ => n / x) n.divisors = n.divisors := by
- by_cases hn : n = 0; · simp [hn]
+ by_cases hn : n = 0
+ · simp [hn]
ext a
constructor
· rw [mem_image]
@@ -36,8 +36,7 @@ divisors, perfect numbers
open Classical
--- Porting note: Unknown namespace BigOperators
--- open BigOperators
+open BigOperators
open Finset
The unported dependencies are