data.nat.factors | 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

008205aa

(last sync)

Changes in mathlib3port

mathlib3

mathlib3port

327c3c0d

bump to nightly-2024-03-17-08

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

22f01ce4

Diff

@@ -63,7 +63,7 @@ theorem prime_of_mem_factors : ∀ {n p}, p ∈ factors n → Prime p
   | n@(k + 2) => fun p h =>
     let m := minFac n
     have : n / m < n := factors_lemma
-    have h₁ : p = m ∨ p ∈ factors (n / m) := (List.mem_cons _ _ _).1 (by rwa [factors] at h )
+    have h₁ : p = m ∨ p ∈ factors (n / m) := (List.mem_cons _ _ _).1 (by rwa [factors] at h)
     Or.cases_on h₁ (fun h₂ => h₂.symm ▸ minFac_prime (by decide)) prime_of_mem_factors
 #align nat.prime_of_mem_factors Nat.prime_of_mem_factors
 -/
@@ -86,7 +86,7 @@ theorem prod_factors : ∀ {n}, n ≠ 0 → List.prod (factors n) = n
       have h₁ : n / m ≠ 0 := fun h =>
         by
         have : n = 0 * m := (Nat.div_eq_iff_eq_mul_left (minFac_pos _) (minFac_dvd _)).1 h
