data.nat.choose.dvd | Mathlib porting status

Changes since the initial port

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.

Changes in mathlib3

966e0cf0

(last sync)

refactor(number_theory/primorial): split the proof, golf it (#18238)

Add nat.prime.dvd_choose, delete less general dvd_choose_of_middling_prime.
Add primorial_pos, primorial_add, primorial_add_dvd, and primorial_add_le.
Golf some proofs.

Here is a proof of dvd_choose_of_middling_prime based on nat.prime.dvd_choose:

open nat

lemma dvd_choose_of_middling_prime (p : ℕ) (is_prime : nat.prime p) (m : ℕ)
  (p_big : m + 1 < p) (p_small : p ≤ 2 * m + 1) : p ∣ choose (2 * m + 1) (m + 1) :=
is_prime.dvd_choose p_big (by simpa [two_mul] using p_big.le) p_small

Forward-ported in leanprover-community/mathlib4#1770

Diff

@@ -19,26 +19,23 @@ open_locale nat
 
 namespace prime
 
-lemma dvd_choose_add {p a b : ℕ} (hap : a < p) (hbp : b < p) (h : p ≤ a + b)
-  (hp : prime p) : p ∣ choose (a + b) a :=
-have h₁ : p ∣ (a + b)!, from hp.dvd_factorial.2 h,
-have h₂ : ¬p ∣ a!, from mt hp.dvd_factorial.1 (not_le_of_gt hap),
-have h₃ : ¬p ∣ b!, from mt hp.dvd_factorial.1 (not_le_of_gt hbp),
-by
-  rw [← choose_mul_factorial_mul_factorial (le.intro rfl), mul_assoc, hp.dvd_mul, hp.dvd_mul,
-      add_tsub_cancel_left a b] at h₁;
-  exact h₁.resolve_right (not_or_distrib.2 ⟨h₂, h₃⟩)
-
-lemma dvd_choose_self {p k : ℕ} (hk : 0 < k) (hkp : k < p) (hp : prime p) :
-  p ∣ choose p k :=
+lemma dvd_choose_add {p a b : ℕ} (hp : prime p) (hap : a < p) (hbp : b < p) (h : p ≤ a + b) :
+  p ∣ choose (a + b) a :=
 begin
-  have r : k + (p - k) = p,
-    by rw [← add_tsub_assoc_of_le (nat.le_of_lt hkp) k, add_tsub_cancel_left],
-  have e : p ∣ choose (k + (p - k)) k,
-    by exact dvd_choose_add hkp (nat.sub_lt (hk.trans hkp) hk) (by rw r) hp,
-  rwa r at e,
+  have h₁ : p ∣ (a + b)!, from hp.dvd_factorial.2 h,
+  rw [← add_choose_mul_factorial_mul_factorial, ← choose_symm_add, hp.dvd_mul, hp.dvd_mul,
+    hp.dvd_factorial, hp.dvd_factorial] at h₁,
+  exact (h₁.resolve_right hbp.not_le).resolve_right hap.not_le
 end
 
+lemma dvd_choose {p a b : ℕ} (hp : prime p) (ha : a < p) (hab : b - a < p) (h : p ≤ b) :
+  p ∣ choose b a :=
+have a + (b - a) = b := nat.add_sub_of_le (ha.le.trans h),
+this ▸ hp.dvd_choose_add ha hab (this.symm ▸ h)
+
+lemma dvd_choose_self {p k : ℕ} (hp : prime p) (hk : k ≠ 0) (hkp : k < p) : p ∣ choose p k :=
+hp.dvd_choose hkp (nat.sub_lt ((zero_le _).trans_lt hkp) hk.bot_lt) le_rfl
+
 end prime
 
 end nat

207cfac9

(first ported)

Changes in mathlib3port

mathlib3

mathlib3port

966e0cf0

bump to nightly-2024-03-17-08

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

22f01ce4

Diff

@@ -28,7 +28,7 @@ theorem dvd_choose_add {p a b : ℕ} (hp : Prime p) (hap : a < p) (hbp : b < p)
   by
   have h₁ : p ∣ (a + b)! := hp.dvd_factorial.2 h
   rw [← add_choose_mul_factorial_mul_factorial, ← choose_symm_add, hp.dvd_mul, hp.dvd_mul,
-    hp.dvd_factorial, hp.dvd_factorial] at h₁ 
+    hp.dvd_factorial, hp.dvd_factorial] at h₁
   exact (h₁.resolve_right hbp.not_le).resolve_right hap.not_le
 #align nat.prime.dvd_choose_add Nat.Prime.dvd_choose_add
 -/