-        rw [MulZeroClass.zero_mul] at this  <;> exact (show k + 2 ≠ 0 by decide) this
+        rw [MulZeroClass.zero_mul] at this <;> exact (show k + 2 ≠ 0 by decide) this
       rw [factors, List.prod_cons, prod_factors h₁, Nat.mul_div_cancel' (min_fac_dvd _)]
 #align nat.prod_factors Nat.prod_factors
 -/
@@ -150,7 +150,7 @@ theorem factors_eq_nil (n : ℕ) : n.factors = [] ↔ n = 0 ∨ n = 1 :=
   · rcases n with (_ | _ | n)
     · exact Or.inl rfl
     · exact Or.inr rfl
-    · rw [factors] at h ; injection h
+    · rw [factors] at h; injection h
   · rcases h with (rfl | rfl)
     · exact factors_zero
     · exact factors_one
@@ -195,7 +195,7 @@ theorem mem_factors {n p} (hn : n ≠ 0) : p ∈ factors n ↔ Prime p ∧ p ∣
 theorem le_of_mem_factors {n p : ℕ} (h : p ∈ n.factors) : p ≤ n :=
   by
   rcases n.eq_zero_or_pos with (rfl | hn)
-  · rw [factors_zero] at h ; cases h
+  · rw [factors_zero] at h; cases h
   · exact le_of_dvd hn (dvd_of_mem_factors h)
 #align nat.le_of_mem_factors Nat.le_of_mem_factors
 -/
@@ -208,7 +208,7 @@ theorem factors_unique {n : ℕ} {l : List ℕ} (h₁ : Prod l = n) (h₂ : ∀
   · rw [h₁]
     refine' (prod_factors _).symm
     rintro rfl
-    rw [prod_eq_zero_iff] at h₁ 
+    rw [prod_eq_zero_iff] at h₁
     exact Prime.ne_zero (h₂ 0 h₁) rfl
   · simp_rw [← prime_iff]; exact h₂
   · simp_rw [← prime_iff]; exact fun p => prime_of_mem_factors
@@ -244,7 +244,7 @@ theorem perm_factors_mul {a b : ℕ} (ha : a ≠ 0) (hb : b ≠ 0) :
   refine' (factors_unique _ _).symm
   · rw [List.prod_append, prod_factors ha, prod_factors hb]
   · intro p hp
-    rw [List.mem_append] at hp 
+    rw [List.mem_append] at hp
     cases hp <;> exact prime_of_mem_factors hp
 #align nat.perm_factors_mul Nat.perm_factors_mul
 -/

327c3c0d

bump to nightly-2023-11-05-06

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

acc3325f

Diff

@@ -366,7 +366,7 @@ theorem mem_factors_mul_right {p a b : ℕ} (hpb : p ∈ b.factors) (ha : a ≠
 theorem eq_two_pow_or_exists_odd_prime_and_dvd (n : ℕ) :
     (∃ k : ℕ, n = 2 ^ k) ∨ ∃ p, Nat.Prime p ∧ p ∣ n ∧ Odd p :=
   (eq_or_ne n 0).elim (fun hn => Or.inr ⟨3, prime_three, hn.symm ▸ dvd_zero 3, ⟨1, rfl⟩⟩) fun hn =>
-    or_iff_not_imp_right.mpr fun H =>
+    Classical.or_iff_not_imp_right.mpr fun H =>
       ⟨n.factors.length,
         eq_prime_pow_of_unique_prime_dvd hn fun p hprime hdvd =>
           hprime.eq_two_or_odd'.resolve_right fun hodd => H ⟨p, hprime, hdvd, hodd⟩⟩

327c3c0d

bump to nightly-2023-09-24-06

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

5655435f

Diff

@@ -3,9 +3,9 @@ Copyright (c) 2015 Microsoft Corporation. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Leonardo de Moura, Jeremy Avigad, Mario Carneiro
 -/
-import Mathbin.Data.Nat.Prime
-import Mathbin.Data.List.Prime
-import Mathbin.Data.List.Sort
+import Data.Nat.Prime
+import Data.List.Prime
+import Data.List.Sort
 import Mathbin.Tactic.NthRewrite.Default
 
 #align_import data.nat.factors from "leanprover-community/mathlib"@"327c3c0d9232d80e250dc8f65e7835b82b266ea5"

327c3c0d

bump to nightly-2023-09-20-06

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

e28e6964

Diff

@@ -251,7 +251,7 @@ theorem perm_factors_mul {a b : ℕ} (ha : a ≠ 0) (hb : b ≠ 0) :
 
 #print Nat.perm_factors_mul_of_coprime /-
 /-- For coprime `a` and `b`, the prime factors of `a * b` are the union of those of `a` and `b` -/
-theorem perm_factors_mul_of_coprime {a b : ℕ} (hab : coprime a b) :
+theorem perm_factors_mul_of_coprime {a b : ℕ} (hab : Coprime a b) :
     (a * b).factors ~ a.factors ++ b.factors :=
   by
   rcases a.eq_zero_or_pos with (rfl | ha)
@@ -322,7 +322,7 @@ theorem mem_factors_mul {a b : ℕ} (ha : a ≠ 0) (hb : b ≠ 0) {p : ℕ} :
 
 #print Nat.coprime_factors_disjoint /-
 /-- The sets of factors of coprime `a` and `b` are disjoint -/
-theorem coprime_factors_disjoint {a b : ℕ} (hab : a.coprime b) :
+theorem coprime_factors_disjoint {a b : ℕ} (hab : a.Coprime b) :
     List.Disjoint a.factors b.factors := by
   intro q hqa hqb
   apply not_prime_one
@@ -332,7 +332,7 @@ theorem coprime_factors_disjoint {a b : ℕ} (hab : a.coprime b) :
 -/
 
 #print Nat.mem_factors_mul_of_coprime /-
-theorem mem_factors_mul_of_coprime {a b : ℕ} (hab : coprime a b) (p : ℕ) :
+theorem mem_factors_mul_of_coprime {a b : ℕ} (hab : Coprime a b) (p : ℕ) :
     p ∈ (a * b).factors ↔ p ∈ a.factors ∪ b.factors :=
   by
   rcases a.eq_zero_or_pos with (rfl | ha)

327c3c0d

bump to nightly-2023-08-09-09

mathlib commit https://github.com/leanprover-community/mathlib/commit/32a7e535287f9c73f2e4d2aef306a39190f0b504

af9a0040

Diff

@@ -339,7 +339,7 @@ theorem mem_factors_mul_of_coprime {a b : ℕ} (hab : coprime a b) (p : ℕ) :
   · simp [(coprime_zero_left _).mp hab]
   rcases b.eq_zero_or_pos with (rfl | hb)
   · simp [(coprime_zero_right _).mp hab]
-  rw [mem_factors_mul ha.ne' hb.ne', List.mem_union]
+  rw [mem_factors_mul ha.ne' hb.ne', List.mem_union_iff]
 #align nat.mem_factors_mul_of_coprime Nat.mem_factors_mul_of_coprime
 -/

327c3c0d

bump to nightly-2023-08-02-01

mathlib commit https://github.com/leanprover-community/mathlib/commit/63721b2c3eba6c325ecf8ae8cca27155a4f6306f

7aca3f15

Diff

@@ -301,7 +301,7 @@ theorem dvd_of_factors_subperm {a b : ℕ} (ha : a ≠ 0) (h : a.factors <+~ b.f
   rcases a with (_ | _ | a)
   · exact (ha rfl).elim
   · exact one_dvd _
-  use (b.factors.diff a.succ.succ.factors).Prod
+  use(b.factors.diff a.succ.succ.factors).Prod
   nth_rw 1 [← Nat.prod_factors ha]
   rw [← List.prod_append,
     List.Perm.prod_eq <| List.subperm_append_diff_self_of_count_le <| list.subperm_ext_iff.mp h,

327c3c0d

bump to nightly-2023-07-20-09

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

9c56d0dd

Diff

@@ -2,17 +2,14 @@
 Copyright (c) 2015 Microsoft Corporation. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Leonardo de Moura, Jeremy Avigad, Mario Carneiro
-
-! This file was ported from Lean 3 source module data.nat.factors
-! leanprover-community/mathlib commit 327c3c0d9232d80e250dc8f65e7835b82b266ea5
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Data.Nat.Prime
 import Mathbin.Data.List.Prime
 import Mathbin.Data.List.Sort
 import Mathbin.Tactic.NthRewrite.Default
 
+#align_import data.nat.factors from "leanprover-community/mathlib"@"327c3c0d9232d80e250dc8f65e7835b82b266ea5"
+
 /-!
 # Prime numbers

327c3c0d

bump to nightly-2023-06-13-21

mathlib commit https://github.com/leanprover-community/mathlib/commit/9fb8964792b4237dac6200193a0d533f1b3f7423

829520ac

Diff

@@ -334,6 +334,7 @@ theorem coprime_factors_disjoint {a b : ℕ} (hab : a.coprime b) :
 #align nat.coprime_factors_disjoint Nat.coprime_factors_disjoint
 -/
 
+#print Nat.mem_factors_mul_of_coprime /-
 theorem mem_factors_mul_of_coprime {a b : ℕ} (hab : coprime a b) (p : ℕ) :
     p ∈ (a * b).factors ↔ p ∈ a.factors ∪ b.factors :=
   by
@@ -343,6 +344,7 @@ theorem mem_factors_mul_of_coprime {a b : ℕ} (hab : coprime a b) (p : ℕ) :
   · simp [(coprime_zero_right _).mp hab]
   rw [mem_factors_mul ha.ne' hb.ne', List.mem_union]
 #align nat.mem_factors_mul_of_coprime Nat.mem_factors_mul_of_coprime
+-/
 
 open List

327c3c0d

bump to nightly-2023-06-01-16

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

b9c87c70

Diff

@@ -66,7 +66,7 @@ theorem prime_of_mem_factors : ∀ {n p}, p ∈ factors n → Prime p
   | n@(k + 2) => fun p h =>
     let m := minFac n
     have : n / m < n := factors_lemma
-    have h₁ : p = m ∨ p ∈ factors (n / m) := (List.mem_cons _ _ _).1 (by rwa [factors] at h)
+    have h₁ : p = m ∨ p ∈ factors (n / m) := (List.mem_cons _ _ _).1 (by rwa [factors] at h )
     Or.cases_on h₁ (fun h₂ => h₂.symm ▸ minFac_prime (by decide)) prime_of_mem_factors
 #align nat.prime_of_mem_factors Nat.prime_of_mem_factors
 -/
@@ -89,7 +89,7 @@ theorem prod_factors : ∀ {n}, n ≠ 0 → List.prod (factors n) = n
       have h₁ : n / m ≠ 0 := fun h =>
         by
         have : n = 0 * m := (Nat.div_eq_iff_eq_mul_left (minFac_pos _) (minFac_dvd _)).1 h
-        rw [MulZeroClass.zero_mul] at this <;> exact (show k + 2 ≠ 0 by decide) this
+        rw [MulZeroClass.zero_mul] at this  <;> exact (show k + 2 ≠ 0 by decide) this
       rw [factors, List.prod_cons, prod_factors h₁, Nat.mul_div_cancel' (min_fac_dvd _)]
 #align nat.prod_factors Nat.prod_factors
 -/
@@ -153,7 +153,7 @@ theorem factors_eq_nil (n : ℕ) : n.factors = [] ↔ n = 0 ∨ n = 1 :=
   · rcases n with (_ | _ | n)
     · exact Or.inl rfl
     · exact Or.inr rfl
-    · rw [factors] at h; injection h
+    · rw [factors] at h ; injection h
   · rcases h with (rfl | rfl)
     · exact factors_zero
     · exact factors_one
@@ -198,7 +198,7 @@ theorem mem_factors {n p} (hn : n ≠ 0) : p ∈ factors n ↔ Prime p ∧ p ∣
 theorem le_of_mem_factors {n p : ℕ} (h : p ∈ n.factors) : p ≤ n :=
   by
   rcases n.eq_zero_or_pos with (rfl | hn)
-  · rw [factors_zero] at h; cases h
+  · rw [factors_zero] at h ; cases h
   · exact le_of_dvd hn (dvd_of_mem_factors h)
 #align nat.le_of_mem_factors Nat.le_of_mem_factors
 -/
@@ -211,7 +211,7 @@ theorem factors_unique {n : ℕ} {l : List ℕ} (h₁ : Prod l = n) (h₂ : ∀
   · rw [h₁]
     refine' (prod_factors _).symm
     rintro rfl
-    rw [prod_eq_zero_iff] at h₁
+    rw [prod_eq_zero_iff] at h₁ 
     exact Prime.ne_zero (h₂ 0 h₁) rfl
   · simp_rw [← prime_iff]; exact h₂
   · simp_rw [← prime_iff]; exact fun p => prime_of_mem_factors
@@ -247,7 +247,7 @@ theorem perm_factors_mul {a b : ℕ} (ha : a ≠ 0) (hb : b ≠ 0) :
   refine' (factors_unique _ _).symm
   · rw [List.prod_append, prod_factors ha, prod_factors hb]
   · intro p hp
-    rw [List.mem_append] at hp
+    rw [List.mem_append] at hp 
     cases hp <;> exact prime_of_mem_factors hp
 #align nat.perm_factors_mul Nat.perm_factors_mul
 -/

327c3c0d

bump to nightly-2023-05-28-18

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

8d353152

Diff

@@ -31,7 +31,7 @@ This file deals with the factors of natural numbers.
 
 open Bool Subtype
 
-open Nat
+open scoped Nat
 
 namespace Nat

327c3c0d

bump to nightly-2023-05-28-06

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

ba5d8b97

Diff

@@ -334,12 +334,6 @@ theorem coprime_factors_disjoint {a b : ℕ} (hab : a.coprime b) :
 #align nat.coprime_factors_disjoint Nat.coprime_factors_disjoint
 -/
 
-/- warning: nat.mem_factors_mul_of_coprime -> Nat.mem_factors_mul_of_coprime is a dubious translation:
-lean 3 declaration is
-  forall {a : Nat} {b : Nat}, (Nat.coprime a b) -> (forall (p : Nat), Iff (Membership.Mem.{0, 0} Nat (List.{0} Nat) (List.hasMem.{0} Nat) p (Nat.factors (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) a b))) (Membership.Mem.{0, 0} Nat (List.{0} Nat) (List.hasMem.{0} Nat) p (Union.union.{0} (List.{0} Nat) (List.hasUnion.{0} Nat (fun (a : Nat) (b : Nat) => Nat.decidableEq a b)) (Nat.factors a) (Nat.factors b))))
-but is expected to have type
-  forall {a : Nat} {b : Nat}, (Nat.coprime a b) -> (forall (p : Nat), Iff (Membership.mem.{0, 0} Nat (List.{0} Nat) (List.instMembershipList.{0} Nat) p (Nat.factors (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) a b))) (Membership.mem.{0, 0} Nat (List.{0} Nat) (List.instMembershipList.{0} Nat) p (Union.union.{0} (List.{0} Nat) (List.instUnionList.{0} Nat (fun (a : Nat) (b : Nat) => instDecidableEqNat a b)) (Nat.factors a) (Nat.factors b))))
-Case conversion may be inaccurate. Consider using '#align nat.mem_factors_mul_of_coprime Nat.mem_factors_mul_of_coprimeₓ'. -/
 theorem mem_factors_mul_of_coprime {a b : ℕ} (hab : coprime a b) (p : ℕ) :
     p ∈ (a * b).factors ↔ p ∈ a.factors ∪ b.factors :=
   by

327c3c0d

bump to nightly-2023-05-28-04

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

6797a637

Diff

@@ -153,8 +153,7 @@ theorem factors_eq_nil (n : ℕ) : n.factors = [] ↔ n = 0 ∨ n = 1 :=
   · rcases n with (_ | _ | n)
     · exact Or.inl rfl
     · exact Or.inr rfl
-    · rw [factors] at h
-      injection h
+    · rw [factors] at h; injection h
   · rcases h with (rfl | rfl)
     · exact factors_zero
     · exact factors_one
@@ -199,8 +198,7 @@ theorem mem_factors {n p} (hn : n ≠ 0) : p ∈ factors n ↔ Prime p ∧ p ∣
 theorem le_of_mem_factors {n p : ℕ} (h : p ∈ n.factors) : p ≤ n :=
   by
   rcases n.eq_zero_or_pos with (rfl | hn)
-  · rw [factors_zero] at h
-    cases h
+  · rw [factors_zero] at h; cases h
   · exact le_of_dvd hn (dvd_of_mem_factors h)
 #align nat.le_of_mem_factors Nat.le_of_mem_factors
 -/
@@ -215,10 +213,8 @@ theorem factors_unique {n : ℕ} {l : List ℕ} (h₁ : Prod l = n) (h₂ : ∀
     rintro rfl
     rw [prod_eq_zero_iff] at h₁
     exact Prime.ne_zero (h₂ 0 h₁) rfl
-  · simp_rw [← prime_iff]
-    exact h₂
-  · simp_rw [← prime_iff]
-    exact fun p => prime_of_mem_factors
+  · simp_rw [← prime_iff]; exact h₂
+  · simp_rw [← prime_iff]; exact fun p => prime_of_mem_factors
 #align nat.factors_unique Nat.factors_unique
 -/
 
@@ -369,9 +365,7 @@ theorem mem_factors_mul_left {p a b : ℕ} (hpa : p ∈ a.factors) (hb : b ≠ 0
 #print Nat.mem_factors_mul_right /-
 /-- If `p` is a prime factor of `b` then `p` is also a prime factor of `a * b` for any `a > 0` -/
 theorem mem_factors_mul_right {p a b : ℕ} (hpb : p ∈ b.factors) (ha : a ≠ 0) :
-    p ∈ (a * b).factors := by
-  rw [mul_comm]
-  exact mem_factors_mul_left hpb ha
+    p ∈ (a * b).factors := by rw [mul_comm]; exact mem_factors_mul_left hpb ha
 #align nat.mem_factors_mul_right Nat.mem_factors_mul_right
 -/

327c3c0d

bump to nightly-2023-03-11-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/3180fab693e2cee3bff62675571264cb8778b212

cd44fb92

Diff

@@ -89,7 +89,7 @@ theorem prod_factors : ∀ {n}, n ≠ 0 → List.prod (factors n) = n
       have h₁ : n / m ≠ 0 := fun h =>
         by
         have : n = 0 * m := (Nat.div_eq_iff_eq_mul_left (minFac_pos _) (minFac_dvd _)).1 h
-        rw [zero_mul] at this <;> exact (show k + 2 ≠ 0 by decide) this
+        rw [MulZeroClass.zero_mul] at this <;> exact (show k + 2 ≠ 0 by decide) this
       rw [factors, List.prod_cons, prod_factors h₁, Nat.mul_div_cancel' (min_fac_dvd _)]
 #align nat.prod_factors Nat.prod_factors
 -/
@@ -273,7 +273,7 @@ theorem perm_factors_mul_of_coprime {a b : ℕ} (hab : coprime a b) :
 theorem factors_sublist_right {n k : ℕ} (h : k ≠ 0) : n.factors <+ (n * k).factors :=
   by
   cases n
-  · rw [zero_mul]
+  · rw [MulZeroClass.zero_mul]
   apply sublist_of_subperm_of_sorted _ (factors_sorted _) (factors_sorted _)
   rw [(perm_factors_mul n.succ_ne_zero h).subperm_left]
   exact (sublist_append_left _ _).Subperm

327c3c0d

bump to nightly-2023-02-21-16

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

1107b979

Changes in mathlib4

mathlib3

mathlib4

008205aa

chore: reduce proof dependencies for Nat.factors_count_eq (#12105)

This is a bit longer, partially duplicating the argument from UniqueFactorizationMonoid.multiplicity_eq_count_normalizedFactors, but it means we no longer need to depend on RingTheory.Int.Basic at this point.

The other added lemmas seem useful regardless.

51a6e529

Diff

@@ -253,6 +253,22 @@ theorem dvd_of_factors_subperm {a b : ℕ} (ha : a ≠ 0) (h : a.factors <+~ b.f
     Nat.prod_factors hb.ne']
 #align nat.dvd_of_factors_subperm Nat.dvd_of_factors_subperm
 
+theorem replicate_subperm_factors_iff {a b n : ℕ} (ha : Prime a) (hb : b ≠ 0) :
+    replicate n a <+~ factors b ↔ a ^ n ∣ b := by
+  induction n generalizing b with
+  | zero => simp
+  | succ n ih =>
+    constructor
+    · rw [List.subperm_iff]
+      rintro ⟨u, hu1, hu2⟩
+      rw [← Nat.prod_factors hb, ← hu1.prod_eq, ← prod_replicate]
+      exact hu2.prod_dvd_prod
+    · rintro ⟨c, rfl⟩
+      rw [Ne.def, pow_succ', mul_assoc, mul_eq_zero, _root_.not_or] at hb
+      rw [pow_succ', mul_assoc, replicate_succ, (Nat.perm_factors_mul hb.1 hb.2).subperm_left,
+        factors_prime ha, singleton_append, subperm_cons, ih hb.2]
+      exact dvd_mul_right _ _
+
 end
 
 theorem mem_factors_mul {a b : ℕ} (ha : a ≠ 0) (hb : b ≠ 0) {p : ℕ} :

008205aa

chore: move Mathlib to v4.7.0-rc1 (#11162)

This is a very large PR, but it has been reviewed piecemeal already in PRs to the bump/v4.7.0 branch as we update to intermediate nightlies.

Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Kyle Miller <kmill31415@gmail.com> Co-authored-by: damiano <adomani@gmail.com>

fa48894a

Diff

@@ -310,7 +310,7 @@ theorem four_dvd_or_exists_odd_prime_and_dvd_of_two_lt {n : ℕ} (n2 : 2 < n) :
   obtain ⟨_ | _ | k, rfl⟩ | ⟨p, hp, hdvd, hodd⟩ := n.eq_two_pow_or_exists_odd_prime_and_dvd
   · contradiction
   · contradiction
-  · simp [pow_succ, mul_assoc]
+  · simp [Nat.pow_succ, mul_assoc]
   · exact Or.inr ⟨p, hp, hdvd, hodd⟩
 
 end Nat

008205aa

style: homogenise porting notes (#11145)

Homogenises porting notes via capitalisation and addition of whitespace.

It makes the following changes:

converts "--porting note" into "-- Porting note";
converts "porting note" into "Porting note".

8be0b69c

Diff

@@ -244,7 +244,7 @@ theorem dvd_of_factors_subperm {a b : ℕ} (ha : a ≠ 0) (h : a.factors <+~ b.f
   rcases a with (_ | _ | a)
   · exact (ha rfl).elim
   · exact one_dvd _
-  --Porting note: previous proof
+  -- Porting note: previous proof
   --use (b.factors.diff a.succ.succ.factors).prod
   use (@List.diff _ instBEq b.factors a.succ.succ.factors).prod
   nth_rw 1 [← Nat.prod_factors ha]

008205aa

chore: reduce imports (#9830)

This uses the improved shake script from #9772 to reduce imports across mathlib. The corresponding noshake.json file has been added to #9772.

Co-authored-by: Mario Carneiro <di.gama@gmail.com>

f4c4ca61

Diff

@@ -6,6 +6,7 @@ Authors: Leonardo de Moura, Jeremy Avigad, Mario Carneiro
 import Mathlib.Data.Nat.Prime
 import Mathlib.Data.List.Prime
 import Mathlib.Data.List.Sort
+import Mathlib.Data.List.Chain
 
 #align_import data.nat.factors from "leanprover-community/mathlib"@"008205aa645b3f194c1da47025c5f110c8406eab"

008205aa

chore: patch std4#89 (#8566)

Co-authored-by: Mario Carneiro <di.gama@gmail.com> Co-authored-by: Tobias Grosser <tobias@grosser.es> Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Scott Morrison <scott@tqft.net>

ee5a1c52

Diff

@@ -129,6 +129,7 @@ theorem factors_eq_nil (n : ℕ) : n.factors = [] ↔ n = 0 ∨ n = 1 := by
     · exact factors_one
 #align nat.factors_eq_nil Nat.factors_eq_nil
 
+open scoped List in
 theorem eq_of_perm_factors {a b : ℕ} (ha : a ≠ 0) (hb : b ≠ 0) (h : a.factors ~ b.factors) :
     a = b := by simpa [prod_factors ha, prod_factors hb] using List.Perm.prod_eq h
 #align nat.eq_of_perm_factors Nat.eq_of_perm_factors

008205aa

refactor: Unify spelling of "prime factors" (#8164)

mathlib can't make up its mind on whether to spell "the prime factors of n" as n.factors.toFinset or n.factorization.support, even though those two are defeq. This PR proposes to unify everything to a new definition Nat.primeFactors, and streamline the existing scattered API about n.factors.toFinset and n.factorization.support to Nat.primeFactors. We also get to write a bit more API that didn't make sense before, eg primeFactors_mono.

5ced22e4

Diff

@@ -154,6 +154,9 @@ theorem mem_factors {n p} (hn : n ≠ 0) : p ∈ factors n ↔ Prime p ∧ p ∣
     (mem_factors_iff_dvd hn hprime).mpr hdvd⟩
 #align nat.mem_factors Nat.mem_factors
 
+@[simp] lemma mem_factors' {n p} : p ∈ n.factors ↔ p.Prime ∧ p ∣ n ∧ n ≠ 0 := by
+  cases n <;> simp [mem_factors, *]
+
 theorem le_of_mem_factors {n p : ℕ} (h : p ∈ n.factors) : p ≤ n := by
   rcases n.eq_zero_or_pos with (rfl | hn)
   · rw [factors_zero] at h

008205aa

feat: reduce FLT to odd primes (#7485)

37079e5a

Diff

@@ -300,6 +300,14 @@ theorem eq_two_pow_or_exists_odd_prime_and_dvd (n : ℕ) :
           hprime.eq_two_or_odd'.resolve_right fun hodd => H ⟨_, hprime, hdvd, hodd⟩⟩
 #align nat.eq_two_pow_or_exists_odd_prime_and_dvd Nat.eq_two_pow_or_exists_odd_prime_and_dvd
 
+theorem four_dvd_or_exists_odd_prime_and_dvd_of_two_lt {n : ℕ} (n2 : 2 < n) :
+    4 ∣ n ∨ ∃ p, Prime p ∧ p ∣ n ∧ Odd p := by
+  obtain ⟨_ | _ | k, rfl⟩ | ⟨p, hp, hdvd, hodd⟩ := n.eq_two_pow_or_exists_odd_prime_and_dvd
+  · contradiction
+  · contradiction
+  · simp [pow_succ, mul_assoc]
+  · exact Or.inr ⟨p, hp, hdvd, hodd⟩
+
 end Nat
 
 assert_not_exists Multiset

008205aa

chore: remove nonterminal simp (#7580)

Removes nonterminal simps on lines looking like simp [...]

6fc8e6ec

Diff

@@ -216,7 +216,7 @@ theorem factors_sublist_right {n k : ℕ} (h : k ≠ 0) : n.factors <+ (n * k).f
   cases' n with hn
   · simp [zero_mul]
   apply sublist_of_subperm_of_sorted _ (factors_sorted _) (factors_sorted _)
-  simp [(perm_factors_mul (Nat.succ_ne_zero _) h).subperm_left]
+  simp only [(perm_factors_mul (Nat.succ_ne_zero _) h).subperm_left]
   exact (sublist_append_left _ _).subperm
 #align nat.factors_sublist_right Nat.factors_sublist_right

008205aa

chore: bump to v4.1.0-rc1 (2nd attempt) (#7216)

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

bfaffcf1

Diff

@@ -203,7 +203,7 @@ theorem perm_factors_mul {a b : ℕ} (ha : a ≠ 0) (hb : b ≠ 0) :
 #align nat.perm_factors_mul Nat.perm_factors_mul
 
 /-- For coprime `a` and `b`, the prime factors of `a * b` are the union of those of `a` and `b` -/
-theorem perm_factors_mul_of_coprime {a b : ℕ} (hab : coprime a b) :
+theorem perm_factors_mul_of_coprime {a b : ℕ} (hab : Coprime a b) :
     (a * b).factors ~ a.factors ++ b.factors := by
   rcases a.eq_zero_or_pos with (rfl | ha)
   · simp [(coprime_zero_left _).mp hab]
@@ -257,7 +257,7 @@ theorem mem_factors_mul {a b : ℕ} (ha : a ≠ 0) (hb : b ≠ 0) {p : ℕ} :
 #align nat.mem_factors_mul Nat.mem_factors_mul
 
 /-- The sets of factors of coprime `a` and `b` are disjoint -/
-theorem coprime_factors_disjoint {a b : ℕ} (hab : a.coprime b) :
+theorem coprime_factors_disjoint {a b : ℕ} (hab : a.Coprime b) :
     List.Disjoint a.factors b.factors := by
   intro q hqa hqb
   apply not_prime_one
@@ -265,7 +265,7 @@ theorem coprime_factors_disjoint {a b : ℕ} (hab : a.coprime b) :
   exact prime_of_mem_factors hqa
 #align nat.coprime_factors_disjoint Nat.coprime_factors_disjoint
 
-theorem mem_factors_mul_of_coprime {a b : ℕ} (hab : coprime a b) (p : ℕ) :
+theorem mem_factors_mul_of_coprime {a b : ℕ} (hab : Coprime a b) (p : ℕ) :
     p ∈ (a * b).factors ↔ p ∈ a.factors ∪ b.factors := by
   rcases a.eq_zero_or_pos with (rfl | ha)
   · simp [(coprime_zero_left _).mp hab]

008205aa

Revert "chore: bump to v4.1.0-rc1 (#7174)" (#7198)

This reverts commit 6f8e8104. Unfortunately this bump was not linted correctly, as CI did not run runLinter Mathlib.

We can unrevert once that's fixed.

40b58304

Diff

@@ -203,7 +203,7 @@ theorem perm_factors_mul {a b : ℕ} (ha : a ≠ 0) (hb : b ≠ 0) :
 #align nat.perm_factors_mul Nat.perm_factors_mul
 
 /-- For coprime `a` and `b`, the prime factors of `a * b` are the union of those of `a` and `b` -/
-theorem perm_factors_mul_of_coprime {a b : ℕ} (hab : Coprime a b) :
+theorem perm_factors_mul_of_coprime {a b : ℕ} (hab : coprime a b) :
     (a * b).factors ~ a.factors ++ b.factors := by
   rcases a.eq_zero_or_pos with (rfl | ha)
   · simp [(coprime_zero_left _).mp hab]
@@ -257,7 +257,7 @@ theorem mem_factors_mul {a b : ℕ} (ha : a ≠ 0) (hb : b ≠ 0) {p : ℕ} :
 #align nat.mem_factors_mul Nat.mem_factors_mul
 
 /-- The sets of factors of coprime `a` and `b` are disjoint -/
-theorem coprime_factors_disjoint {a b : ℕ} (hab : a.Coprime b) :
+theorem coprime_factors_disjoint {a b : ℕ} (hab : a.coprime b) :
     List.Disjoint a.factors b.factors := by
   intro q hqa hqb
   apply not_prime_one
@@ -265,7 +265,7 @@ theorem coprime_factors_disjoint {a b : ℕ} (hab : a.Coprime b) :
   exact prime_of_mem_factors hqa
 #align nat.coprime_factors_disjoint Nat.coprime_factors_disjoint
 
-theorem mem_factors_mul_of_coprime {a b : ℕ} (hab : Coprime a b) (p : ℕ) :
+theorem mem_factors_mul_of_coprime {a b : ℕ} (hab : coprime a b) (p : ℕ) :
     p ∈ (a * b).factors ↔ p ∈ a.factors ∪ b.factors := by
   rcases a.eq_zero_or_pos with (rfl | ha)
   · simp [(coprime_zero_left _).mp hab]

008205aa

chore: bump to v4.1.0-rc1 (#7174)

Some changes have already been review and delegated in #6910 and #7148.

The diff that needs looking at is https://github.com/leanprover-community/mathlib4/pull/7174/commits/64d6d07ee18163627c8f517eb31455411921c5ac

The std bump PR was insta-merged already!

Co-authored-by: leanprover-community-mathlib4-bot <leanprover-community-mathlib4-bot@users.noreply.github.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

6f8e8104

Diff

@@ -203,7 +203,7 @@ theorem perm_factors_mul {a b : ℕ} (ha : a ≠ 0) (hb : b ≠ 0) :
 #align nat.perm_factors_mul Nat.perm_factors_mul
 
 /-- For coprime `a` and `b`, the prime factors of `a * b` are the union of those of `a` and `b` -/
-theorem perm_factors_mul_of_coprime {a b : ℕ} (hab : coprime a b) :
+theorem perm_factors_mul_of_coprime {a b : ℕ} (hab : Coprime a b) :
     (a * b).factors ~ a.factors ++ b.factors := by
   rcases a.eq_zero_or_pos with (rfl | ha)
   · simp [(coprime_zero_left _).mp hab]
@@ -257,7 +257,7 @@ theorem mem_factors_mul {a b : ℕ} (ha : a ≠ 0) (hb : b ≠ 0) {p : ℕ} :
 #align nat.mem_factors_mul Nat.mem_factors_mul
 
 /-- The sets of factors of coprime `a` and `b` are disjoint -/
-theorem coprime_factors_disjoint {a b : ℕ} (hab : a.coprime b) :
+theorem coprime_factors_disjoint {a b : ℕ} (hab : a.Coprime b) :
     List.Disjoint a.factors b.factors := by
   intro q hqa hqb
   apply not_prime_one
@@ -265,7 +265,7 @@ theorem coprime_factors_disjoint {a b : ℕ} (hab : a.coprime b) :
   exact prime_of_mem_factors hqa
 #align nat.coprime_factors_disjoint Nat.coprime_factors_disjoint
 
-theorem mem_factors_mul_of_coprime {a b : ℕ} (hab : coprime a b) (p : ℕ) :
+theorem mem_factors_mul_of_coprime {a b : ℕ} (hab : Coprime a b) (p : ℕ) :
     p ∈ (a * b).factors ↔ p ∈ a.factors ∪ b.factors := by
   rcases a.eq_zero_or_pos with (rfl | ha)
   · simp [(coprime_zero_left _).mp hab]

008205aa

chore: bump Std version (#6435)

Notably there is now a l1 ∪ l2 notation for List.union.

Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Bulhwi Cha <chabulhwi@semmalgil.com>

5f5bef5a

Diff

@@ -271,7 +271,7 @@ theorem mem_factors_mul_of_coprime {a b : ℕ} (hab : coprime a b) (p : ℕ) :
   · simp [(coprime_zero_left _).mp hab]
   rcases b.eq_zero_or_pos with (rfl | hb)
   · simp [(coprime_zero_right _).mp hab]
-  rw [mem_factors_mul ha.ne' hb.ne', List.mem_union]
+  rw [mem_factors_mul ha.ne' hb.ne', List.mem_union_iff]
 #align nat.mem_factors_mul_of_coprime Nat.mem_factors_mul_of_coprime
 
 open List

008205aa

chore: cleanup some set_option commands (#6281)

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

865bd5b5

Diff

@@ -21,8 +21,6 @@ This file deals with the factors of natural numbers.
 
 -/
 
-set_option autoImplicit false
-
 open Bool Subtype
 
 open Nat

008205aa

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,16 +2,13 @@
 Copyright (c) 2015 Microsoft Corporation. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Leonardo de Moura, Jeremy Avigad, Mario Carneiro
-
-! This file was ported from Lean 3 source module data.nat.factors
-! leanprover-community/mathlib commit 008205aa645b3f194c1da47025c5f110c8406eab
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Data.Nat.Prime
 import Mathlib.Data.List.Prime
 import Mathlib.Data.List.Sort
 
+#align_import data.nat.factors from "leanprover-community/mathlib"@"008205aa645b3f194c1da47025c5f110c8406eab"
+
 /-!
 # Prime numbers

008205aa

feat: assert_not_exists (#4245)

25809c65

Diff

@@ -307,5 +307,4 @@ theorem eq_two_pow_or_exists_odd_prime_and_dvd (n : ℕ) :
 
 end Nat
 
--- Porting note: `assert_not_exists` is not implemented yet.
---assert_not_exists Multiset
+assert_not_exists Multiset

008205aa

feat: add Mathlib.Tactic.Common, and import (#4056)

This makes a mathlib4 version of mathlib3's tactic.basic, now called Mathlib.Tactic.Common, which imports all tactics which do not have significant theory requirements, and then is imported all across the base of the hierarchy.

This ensures that all common tactics are available nearly everywhere in the library, rather than having to be imported one-by-one as you need them.

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

a4eaf1c4

Diff

@@ -11,7 +11,6 @@ Authors: Leonardo de Moura, Jeremy Avigad, Mario Carneiro
 import Mathlib.Data.Nat.Prime
 import Mathlib.Data.List.Prime
 import Mathlib.Data.List.Sort
-import Mathlib.Tactic.NthRewrite
 
 /-!
 # Prime numbers

008205aa

chore: bye-bye, solo bys! (#3825)

This PR puts, with one exception, every single remaining by that lies all by itself on its own line to the previous line, thus matching the current behaviour of start-port.sh. The exception is when the by begins the second or later argument to a tuple or anonymous constructor; see https://github.com/leanprover-community/mathlib4/pull/3825#discussion_r1186702599.

Essentially this is s/\n *by$/ by/g, but with manual editing to satisfy the linter's max-100-char-line requirement. The Python style linter is also modified to catch these "isolated bys".

14167e48

Diff

@@ -283,8 +283,8 @@ theorem mem_factors_mul_of_coprime {a b : ℕ} (hab : coprime a b) (p : ℕ) :
 open List
 
 /-- If `p` is a prime factor of `a` then `p` is also a prime factor of `a * b` for any `b > 0` -/
-theorem mem_factors_mul_left {p a b : ℕ} (hpa : p ∈ a.factors) (hb : b ≠ 0) : p ∈ (a * b).factors :=
-  by
+theorem mem_factors_mul_left {p a b : ℕ} (hpa : p ∈ a.factors) (hb : b ≠ 0) :
+    p ∈ (a * b).factors := by
   rcases eq_or_ne a 0 with (rfl | ha)
   · simp at hpa
   apply (mem_factors_mul ha hb).2 (Or.inl hpa)

008205aa

chore: fix #align lines (#3640)

This PR fixes two things:

Most 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.
All remaining more-than-one-line #align statements. (This was needed for a script I wrote for #3630.)

2b42dc7c

Diff

@@ -206,7 +206,6 @@ theorem perm_factors_mul {a b : ℕ} (ha : a ≠ 0) (hb : b ≠ 0) :
   · intro p hp
     rw [List.mem_append] at hp
     cases' hp with hp' hp' <;> exact prime_of_mem_factors hp'
-
 #align nat.perm_factors_mul Nat.perm_factors_mul
 
 /-- For coprime `a` and `b`, the prime factors of `a * b` are the union of those of `a` and `b` -/

008205aa

feat: port Data.Nat.Factors (#1664)

Co-authored-by: qawbecrdtey <qawbecrdtey@kaist.ac.kr> Co-authored-by: qawbecrdtey <qawbecrdtey@naver.com> Co-authored-by: ChrisHughes24 <chrishughes24@gmail.com>

346d9bc7

`data.nat.factors` ⟷ `Mathlib.Data.Nat.Factors`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 3 + 173

data.nat.factors ⟷ Mathlib.Data.Nat.Factors

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 3 + 173

`data.nat.factors` ⟷ `Mathlib.Data.Nat.Factors`