966e0cf0

bump to nightly-2023-09-24-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451

5655435f

Diff

@@ -3,8 +3,8 @@ Copyright (c) 2018 Chris Hughes. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Chris Hughes, Patrick Stevens
 -/
-import Mathbin.Data.Nat.Choose.Basic
-import Mathbin.Data.Nat.Prime
+import Data.Nat.Choose.Basic
+import Data.Nat.Prime
 
 #align_import data.nat.choose.dvd from "leanprover-community/mathlib"@"966e0cf0685c9cedf8a3283ac69eef4d5f2eaca2"

966e0cf0

bump to nightly-2023-07-20-09

mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345

9c56d0dd

Diff

@@ -2,15 +2,12 @@
 Copyright (c) 2018 Chris Hughes. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Chris Hughes, Patrick Stevens
-
-! This file was ported from Lean 3 source module data.nat.choose.dvd
-! leanprover-community/mathlib commit 966e0cf0685c9cedf8a3283ac69eef4d5f2eaca2
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Data.Nat.Choose.Basic
 import Mathbin.Data.Nat.Prime
 
+#align_import data.nat.choose.dvd from "leanprover-community/mathlib"@"966e0cf0685c9cedf8a3283ac69eef4d5f2eaca2"
+
 /-!
 # Divisibility properties of binomial coefficients

966e0cf0

bump to nightly-2023-06-01-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/cca40788df1b8755d5baf17ab2f27dacc2e17acb

b9c87c70

Diff

@@ -31,7 +31,7 @@ theorem dvd_choose_add {p a b : ℕ} (hp : Prime p) (hap : a < p) (hbp : b < p)
   by
   have h₁ : p ∣ (a + b)! := hp.dvd_factorial.2 h
   rw [← add_choose_mul_factorial_mul_factorial, ← choose_symm_add, hp.dvd_mul, hp.dvd_mul,
-    hp.dvd_factorial, hp.dvd_factorial] at h₁
+    hp.dvd_factorial, hp.dvd_factorial] at h₁ 
   exact (h₁.resolve_right hbp.not_le).resolve_right hap.not_le
 #align nat.prime.dvd_choose_add Nat.Prime.dvd_choose_add
 -/

966e0cf0

bump to nightly-2023-05-28-18

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

8d353152

Diff

@@ -21,7 +21,7 @@ import Mathbin.Data.Nat.Prime
 
 namespace Nat
 
-open Nat
+open scoped Nat
 
 namespace Prime

966e0cf0

bump to nightly-2023-02-21-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc

1107b979

Changes in mathlib4

mathlib3

mathlib4

966e0cf0

chore: script to replace headers with #align_import statements (#5979)

depends on: #5966

Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

89aa3a3b

Diff

@@ -2,15 +2,12 @@
 Copyright (c) 2018 Chris Hughes. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Chris Hughes, Patrick Stevens
-
-! This file was ported from Lean 3 source module data.nat.choose.dvd
-! leanprover-community/mathlib commit 966e0cf0685c9cedf8a3283ac69eef4d5f2eaca2
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Data.Nat.Choose.Basic
 import Mathlib.Data.Nat.Prime
 
+#align_import data.nat.choose.dvd from "leanprover-community/mathlib"@"966e0cf0685c9cedf8a3283ac69eef4d5f2eaca2"
+
 /-!
 # Divisibility properties of binomial coefficients
 -/

966e0cf0

chore: update SHAs, forward-port (#2498)

Also fix some module docstrings.

37358873

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Chris Hughes, Patrick Stevens
 
 ! This file was ported from Lean 3 source module data.nat.choose.dvd
-! leanprover-community/mathlib commit 207cfac9fcd06138865b5d04f7091e46d9320432
+! leanprover-community/mathlib commit 966e0cf0685c9cedf8a3283ac69eef4d5f2eaca2
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/

207cfac9

Feat: add Nat.Prime.dvd_choose (#1770)

This is a forward-port of leanprover-community/mathlib#18238

28fd8fdb

Diff

@@ -22,22 +22,23 @@ open Nat
 
 namespace Prime
 
-theorem dvd_choose_add {p a b : ℕ} (hap : a < p) (hbp : b < p) (h : p ≤ a + b) (hp : Prime p) :
+variable {p a b k : ℕ}
+
+theorem dvd_choose_add (hp : Prime p) (hap : a < p) (hbp : b < p) (h : p ≤ a + b) :
     p ∣ choose (a + b) a := by
   have h₁ : p ∣ (a + b)! := hp.dvd_factorial.2 h
-  have h₂ : ¬p ∣ a ! := mt hp.dvd_factorial.1 (not_le_of_gt hap)
-  have h₃ : ¬p ∣ b ! := mt hp.dvd_factorial.1 (not_le_of_gt hbp)
-  rw [← choose_mul_factorial_mul_factorial (le_add_right a b), mul_assoc,
-      hp.dvd_mul, hp.dvd_mul, add_tsub_cancel_left a b] at h₁
-  exact h₁.resolve_right (not_or.2 ⟨h₂, h₃⟩)
+  rw [← add_choose_mul_factorial_mul_factorial, ← choose_symm_add, hp.dvd_mul, hp.dvd_mul,
+    hp.dvd_factorial, hp.dvd_factorial] at h₁
+  exact (h₁.resolve_right hbp.not_le).resolve_right hap.not_le
 #align nat.prime.dvd_choose_add Nat.Prime.dvd_choose_add
 
-theorem dvd_choose_self {p k : ℕ} (hk : 0 < k) (hkp : k < p) (hp : Prime p) : p ∣ choose p k := by
-  have r : k + (p - k) = p := by
-    rw [← add_tsub_assoc_of_le (Nat.le_of_lt hkp) k, add_tsub_cancel_left]
-  have e : p ∣ choose (k + (p - k)) k :=
-    dvd_choose_add hkp (Nat.sub_lt (hk.trans hkp) hk) (by rw [r]) hp
-  rwa [r] at e
+lemma dvd_choose (hp : Prime p) (ha : a < p) (hab : b - a < p) (h : p ≤ b) : p ∣ choose b a :=
+  have : a + (b - a) = b := Nat.add_sub_of_le (ha.le.trans h)
+  this ▸ hp.dvd_choose_add ha hab (this.symm ▸ h)
+#align nat.prime.dvd_choose Nat.Prime.dvd_choose
+
+lemma dvd_choose_self (hp : Prime p) (hk : k ≠ 0) (hkp : k < p) : p ∣ choose p k :=
+  hp.dvd_choose hkp (sub_lt ((zero_le _).trans_lt hkp) hk.bot_lt) le_rfl
 #align nat.prime.dvd_choose_self Nat.Prime.dvd_choose_self
 
 end Prime

207cfac9

feat: port Data.Nat.Choose.Dvd (#1221)

really easy, mathport did 99% of the work, and the other 1% was done by the brilliant start_port script!

915b6b99

`data.nat.choose.dvd` ⟷ `Mathlib.Data.Nat.Choose.Dvd`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 3 + 142

data.nat.choose.dvd ⟷ Mathlib.Data.Nat.Choose.Dvd

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 3 + 142

`data.nat.choose.dvd` ⟷ `Mathlib.Data.Nat.Choose.Dvd`