number_theory.fermat_psp ⟷ Mathlib.NumberTheory.FermatPsp

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

@@ -174,7 +174,7 @@ private theorem b_id_helper {a b : ℕ} (ha : 2 ≤ a) (hb : 2 < b) : 2 ≤ (a ^
   apply Nat.succ_le_succ
   calc
     2 * a + 1 ≤ a ^ 2 * a := by nlinarith
-    _ = a ^ 3 := by rw [pow_succ' a 2]
+    _ = a ^ 3 := by rw [pow_succ a 2]
     _ ≤ a ^ b := pow_le_pow_right (Nat.le_of_succ_le ha) hb
 
 private theorem AB_id_helper (b p : ℕ) (hb : 2 ≤ b) (hp : Odd p) :
@@ -200,7 +200,7 @@ private theorem bp_helper {b p : ℕ} (hb : 0 < b) (hp : 1 ≤ p) :
     _ = (b ^ p + b) * (b ^ p - b) := by rw [Nat.sq_sub_sq]
     _ = (b ^ p - b) * (b ^ p + b) := by rw [mul_comm]
     _ = (b ^ (p - 1 + 1) - b) * (b ^ p + b) := by rw [Nat.sub_add_cancel hp]
-    _ = (b * b ^ (p - 1) - b) * (b ^ p + b) := by rw [pow_succ]
+    _ = (b * b ^ (p - 1) - b) * (b ^ p + b) := by rw [pow_succ']
     _ = (b * b ^ (p - 1) - b * 1) * (b ^ p + b) := by rw [mul_one]
     _ = b * (b ^ (p - 1) - 1) * (b ^ p + b) := by rw [Nat.mul_sub_left_distrib]
 
@@ -353,7 +353,7 @@ private theorem psp_from_prime_gt_p {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_
     rwa [Nat.mul_div_cancel _ h₂] at h₁
   rw [Nat.mul_sub_left_distrib, mul_one, pow_mul]
   nth_rw_rhs 1 [← Nat.sub_add_cancel (show 1 ≤ p by linarith)]
-  rw [pow_succ (b ^ 2)]
+  rw [pow_succ' (b ^ 2)]
   suffices h : p * b ^ 2 < b ^ 2 * (b ^ 2) ^ (p - 1)
   · apply gt_of_ge_of_gt
     · exact tsub_le_tsub_left (show 1 ≤ p by linarith) (b ^ 2 * (b ^ 2) ^ (p - 1))

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

@@ -253,11 +253,11 @@ private theorem psp_from_prime_psp {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_p
   -- Used to prove that `2 * p * (b ^ 2 - 1) ∣ (b ^ 2 - 1) * (A * B - 1)`.
   have ha₁ : (b ^ 2 - 1) * (A * B - 1) = b * (b ^ (p - 1) - 1) * (b ^ p + b) :=
     by
-    apply_fun fun x => x * (b ^ 2 - 1) at AB_id 
-    rw [Nat.div_mul_cancel hd] at AB_id 
-    apply_fun fun x => x - (b ^ 2 - 1) at AB_id 
-    nth_rw 2 [← one_mul (b ^ 2 - 1)] at AB_id 
-    rw [← Nat.mul_sub_right_distrib, mul_comm] at AB_id 
+    apply_fun fun x => x * (b ^ 2 - 1) at AB_id
+    rw [Nat.div_mul_cancel hd] at AB_id
+    apply_fun fun x => x - (b ^ 2 - 1) at AB_id
+    nth_rw 2 [← one_mul (b ^ 2 - 1)] at AB_id
+    rw [← Nat.mul_sub_right_distrib, mul_comm] at AB_id
     rw [AB_id]
     exact bp_helper hi_b hi_p
   -- If `b` is even, then `b^p` is also even, so `2 ∣ b^p + b`
@@ -291,8 +291,8 @@ private theorem psp_from_prime_psp {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_p
     cases' this with c hc
     have : b ^ 2 - 1 ∣ (b ^ 2) ^ c - 1 := by
       simpa only [one_pow] using nat_sub_dvd_pow_sub_pow _ 1 c
-    have : b ^ 2 - 1 ∣ b ^ (2 * c) - 1 := by rwa [← pow_mul] at this 
-    rwa [← hc] at this 
+    have : b ^ 2 - 1 ∣ b ^ (2 * c) - 1 := by rwa [← pow_mul] at this
+    rwa [← hc] at this
   -- Used to prove that `2 * p` divides `A * B - 1`
   have ha₅ : 2 * p * (b ^ 2 - 1) ∣ (b ^ 2 - 1) * (A * B - 1) :=
     by
@@ -303,7 +303,7 @@ private theorem psp_from_prime_psp {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_p
     -- know that `2 * p ∣ b ^ p + b`
     have q₁ : Nat.Coprime p (b ^ 2 - 1) :=
       haveI q₂ : ¬p ∣ b ^ 2 - 1 := by
-        rw [mul_comm] at not_dvd 
+        rw [mul_comm] at not_dvd
         exact mt (fun h : p ∣ b ^ 2 - 1 => dvd_mul_of_dvd_left h _) not_dvd
       (Nat.Prime.coprime_iff_not_dvd p_prime).mpr q₂
     have q₂ : p * (b ^ 2 - 1) ∣ b ^ (p - 1) - 1 := Nat.Coprime.mul_dvd_of_dvd_of_dvd q₁ ha₃ ha₄
@@ -312,7 +312,7 @@ private theorem psp_from_prime_psp {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_p
       dvd_mul_of_dvd_right q₃ _
     rwa [mul_assoc, mul_comm, mul_assoc b]
   have ha₆ : 2 * p ∣ A * B - 1 := by
-    rw [mul_comm] at ha₅ 
+    rw [mul_comm] at ha₅
     exact Nat.dvd_of_mul_dvd_mul_left hi_bsquared ha₅
   -- `A * B` divides `b ^ (2 * p) - 1` because `A * B * (b ^ 2 - 1) = b ^ (2 * p) - 1`.
   -- This can be proven by multiplying both sides of `AB_id` by `b ^ 2 - 1`.
@@ -350,7 +350,7 @@ private theorem psp_from_prime_gt_p {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_
       Nat.div_lt_div_of_lt_of_dvd AB_dvd h
     have h₂ : 0 < b ^ 2 - 1 := by
       linarith [show 3 ≤ b ^ 2 - 1 from le_tsub_of_add_le_left (show 4 ≤ b ^ 2 by nlinarith)]
-    rwa [Nat.mul_div_cancel _ h₂] at h₁ 
+    rwa [Nat.mul_div_cancel _ h₂] at h₁
   rw [Nat.mul_sub_left_distrib, mul_one, pow_mul]
   nth_rw_rhs 1 [← Nat.sub_add_cancel (show 1 ≤ p by linarith)]
   rw [pow_succ (b ^ 2)]

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

@@ -158,7 +158,7 @@ theorem fermatPsp_base_one {n : ℕ} (h₁ : 1 < n) (h₂ : ¬n.Prime) : Nat.Fer
 section HelperLemmas
 
 private theorem pow_gt_exponent {a : ℕ} (b : ℕ) (h : 2 ≤ a) : b < a ^ b :=
-  lt_of_lt_of_le (Nat.lt_two_pow b) <| Nat.pow_le_pow_of_le_left h _
+  lt_of_lt_of_le (Nat.lt_two_pow b) <| Nat.pow_le_pow_left h _
 
 private theorem a_id_helper {a b : ℕ} (ha : 2 ≤ a) (hb : 2 ≤ b) : 2 ≤ (a ^ b - 1) / (a - 1) :=
   by
@@ -175,7 +175,7 @@ private theorem b_id_helper {a b : ℕ} (ha : 2 ≤ a) (hb : 2 < b) : 2 ≤ (a ^
   calc
     2 * a + 1 ≤ a ^ 2 * a := by nlinarith
     _ = a ^ 3 := by rw [pow_succ' a 2]
-    _ ≤ a ^ b := pow_le_pow (Nat.le_of_succ_le ha) hb
+    _ ≤ a ^ b := pow_le_pow_right (Nat.le_of_succ_le ha) hb
 
 private theorem AB_id_helper (b p : ℕ) (hb : 2 ≤ b) (hp : Odd p) :
     (b ^ p - 1) / (b - 1) * ((b ^ p + 1) / (b + 1)) = (b ^ (2 * p) - 1) / (b ^ 2 - 1) :=
@@ -389,7 +389,7 @@ theorem exists_infinite_pseudoprimes {b : ℕ} (h : 1 ≤ b) (m : ℕ) :
     cases' h with p hp
     cases' hp with hp₁ hp₂
     have h₁ : 0 < b := pos_of_gt (nat.succ_le_iff.mp b_ge_two)
-    have h₂ : 4 ≤ b ^ 2 := pow_le_pow_of_le_left' b_ge_two 2
+    have h₂ : 4 ≤ b ^ 2 := pow_le_pow_left' b_ge_two 2
     have h₃ : 0 < b ^ 2 - 1 := tsub_pos_of_lt (gt_of_ge_of_gt h₂ (by norm_num))
     have h₄ : 0 < b * (b ^ 2 - 1) := mul_pos h₁ h₃
     have h₅ : b * (b ^ 2 - 1) < p := by linarith

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

@@ -72,7 +72,7 @@ namespace Nat.FermatPsp
 
 #print Nat.decidableProbablePrime /-
 instance decidableProbablePrime (n b : ℕ) : Decidable (ProbablePrime n b) :=
-  Nat.decidableDvd _ _
+  Nat.decidable_dvd _ _
 #align fermat_psp.decidable_probable_prime Nat.decidableProbablePrime
 -/
 

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

@@ -3,9 +3,9 @@ Copyright (c) 2022 Niels Voss. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Niels Voss
 -/
-import Mathbin.Data.Nat.Prime
-import Mathbin.FieldTheory.Finite.Basic
-import Mathbin.Order.Filter.Cofinite
+import Data.Nat.Prime
+import FieldTheory.Finite.Basic
+import Order.Filter.Cofinite
 
 #align_import number_theory.fermat_psp from "leanprover-community/mathlib"@"5c1efce12ba86d4901463f61019832f6a4b1a0d0"
 

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

@@ -87,7 +87,7 @@ instance decidablePsp (n b : ℕ) : Decidable (Nat.FermatPsp n b) :=
 `n` and `b` are both positive.
 -/
 theorem coprime_of_probablePrime {n b : ℕ} (h : ProbablePrime n b) (h₁ : 1 ≤ n) (h₂ : 1 ≤ b) :
-    Nat.coprime n b := by
+    Nat.Coprime n b := by
   by_cases h₃ : 2 ≤ n
   · -- To prove that `n` is coprime with `b`, we we need to show that for all prime factors of `n`,
     -- we can derive a contradiction if `n` divides `b`.
@@ -136,7 +136,7 @@ positive.
 
 This lemma is a small wrapper based on `coprime_of_probable_prime`
 -/
-theorem coprime_of_fermatPsp {n b : ℕ} (h : Nat.FermatPsp n b) (h₁ : 1 ≤ b) : Nat.coprime n b :=
+theorem coprime_of_fermatPsp {n b : ℕ} (h : Nat.FermatPsp n b) (h₁ : 1 ≤ b) : Nat.Coprime n b :=
   by
   rcases h with ⟨hp, hn₁, hn₂⟩
   exact coprime_of_probable_prime hp (by linarith) h₁
@@ -301,12 +301,12 @@ private theorem psp_from_prime_psp {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_p
     -- We already proved that `b ^ 2 - 1 ∣ b ^ (p - 1) - 1`.
     -- Since `2 ∣ b ^ p + b` and `p ∣ b ^ p + b`, if we show that 2 and p are coprime, then we
     -- know that `2 * p ∣ b ^ p + b`
-    have q₁ : Nat.coprime p (b ^ 2 - 1) :=
+    have q₁ : Nat.Coprime p (b ^ 2 - 1) :=
       haveI q₂ : ¬p ∣ b ^ 2 - 1 := by
         rw [mul_comm] at not_dvd 
         exact mt (fun h : p ∣ b ^ 2 - 1 => dvd_mul_of_dvd_left h _) not_dvd
       (Nat.Prime.coprime_iff_not_dvd p_prime).mpr q₂
-    have q₂ : p * (b ^ 2 - 1) ∣ b ^ (p - 1) - 1 := Nat.coprime.mul_dvd_of_dvd_of_dvd q₁ ha₃ ha₄
+    have q₂ : p * (b ^ 2 - 1) ∣ b ^ (p - 1) - 1 := Nat.Coprime.mul_dvd_of_dvd_of_dvd q₁ ha₃ ha₄
     have q₃ : p * (b ^ 2 - 1) * 2 ∣ (b ^ (p - 1) - 1) * (b ^ p + b) := mul_dvd_mul q₂ ha₂
     have q₄ : p * (b ^ 2 - 1) * 2 ∣ b * ((b ^ (p - 1) - 1) * (b ^ p + b)) :=
       dvd_mul_of_dvd_right q₃ _

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

@@ -45,44 +45,44 @@ The main theorems are
 -/
 
 
-#print FermatPsp.ProbablePrime /-
+#print Nat.ProbablePrime /-
 /--
 `n` is a probable prime to base `b` if `n` passes the Fermat primality test; that is, `n` divides
 `b ^ (n - 1) - 1`.
 This definition implies that all numbers are probable primes to base 0 or 1, and that 0 and 1 are
 probable primes to any base.
 -/
-def FermatPsp.ProbablePrime (n b : ℕ) : Prop :=
+def Nat.ProbablePrime (n b : ℕ) : Prop :=
   n ∣ b ^ (n - 1) - 1
-#align fermat_psp.probable_prime FermatPsp.ProbablePrime
+#align fermat_psp.probable_prime Nat.ProbablePrime
 -/
 
-#print FermatPsp /-
+#print Nat.FermatPsp /-
 /--
 `n` is a Fermat pseudoprime to base `b` if `n` is a probable prime to base `b` and is composite. By
 this definition, all composite natural numbers are pseudoprimes to base 0 and 1. This definition
 also permits `n` to be less than `b`, so that 4 is a pseudoprime to base 5, for example.
 -/
-def FermatPsp (n b : ℕ) : Prop :=
-  FermatPsp.ProbablePrime n b ∧ ¬n.Prime ∧ 1 < n
-#align fermat_psp FermatPsp
+def Nat.FermatPsp (n b : ℕ) : Prop :=
+  Nat.ProbablePrime n b ∧ ¬n.Prime ∧ 1 < n
+#align fermat_psp Nat.FermatPsp
 -/
 
-namespace FermatPsp
+namespace Nat.FermatPsp
 
-#print FermatPsp.decidableProbablePrime /-
+#print Nat.decidableProbablePrime /-
 instance decidableProbablePrime (n b : ℕ) : Decidable (ProbablePrime n b) :=
   Nat.decidableDvd _ _
-#align fermat_psp.decidable_probable_prime FermatPsp.decidableProbablePrime
+#align fermat_psp.decidable_probable_prime Nat.decidableProbablePrime
 -/
 
-#print FermatPsp.decidablePsp /-
-instance decidablePsp (n b : ℕ) : Decidable (FermatPsp n b) :=
+#print Nat.decidablePsp /-
+instance decidablePsp (n b : ℕ) : Decidable (Nat.FermatPsp n b) :=
   And.decidable
-#align fermat_psp.decidable_psp FermatPsp.decidablePsp
+#align fermat_psp.decidable_psp Nat.decidablePsp
 -/
 
-#print FermatPsp.coprime_of_probablePrime /-
+#print Nat.coprime_of_probablePrime /-
 /-- If `n` passes the Fermat primality test to base `b`, then `n` is coprime with `b`, assuming that
 `n` and `b` are both positive.
 -/
@@ -111,10 +111,10 @@ theorem coprime_of_probablePrime {n b : ℕ} (h : ProbablePrime n b) (h₁ : 1 
   -- If `n = 1`, then it follows trivially that `n` is coprime with `b`.
   · rw [show n = 1 by linarith]
     norm_num
-#align fermat_psp.coprime_of_probable_prime FermatPsp.coprime_of_probablePrime
+#align fermat_psp.coprime_of_probable_prime Nat.coprime_of_probablePrime
 -/
 
-#print FermatPsp.probablePrime_iff_modEq /-
+#print Nat.probablePrime_iff_modEq /-
 theorem probablePrime_iff_modEq (n : ℕ) {b : ℕ} (h : 1 ≤ b) :
     ProbablePrime n b ↔ b ^ (n - 1) ≡ 1 [MOD n] :=
   by
@@ -127,30 +127,30 @@ theorem probablePrime_iff_modEq (n : ℕ) {b : ℕ} (h : 1 ≤ b) :
     exact_mod_cast h₁
   · intro h₁
     exact_mod_cast Nat.ModEq.dvd h₁
-#align fermat_psp.probable_prime_iff_modeq FermatPsp.probablePrime_iff_modEq
+#align fermat_psp.probable_prime_iff_modeq Nat.probablePrime_iff_modEq
 -/
 
-#print FermatPsp.coprime_of_fermatPsp /-
+#print Nat.coprime_of_fermatPsp /-
 /-- If `n` is a Fermat pseudoprime to base `b`, then `n` is coprime with `b`, assuming that `b` is
 positive.
 
 This lemma is a small wrapper based on `coprime_of_probable_prime`
 -/
-theorem coprime_of_fermatPsp {n b : ℕ} (h : FermatPsp n b) (h₁ : 1 ≤ b) : Nat.coprime n b :=
+theorem coprime_of_fermatPsp {n b : ℕ} (h : Nat.FermatPsp n b) (h₁ : 1 ≤ b) : Nat.coprime n b :=
   by
   rcases h with ⟨hp, hn₁, hn₂⟩
   exact coprime_of_probable_prime hp (by linarith) h₁
-#align fermat_psp.coprime_of_fermat_psp FermatPsp.coprime_of_fermatPsp
+#align fermat_psp.coprime_of_fermat_psp Nat.coprime_of_fermatPsp
 -/
 
-#print FermatPsp.base_one /-
+#print Nat.fermatPsp_base_one /-
 /-- All composite numbers are Fermat pseudoprimes to base 1.
 -/
-theorem base_one {n : ℕ} (h₁ : 1 < n) (h₂ : ¬n.Prime) : FermatPsp n 1 :=
+theorem fermatPsp_base_one {n : ℕ} (h₁ : 1 < n) (h₂ : ¬n.Prime) : Nat.FermatPsp n 1 :=
   by
   refine' ⟨show n ∣ 1 ^ (n - 1) - 1 from _, h₂, h₁⟩
   exact show 0 = 1 ^ (n - 1) - 1 by norm_num ▸ dvd_zero n
-#align fermat_psp.base_one FermatPsp.base_one
+#align fermat_psp.base_one Nat.fermatPsp_base_one
 -/
 
 -- Lemmas that are needed to prove statements in this file, but aren't directly related to Fermat
@@ -227,7 +227,7 @@ The primary purpose of this lemma is to help prove `exists_infinite_pseudoprimes
 We use <https://primes.utm.edu/notes/proofs/a_pseudoprimes.html> as a rough outline of the proof.
 -/
 private theorem psp_from_prime_psp {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_prime : p.Prime)
-    (p_gt_two : 2 < p) (not_dvd : ¬p ∣ b * (b ^ 2 - 1)) : FermatPsp (pspFromPrime b p) b :=
+    (p_gt_two : 2 < p) (not_dvd : ¬p ∣ b * (b ^ 2 - 1)) : Nat.FermatPsp (pspFromPrime b p) b :=
   by
   unfold psp_from_prime
   set A := (b ^ p - 1) / (b - 1)
@@ -370,12 +370,13 @@ private theorem psp_from_prime_gt_p {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_
   have : p ≤ 2 * p - 2 := le_tsub_of_add_le_left this
   exact Nat.lt_of_le_of_lt this (pow_gt_exponent _ b_ge_two)
 
-#print FermatPsp.exists_infinite_pseudoprimes /-
+#print Nat.exists_infinite_pseudoprimes /-
 /-- For all positive bases, there exist Fermat infinite pseudoprimes to that base.
 Given in this form: for all numbers `b ≥ 1` and `m`, there exists a pseudoprime `n` to base `b` such
 that `m ≤ n`. This form is similar to `nat.exists_infinite_primes`.
 -/
-theorem exists_infinite_pseudoprimes {b : ℕ} (h : 1 ≤ b) (m : ℕ) : ∃ n : ℕ, FermatPsp n b ∧ m ≤ n :=
+theorem exists_infinite_pseudoprimes {b : ℕ} (h : 1 ≤ b) (m : ℕ) :
+    ∃ n : ℕ, Nat.FermatPsp n b ∧ m ≤ n :=
   by
   by_cases b_ge_two : 2 ≤ b
   -- If `2 ≤ b`, then because there exist infinite prime numbers, there is a prime number p such
@@ -409,26 +410,27 @@ theorem exists_infinite_pseudoprimes {b : ℕ} (h : 1 ≤ b) (m : ℕ) : ∃ n :
     use 2 * (m + 2)
     have : ¬Nat.Prime (2 * (m + 2)) := Nat.not_prime_mul (by norm_num) (by norm_num)
     exact ⟨base_one (by linarith) this, by linarith⟩
-#align fermat_psp.exists_infinite_pseudoprimes FermatPsp.exists_infinite_pseudoprimes
+#align fermat_psp.exists_infinite_pseudoprimes Nat.exists_infinite_pseudoprimes
 -/
 
-#print FermatPsp.frequently_atTop_fermatPsp /-
-theorem frequently_atTop_fermatPsp {b : ℕ} (h : 1 ≤ b) : ∃ᶠ n in Filter.atTop, FermatPsp n b :=
+#print Nat.frequently_atTop_fermatPsp /-
+theorem frequently_atTop_fermatPsp {b : ℕ} (h : 1 ≤ b) : ∃ᶠ n in Filter.atTop, Nat.FermatPsp n b :=
   by
   -- Based on the proof of `nat.frequently_at_top_modeq_one`
   refine' Filter.frequently_atTop.2 fun n => _
   obtain ⟨p, hp⟩ := exists_infinite_pseudoprimes h n
   exact ⟨p, hp.2, hp.1⟩
-#align fermat_psp.frequently_at_top_fermat_psp FermatPsp.frequently_atTop_fermatPsp
+#align fermat_psp.frequently_at_top_fermat_psp Nat.frequently_atTop_fermatPsp
 -/
 
-#print FermatPsp.infinite_setOf_prime_modeq_one /-
+#print Nat.infinite_setOf_pseudoprimes /-
 /-- Infinite set variant of `exists_infinite_pseudoprimes`
 -/
-theorem infinite_setOf_prime_modeq_one {b : ℕ} (h : 1 ≤ b) : Set.Infinite {n : ℕ | FermatPsp n b} :=
+theorem infinite_setOf_pseudoprimes {b : ℕ} (h : 1 ≤ b) :
+    Set.Infinite {n : ℕ | Nat.FermatPsp n b} :=
   Nat.frequently_atTop_iff_infinite.mp (frequently_atTop_fermatPsp h)
-#align fermat_psp.infinite_set_of_prime_modeq_one FermatPsp.infinite_setOf_prime_modeq_one
+#align fermat_psp.infinite_set_of_prime_modeq_one Nat.infinite_setOf_pseudoprimes
 -/
 
-end FermatPsp
+end Nat.FermatPsp
 

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

@@ -2,16 +2,13 @@
 Copyright (c) 2022 Niels Voss. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Niels Voss
-
-! This file was ported from Lean 3 source module number_theory.fermat_psp
-! leanprover-community/mathlib commit 5c1efce12ba86d4901463f61019832f6a4b1a0d0
-! 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.FieldTheory.Finite.Basic
 import Mathbin.Order.Filter.Cofinite
 
+#align_import number_theory.fermat_psp from "leanprover-community/mathlib"@"5c1efce12ba86d4901463f61019832f6a4b1a0d0"
+
 /-!
 # Fermat Pseudoprimes
 

mathlib commit https://github.com/leanprover-community/mathlib/commit/7e5137f579de09a059a5ce98f364a04e221aabf0

@@ -179,7 +179,6 @@ private theorem b_id_helper {a b : ℕ} (ha : 2 ≤ a) (hb : 2 < b) : 2 ≤ (a ^
     2 * a + 1 ≤ a ^ 2 * a := by nlinarith
     _ = a ^ 3 := by rw [pow_succ' a 2]
     _ ≤ a ^ b := pow_le_pow (Nat.le_of_succ_le ha) hb
-    
 
 private theorem AB_id_helper (b p : ℕ) (hb : 2 ≤ b) (hp : Odd p) :
     (b ^ p - 1) / (b - 1) * ((b ^ p + 1) / (b + 1)) = (b ^ (2 * p) - 1) / (b ^ 2 - 1) :=
@@ -207,7 +206,6 @@ private theorem bp_helper {b p : ℕ} (hb : 0 < b) (hp : 1 ≤ p) :
     _ = (b * b ^ (p - 1) - b) * (b ^ p + b) := by rw [pow_succ]
     _ = (b * b ^ (p - 1) - b * 1) * (b ^ p + b) := by rw [mul_one]
     _ = b * (b ^ (p - 1) - 1) * (b ^ p + b) := by rw [Nat.mul_sub_left_distrib]
-    
 
 end HelperLemmas
 

mathlib commit https://github.com/leanprover-community/mathlib/commit/5f25c089cb34db4db112556f23c50d12da81b297

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Niels Voss
 
 ! This file was ported from Lean 3 source module number_theory.fermat_psp
-! leanprover-community/mathlib commit c0439b4877c24a117bfdd9e32faf62eee9b115eb
+! leanprover-community/mathlib commit 5c1efce12ba86d4901463f61019832f6a4b1a0d0
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -15,6 +15,9 @@ import Mathbin.Order.Filter.Cofinite
 /-!
 # Fermat Pseudoprimes
 
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
 In this file we define Fermat pseudoprimes: composite numbers that pass the Fermat primality test.
 A natural number `n` passes the Fermat primality test to base `b` (and is therefore deemed a
 "probable prime") if `n` divides `b ^ (n - 1) - 1`. `n` is a Fermat pseudoprime to base `b` if `n`
@@ -45,6 +48,7 @@ The main theorems are
 -/
 
 
+#print FermatPsp.ProbablePrime /-
 /--
 `n` is a probable prime to base `b` if `n` passes the Fermat primality test; that is, `n` divides
 `b ^ (n - 1) - 1`.
@@ -54,7 +58,9 @@ probable primes to any base.
 def FermatPsp.ProbablePrime (n b : ℕ) : Prop :=
   n ∣ b ^ (n - 1) - 1
 #align fermat_psp.probable_prime FermatPsp.ProbablePrime
+-/
 
+#print FermatPsp /-
 /--
 `n` is a Fermat pseudoprime to base `b` if `n` is a probable prime to base `b` and is composite. By
 this definition, all composite natural numbers are pseudoprimes to base 0 and 1. This definition
@@ -63,17 +69,23 @@ also permits `n` to be less than `b`, so that 4 is a pseudoprime to base 5, for
 def FermatPsp (n b : ℕ) : Prop :=
   FermatPsp.ProbablePrime n b ∧ ¬n.Prime ∧ 1 < n
 #align fermat_psp FermatPsp
+-/
 
 namespace FermatPsp
 
+#print FermatPsp.decidableProbablePrime /-
 instance decidableProbablePrime (n b : ℕ) : Decidable (ProbablePrime n b) :=
   Nat.decidableDvd _ _
 #align fermat_psp.decidable_probable_prime FermatPsp.decidableProbablePrime
+-/
 
+#print FermatPsp.decidablePsp /-
 instance decidablePsp (n b : ℕ) : Decidable (FermatPsp n b) :=
   And.decidable
 #align fermat_psp.decidable_psp FermatPsp.decidablePsp
+-/
 
+#print FermatPsp.coprime_of_probablePrime /-
 /-- If `n` passes the Fermat primality test to base `b`, then `n` is coprime with `b`, assuming that
 `n` and `b` are both positive.
 -/
@@ -103,7 +115,9 @@ theorem coprime_of_probablePrime {n b : ℕ} (h : ProbablePrime n b) (h₁ : 1 
   · rw [show n = 1 by linarith]
     norm_num
 #align fermat_psp.coprime_of_probable_prime FermatPsp.coprime_of_probablePrime
+-/
 
+#print FermatPsp.probablePrime_iff_modEq /-
 theorem probablePrime_iff_modEq (n : ℕ) {b : ℕ} (h : 1 ≤ b) :
     ProbablePrime n b ↔ b ^ (n - 1) ≡ 1 [MOD n] :=
   by
@@ -117,7 +131,9 @@ theorem probablePrime_iff_modEq (n : ℕ) {b : ℕ} (h : 1 ≤ b) :
   · intro h₁
     exact_mod_cast Nat.ModEq.dvd h₁
 #align fermat_psp.probable_prime_iff_modeq FermatPsp.probablePrime_iff_modEq
+-/
 
+#print FermatPsp.coprime_of_fermatPsp /-
 /-- If `n` is a Fermat pseudoprime to base `b`, then `n` is coprime with `b`, assuming that `b` is
 positive.
 
@@ -128,7 +144,9 @@ theorem coprime_of_fermatPsp {n b : ℕ} (h : FermatPsp n b) (h₁ : 1 ≤ b) :
   rcases h with ⟨hp, hn₁, hn₂⟩
   exact coprime_of_probable_prime hp (by linarith) h₁
 #align fermat_psp.coprime_of_fermat_psp FermatPsp.coprime_of_fermatPsp
+-/
 
+#print FermatPsp.base_one /-
 /-- All composite numbers are Fermat pseudoprimes to base 1.
 -/
 theorem base_one {n : ℕ} (h₁ : 1 < n) (h₂ : ¬n.Prime) : FermatPsp n 1 :=
@@ -136,6 +154,7 @@ theorem base_one {n : ℕ} (h₁ : 1 < n) (h₂ : ¬n.Prime) : FermatPsp n 1 :=
   refine' ⟨show n ∣ 1 ^ (n - 1) - 1 from _, h₂, h₁⟩
   exact show 0 = 1 ^ (n - 1) - 1 by norm_num ▸ dvd_zero n
 #align fermat_psp.base_one FermatPsp.base_one
+-/
 
 -- Lemmas that are needed to prove statements in this file, but aren't directly related to Fermat
 -- pseudoprimes
@@ -239,9 +258,9 @@ private theorem psp_from_prime_psp {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_p
   -- Used to prove that `2 * p * (b ^ 2 - 1) ∣ (b ^ 2 - 1) * (A * B - 1)`.
   have ha₁ : (b ^ 2 - 1) * (A * B - 1) = b * (b ^ (p - 1) - 1) * (b ^ p + b) :=
     by
-    apply_fun fun x => x * (b ^ 2 - 1)  at AB_id 
+    apply_fun fun x => x * (b ^ 2 - 1) at AB_id 
     rw [Nat.div_mul_cancel hd] at AB_id 
-    apply_fun fun x => x - (b ^ 2 - 1)  at AB_id 
+    apply_fun fun x => x - (b ^ 2 - 1) at AB_id 
     nth_rw 2 [← one_mul (b ^ 2 - 1)] at AB_id 
     rw [← Nat.mul_sub_right_distrib, mul_comm] at AB_id 
     rw [AB_id]
@@ -356,6 +375,7 @@ private theorem psp_from_prime_gt_p {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_
   have : p ≤ 2 * p - 2 := le_tsub_of_add_le_left this
   exact Nat.lt_of_le_of_lt this (pow_gt_exponent _ b_ge_two)
 
+#print FermatPsp.exists_infinite_pseudoprimes /-
 /-- For all positive bases, there exist Fermat infinite pseudoprimes to that base.
 Given in this form: for all numbers `b ≥ 1` and `m`, there exists a pseudoprime `n` to base `b` such
 that `m ≤ n`. This form is similar to `nat.exists_infinite_primes`.
@@ -395,7 +415,9 @@ theorem exists_infinite_pseudoprimes {b : ℕ} (h : 1 ≤ b) (m : ℕ) : ∃ n :
     have : ¬Nat.Prime (2 * (m + 2)) := Nat.not_prime_mul (by norm_num) (by norm_num)
     exact ⟨base_one (by linarith) this, by linarith⟩
 #align fermat_psp.exists_infinite_pseudoprimes FermatPsp.exists_infinite_pseudoprimes
+-/
 
+#print FermatPsp.frequently_atTop_fermatPsp /-
 theorem frequently_atTop_fermatPsp {b : ℕ} (h : 1 ≤ b) : ∃ᶠ n in Filter.atTop, FermatPsp n b :=
   by
   -- Based on the proof of `nat.frequently_at_top_modeq_one`
@@ -403,13 +425,15 @@ theorem frequently_atTop_fermatPsp {b : ℕ} (h : 1 ≤ b) : ∃ᶠ n in Filter.
   obtain ⟨p, hp⟩ := exists_infinite_pseudoprimes h n
   exact ⟨p, hp.2, hp.1⟩
 #align fermat_psp.frequently_at_top_fermat_psp FermatPsp.frequently_atTop_fermatPsp
+-/
 
+#print FermatPsp.infinite_setOf_prime_modeq_one /-
 /-- Infinite set variant of `exists_infinite_pseudoprimes`
 -/
-theorem infinite_setOf_prime_modeq_one {b : ℕ} (h : 1 ≤ b) :
-    Set.Infinite { n : ℕ | FermatPsp n b } :=
+theorem infinite_setOf_prime_modeq_one {b : ℕ} (h : 1 ≤ b) : Set.Infinite {n : ℕ | FermatPsp n b} :=
   Nat.frequently_atTop_iff_infinite.mp (frequently_atTop_fermatPsp h)
 #align fermat_psp.infinite_set_of_prime_modeq_one FermatPsp.infinite_setOf_prime_modeq_one
+-/
 
 end FermatPsp
 

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

@@ -239,11 +239,11 @@ private theorem psp_from_prime_psp {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_p
   -- Used to prove that `2 * p * (b ^ 2 - 1) ∣ (b ^ 2 - 1) * (A * B - 1)`.
   have ha₁ : (b ^ 2 - 1) * (A * B - 1) = b * (b ^ (p - 1) - 1) * (b ^ p + b) :=
     by
-    apply_fun fun x => x * (b ^ 2 - 1)  at AB_id
-    rw [Nat.div_mul_cancel hd] at AB_id
-    apply_fun fun x => x - (b ^ 2 - 1)  at AB_id
-    nth_rw 2 [← one_mul (b ^ 2 - 1)] at AB_id
-    rw [← Nat.mul_sub_right_distrib, mul_comm] at AB_id
+    apply_fun fun x => x * (b ^ 2 - 1)  at AB_id 
+    rw [Nat.div_mul_cancel hd] at AB_id 
+    apply_fun fun x => x - (b ^ 2 - 1)  at AB_id 
+    nth_rw 2 [← one_mul (b ^ 2 - 1)] at AB_id 
+    rw [← Nat.mul_sub_right_distrib, mul_comm] at AB_id 
     rw [AB_id]
     exact bp_helper hi_b hi_p
   -- If `b` is even, then `b^p` is also even, so `2 ∣ b^p + b`
@@ -277,8 +277,8 @@ private theorem psp_from_prime_psp {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_p
     cases' this with c hc
     have : b ^ 2 - 1 ∣ (b ^ 2) ^ c - 1 := by
       simpa only [one_pow] using nat_sub_dvd_pow_sub_pow _ 1 c
-    have : b ^ 2 - 1 ∣ b ^ (2 * c) - 1 := by rwa [← pow_mul] at this
-    rwa [← hc] at this
+    have : b ^ 2 - 1 ∣ b ^ (2 * c) - 1 := by rwa [← pow_mul] at this 
+    rwa [← hc] at this 
   -- Used to prove that `2 * p` divides `A * B - 1`
   have ha₅ : 2 * p * (b ^ 2 - 1) ∣ (b ^ 2 - 1) * (A * B - 1) :=
     by
@@ -289,7 +289,7 @@ private theorem psp_from_prime_psp {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_p
     -- know that `2 * p ∣ b ^ p + b`
     have q₁ : Nat.coprime p (b ^ 2 - 1) :=
       haveI q₂ : ¬p ∣ b ^ 2 - 1 := by
-        rw [mul_comm] at not_dvd
+        rw [mul_comm] at not_dvd 
         exact mt (fun h : p ∣ b ^ 2 - 1 => dvd_mul_of_dvd_left h _) not_dvd
       (Nat.Prime.coprime_iff_not_dvd p_prime).mpr q₂
     have q₂ : p * (b ^ 2 - 1) ∣ b ^ (p - 1) - 1 := Nat.coprime.mul_dvd_of_dvd_of_dvd q₁ ha₃ ha₄
@@ -298,7 +298,7 @@ private theorem psp_from_prime_psp {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_p
       dvd_mul_of_dvd_right q₃ _
     rwa [mul_assoc, mul_comm, mul_assoc b]
   have ha₆ : 2 * p ∣ A * B - 1 := by
-    rw [mul_comm] at ha₅
+    rw [mul_comm] at ha₅ 
     exact Nat.dvd_of_mul_dvd_mul_left hi_bsquared ha₅
   -- `A * B` divides `b ^ (2 * p) - 1` because `A * B * (b ^ 2 - 1) = b ^ (2 * p) - 1`.
   -- This can be proven by multiplying both sides of `AB_id` by `b ^ 2 - 1`.
@@ -336,7 +336,7 @@ private theorem psp_from_prime_gt_p {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_
       Nat.div_lt_div_of_lt_of_dvd AB_dvd h
     have h₂ : 0 < b ^ 2 - 1 := by
       linarith [show 3 ≤ b ^ 2 - 1 from le_tsub_of_add_le_left (show 4 ≤ b ^ 2 by nlinarith)]
-    rwa [Nat.mul_div_cancel _ h₂] at h₁
+    rwa [Nat.mul_div_cancel _ h₂] at h₁ 
   rw [Nat.mul_sub_left_distrib, mul_one, pow_mul]
   nth_rw_rhs 1 [← Nat.sub_add_cancel (show 1 ≤ p by linarith)]
   rw [pow_succ (b ^ 2)]

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

@@ -143,7 +143,6 @@ section HelperLemmas
 
 private theorem pow_gt_exponent {a : ℕ} (b : ℕ) (h : 2 ≤ a) : b < a ^ b :=
   lt_of_lt_of_le (Nat.lt_two_pow b) <| Nat.pow_le_pow_of_le_left h _
-#align fermat_psp.pow_gt_exponent fermat_psp.pow_gt_exponent
 
 private theorem a_id_helper {a b : ℕ} (ha : 2 ≤ a) (hb : 2 ≤ b) : 2 ≤ (a ^ b - 1) / (a - 1) :=
   by
@@ -152,7 +151,6 @@ private theorem a_id_helper {a b : ℕ} (ha : 2 ≤ a) (hb : 2 ≤ b) : 2 ≤ (a
   rw [Nat.lt_div_iff_mul_lt h₁, mul_one, tsub_lt_tsub_iff_right (Nat.le_of_succ_le ha)]
   convert pow_lt_pow (Nat.lt_of_succ_le ha) hb
   rw [pow_one]
-#align fermat_psp.a_id_helper fermat_psp.a_id_helper
 
 private theorem b_id_helper {a b : ℕ} (ha : 2 ≤ a) (hb : 2 < b) : 2 ≤ (a ^ b + 1) / (a + 1) :=
   by
@@ -163,7 +161,6 @@ private theorem b_id_helper {a b : ℕ} (ha : 2 ≤ a) (hb : 2 < b) : 2 ≤ (a ^
     _ = a ^ 3 := by rw [pow_succ' a 2]
     _ ≤ a ^ b := pow_le_pow (Nat.le_of_succ_le ha) hb
     
-#align fermat_psp.b_id_helper fermat_psp.b_id_helper
 
 private theorem AB_id_helper (b p : ℕ) (hb : 2 ≤ b) (hp : Odd p) :
     (b ^ p - 1) / (b - 1) * ((b ^ p + 1) / (b + 1)) = (b ^ (2 * p) - 1) / (b ^ 2 - 1) :=
@@ -173,7 +170,6 @@ private theorem AB_id_helper (b p : ℕ) (hb : 2 ≤ b) (hp : Odd p) :
   convert Nat.div_mul_div_comm q₁ q₂ <;> rw [mul_comm (_ - 1), ← Nat.sq_sub_sq]
   · ring
   · simp
-#align fermat_psp.AB_id_helper fermat_psp.AB_id_helper
 
 /-- Used in the proof of `psp_from_prime_psp`
 -/
@@ -193,7 +189,6 @@ private theorem bp_helper {b p : ℕ} (hb : 0 < b) (hp : 1 ≤ p) :
     _ = (b * b ^ (p - 1) - b * 1) * (b ^ p + b) := by rw [mul_one]
     _ = b * (b ^ (p - 1) - 1) * (b ^ p + b) := by rw [Nat.mul_sub_left_distrib]
     
-#align fermat_psp.bp_helper fermat_psp.bp_helper
 
 end HelperLemmas
 
@@ -210,7 +205,6 @@ because those are the hypotheses for `psp_from_prime_psp`.
 -/
 private def psp_from_prime (b : ℕ) (p : ℕ) : ℕ :=
   (b ^ p - 1) / (b - 1) * ((b ^ p + 1) / (b + 1))
-#align fermat_psp.psp_from_prime fermat_psp.psp_from_prime
 
 /--
 This is a proof that the number produced using `psp_from_prime` is actually pseudoprime to base `b`.
@@ -322,7 +316,6 @@ private theorem psp_from_prime_psp {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_p
   -- We have proved that `A * B ∣ b ^ (2 * p) - 1` and `b ^ (2 * p) - 1 ∣ b ^ (A * B - 1) - 1`.
   -- Therefore, `A * B ∣ b ^ (A * B - 1) - 1`.
   exact dvd_trans ha₇ ha₈
-#align fermat_psp.psp_from_prime_psp fermat_psp.psp_from_prime_psp
 
 /--
 This is a proof that the number produced using `psp_from_prime` is greater than the prime `p` used
@@ -362,7 +355,6 @@ private theorem psp_from_prime_gt_p {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_
   have : 2 + p ≤ 2 * p := by linarith
   have : p ≤ 2 * p - 2 := le_tsub_of_add_le_left this
   exact Nat.lt_of_le_of_lt this (pow_gt_exponent _ b_ge_two)
-#align fermat_psp.psp_from_prime_gt_p fermat_psp.psp_from_prime_gt_p
 
 /-- For all positive bases, there exist Fermat infinite pseudoprimes to that base.
 Given in this form: for all numbers `b ≥ 1` and `m`, there exists a pseudoprime `n` to base `b` such

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

@@ -365,7 +365,7 @@ theorem exists_infinite_pseudoprimes {b : ℕ} (h : 1 ≤ b) (m : ℕ) :
   · have h₁ : b = 1 := by omega
     rw [h₁]
     use 2 * (m + 2)
-    have : ¬Nat.Prime (2 * (m + 2)) := Nat.not_prime_mul (by norm_num) (by norm_num)
+    have : ¬Nat.Prime (2 * (m + 2)) := Nat.not_prime_mul (by omega) (by omega)
     exact ⟨fermatPsp_base_one (by omega) this, by omega⟩
 #align fermat_psp.exists_infinite_pseudoprimes Nat.exists_infinite_pseudoprimes
 

Move basic Nat lemmas from Data.Nat.Order.Basic and Data.Nat.Pow to Data.Nat.Defs. Most proofs need adapting, but that's easily solved by replacing the general mathlib lemmas by the new Std Nat-specific lemmas and using omega.

Other changes

• Move the last few lemmas left in Data.Nat.Pow to Algebra.GroupPower.Order
• Move the deprecated aliases from Data.Nat.Pow to Algebra.GroupPower.Order
• Move the bit/bit0/bit1 lemmas from Data.Nat.Order.Basic to Data.Nat.Bits
• Fix some fallout from not importing Data.Nat.Order.Basic anymore
• Add a few Nat-specific lemmas to help fix the fallout (look for nolint simpNF)
• Turn Nat.mul_self_le_mul_self_iff and Nat.mul_self_lt_mul_self_iff around (they were misnamed)
• Make more arguments to Nat.one_lt_pow implicit

@@ -153,8 +153,7 @@ private theorem AB_id_helper (b p : ℕ) (_ : 2 ≤ b) (hp : Odd p) :
   have q₁ : b - 1 ∣ b ^ p - 1 := by simpa only [one_pow] using nat_sub_dvd_pow_sub_pow b 1 p
   have q₂ : b + 1 ∣ b ^ p + 1 := by simpa only [one_pow] using hp.nat_add_dvd_pow_add_pow b 1
   convert Nat.div_mul_div_comm q₁ q₂ using 2 <;> rw [mul_comm (_ - 1), ← Nat.sq_sub_sq]
-  · ring_nf
-  · simp
+  ring_nf
 
 /-- Used in the proof of `psp_from_prime_psp`
 -/

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>

@@ -126,7 +126,8 @@ theorem coprime_of_fermatPsp {n b : ℕ} (h : FermatPsp n b) (h₁ : 1 ≤ b) :
 -/
 theorem fermatPsp_base_one {n : ℕ} (h₁ : 1 < n) (h₂ : ¬n.Prime) : FermatPsp n 1 := by
   refine' ⟨show n ∣ 1 ^ (n - 1) - 1 from _, h₂, h₁⟩
-  exact show 0 = 1 ^ (n - 1) - 1 by norm_num ▸ dvd_zero n
+  exact show 0 = 1 ^ (n - 1) - 1 by
+    set_option tactic.skipAssignedInstances false in norm_num ▸ dvd_zero n
 #align fermat_psp.base_one Nat.fermatPsp_base_one
 
 -- Lemmas that are needed to prove statements in this file, but aren't directly related to Fermat
@@ -144,7 +145,7 @@ private theorem b_id_helper {a b : ℕ} (ha : 2 ≤ a) (hb : 2 < b) : 2 ≤ (a ^
   apply Nat.succ_le_succ
   calc
     2 * a + 1 ≤ a ^ 2 * a := by nlinarith
-    _ = a ^ 3 := by rw [pow_succ a 2]
+    _ = a ^ 3 := by rw [Nat.pow_succ a 2]
     _ ≤ a ^ b := pow_le_pow_right (Nat.le_of_succ_le ha) hb
 
 private theorem AB_id_helper (b p : ℕ) (_ : 2 ≤ b) (hp : Odd p) :
@@ -313,7 +314,7 @@ private theorem psp_from_prime_gt_p {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_
     rwa [Nat.mul_div_cancel _ h₂] at h₁
   rw [Nat.mul_sub_left_distrib, mul_one, pow_mul]
   conv_rhs => rw [← Nat.sub_add_cancel (show 1 ≤ p by omega)]
-  rw [pow_succ (b ^ 2)]
+  rw [Nat.pow_succ (b ^ 2)]
   suffices h : p * b ^ 2 < (b ^ 2) ^ (p - 1) * b ^ 2 by
     apply gt_of_ge_of_gt
     · exact tsub_le_tsub_left (one_le_of_lt p_gt_two) ((b ^ 2) ^ (p - 1) * b ^ 2)

I ran tryAtEachStep on all files under Mathlib to find all locations where omega succeeds. For each that was a linarith without an only, I tried replacing it with omega, and I verified that elaboration time got smaller. (In almost all cases, there was a noticeable speedup.) I also replaced some slow aesops along the way.

@@ -93,9 +93,9 @@ theorem coprime_of_probablePrime {n b : ℕ} (h : ProbablePrime n b) (h₁ : 1 
     -- suffices to show that `n - 1` isn't zero. However, we know that `n - 1` isn't zero because we
     -- assumed `2 ≤ n` when doing `by_cases`.
     refine' dvd_of_mul_right_dvd (dvd_pow_self (k * j) _)
-    linarith [tsub_pos_of_lt (one_lt_two.trans_le h₃)]
+    omega
   -- If `n = 1`, then it follows trivially that `n` is coprime with `b`.
-  · rw [show n = 1 by linarith]
+  · rw [show n = 1 by omega]
     norm_num
 #align fermat_psp.coprime_of_probable_prime Nat.coprime_of_probablePrime
 
@@ -119,7 +119,7 @@ This lemma is a small wrapper based on `coprime_of_probablePrime`
 -/
 theorem coprime_of_fermatPsp {n b : ℕ} (h : FermatPsp n b) (h₁ : 1 ≤ b) : Nat.Coprime n b := by
   rcases h with ⟨hp, _, hn₂⟩
-  exact coprime_of_probablePrime hp (by linarith) h₁
+  exact coprime_of_probablePrime hp (by omega) h₁
 #align fermat_psp.coprime_of_fermat_psp Nat.coprime_of_fermatPsp
 
 /-- All composite numbers are Fermat pseudoprimes to base 1.
@@ -204,12 +204,12 @@ private theorem psp_from_prime_psp {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_p
   have hi_A : 1 < A := a_id_helper (Nat.succ_le_iff.mp b_ge_two) (Nat.Prime.one_lt p_prime)
   have hi_B : 1 < B := b_id_helper (Nat.succ_le_iff.mp b_ge_two) p_gt_two
   have hi_AB : 1 < A * B := one_lt_mul'' hi_A hi_B
-  have hi_b : 0 < b := by linarith
+  have hi_b : 0 < b := by omega
   have hi_p : 1 ≤ p := Nat.one_le_of_lt p_gt_two
   have hi_bsquared : 0 < b ^ 2 - 1 := by
     -- Porting note: was `by nlinarith [Nat.one_le_pow 2 b hi_b]`
     have h0 := mul_le_mul b_ge_two b_ge_two zero_le_two hi_b.le
-    have h1 : 1 < 2 * 2 := by linarith
+    have h1 : 1 < 2 * 2 := by omega
     have := tsub_pos_of_lt (h1.trans_le h0)
     rwa [pow_two]
   have hi_bpowtwop : 1 ≤ b ^ (2 * p) := Nat.one_le_pow (2 * p) b hi_b
@@ -312,7 +312,7 @@ private theorem psp_from_prime_gt_p {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_
       linarith [show 3 ≤ b ^ 2 - 1 from le_tsub_of_add_le_left (show 4 ≤ b ^ 2 by nlinarith)]
     rwa [Nat.mul_div_cancel _ h₂] at h₁
   rw [Nat.mul_sub_left_distrib, mul_one, pow_mul]
-  conv_rhs => rw [← Nat.sub_add_cancel (show 1 ≤ p by linarith)]
+  conv_rhs => rw [← Nat.sub_add_cancel (show 1 ≤ p by omega)]
   rw [pow_succ (b ^ 2)]
   suffices h : p * b ^ 2 < (b ^ 2) ^ (p - 1) * b ^ 2 by
     apply gt_of_ge_of_gt
@@ -321,11 +321,11 @@ private theorem psp_from_prime_gt_p {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_
       exact tsub_lt_tsub_right_of_le this h
   suffices h : p < (b ^ 2) ^ (p - 1) by
     have : 4 ≤ b ^ 2 := by nlinarith
-    have : 0 < b ^ 2 := by linarith
+    have : 0 < b ^ 2 := by omega
     exact mul_lt_mul_of_pos_right h this
   rw [← pow_mul, Nat.mul_sub_left_distrib, mul_one]
-  have : 2 ≤ 2 * p - 2 := le_tsub_of_add_le_left (show 4 ≤ 2 * p by linarith)
-  have : 2 + p ≤ 2 * p := by linarith
+  have : 2 ≤ 2 * p - 2 := le_tsub_of_add_le_left (show 4 ≤ 2 * p by omega)
+  have : 2 + p ≤ 2 * p := by omega
   have : p ≤ 2 * p - 2 := le_tsub_of_add_le_left this
   exact this.trans_lt (lt_pow_self b_ge_two _)
 
@@ -349,7 +349,7 @@ theorem exists_infinite_pseudoprimes {b : ℕ} (h : 1 ≤ b) (m : ℕ) :
     have h₂ : 4 ≤ b ^ 2 := pow_le_pow_left' b_ge_two 2
     have h₃ : 0 < b ^ 2 - 1 := tsub_pos_of_lt (gt_of_ge_of_gt h₂ (by norm_num))
     have h₄ : 0 < b * (b ^ 2 - 1) := mul_pos h₁ h₃
-    have h₅ : b * (b ^ 2 - 1) < p := by linarith
+    have h₅ : b * (b ^ 2 - 1) < p := by omega
     have h₆ : ¬p ∣ b * (b ^ 2 - 1) := Nat.not_dvd_of_pos_of_lt h₄ h₅
     have h₇ : b ≤ b * (b ^ 2 - 1) := Nat.le_mul_of_pos_right _ h₃
     have h₈ : 2 ≤ b * (b ^ 2 - 1) := le_trans b_ge_two h₇
@@ -358,15 +358,15 @@ theorem exists_infinite_pseudoprimes {b : ℕ} (h : 1 ≤ b) (m : ℕ) :
     use psp_from_prime b p
     constructor
     · exact psp_from_prime_psp b_ge_two hp₂ h₉ h₆
-    · exact le_trans (show m ≤ p by linarith) (le_of_lt h₁₀)
+    · exact le_trans (show m ≤ p by omega) (le_of_lt h₁₀)
   -- If `¬2 ≤ b`, then `b = 1`. Since all composite numbers are pseudoprimes to base 1, we can pick
   -- any composite number greater than m. We choose `2 * (m + 2)` because it is greater than `m` and
   -- is composite for all natural numbers `m`.
-  · have h₁ : b = 1 := by linarith
+  · have h₁ : b = 1 := by omega
     rw [h₁]
     use 2 * (m + 2)
     have : ¬Nat.Prime (2 * (m + 2)) := Nat.not_prime_mul (by norm_num) (by norm_num)
-    exact ⟨fermatPsp_base_one (by linarith) this, by linarith⟩
+    exact ⟨fermatPsp_base_one (by omega) this, by omega⟩
 #align fermat_psp.exists_infinite_pseudoprimes Nat.exists_infinite_pseudoprimes
 
 theorem frequently_atTop_fermatPsp {b : ℕ} (h : 1 ≤ b) : ∃ᶠ n in Filter.atTop, FermatPsp n b := by

No changes to tactic file, it's just boring fixes throughout the library.

This follows on from #6964.

Co-authored-by: sgouezel <sebastien.gouezel@univ-rennes1.fr> Co-authored-by: Eric Wieser <wieser.eric@gmail.com>

@@ -258,8 +258,7 @@ private theorem psp_from_prime_psp {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_p
     rwa [← hc] at this
   -- Used to prove that `2 * p` divides `A * B - 1`
   have ha₅ : 2 * p * (b ^ 2 - 1) ∣ (b ^ 2 - 1) * (A * B - 1) := by
-    suffices q : 2 * p * (b ^ 2 - 1) ∣ b * (b ^ (p - 1) - 1) * (b ^ p + b)
-    · rwa [ha₁]
+    suffices q : 2 * p * (b ^ 2 - 1) ∣ b * (b ^ (p - 1) - 1) * (b ^ p + b) by rwa [ha₁]
     -- We already proved that `b ^ 2 - 1 ∣ b ^ (p - 1) - 1`.
     -- Since `2 ∣ b ^ p + b` and `p ∣ b ^ p + b`, if we show that 2 and p are coprime, then we
     -- know that `2 * p ∣ b ^ p + b`
@@ -306,8 +305,8 @@ private theorem psp_from_prime_gt_p {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_
       AB_id_helper _ _ b_ge_two (p_prime.odd_of_ne_two p_gt_two.ne.symm)]
   have AB_dvd : b ^ 2 - 1 ∣ b ^ (2 * p) - 1 := by
     simpa only [one_pow, pow_mul] using nat_sub_dvd_pow_sub_pow _ 1 p
-  suffices h : p * (b ^ 2 - 1) < b ^ (2 * p) - 1
-  · have h₁ : p * (b ^ 2 - 1) / (b ^ 2 - 1) < (b ^ (2 * p) - 1) / (b ^ 2 - 1) :=
+  suffices h : p * (b ^ 2 - 1) < b ^ (2 * p) - 1 by
+    have h₁ : p * (b ^ 2 - 1) / (b ^ 2 - 1) < (b ^ (2 * p) - 1) / (b ^ 2 - 1) :=
       Nat.div_lt_div_of_lt_of_dvd AB_dvd h
     have h₂ : 0 < b ^ 2 - 1 := by
       linarith [show 3 ≤ b ^ 2 - 1 from le_tsub_of_add_le_left (show 4 ≤ b ^ 2 by nlinarith)]
@@ -315,13 +314,13 @@ private theorem psp_from_prime_gt_p {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_
   rw [Nat.mul_sub_left_distrib, mul_one, pow_mul]
   conv_rhs => rw [← Nat.sub_add_cancel (show 1 ≤ p by linarith)]
   rw [pow_succ (b ^ 2)]
-  suffices h : p * b ^ 2 < (b ^ 2) ^ (p - 1) * b ^ 2
-  · apply gt_of_ge_of_gt
+  suffices h : p * b ^ 2 < (b ^ 2) ^ (p - 1) * b ^ 2 by
+    apply gt_of_ge_of_gt
     · exact tsub_le_tsub_left (one_le_of_lt p_gt_two) ((b ^ 2) ^ (p - 1) * b ^ 2)
     · have : p ≤ p * b ^ 2 := Nat.le_mul_of_pos_right _ (show 0 < b ^ 2 by nlinarith)
       exact tsub_lt_tsub_right_of_le this h
-  suffices h : p < (b ^ 2) ^ (p - 1)
-  · have : 4 ≤ b ^ 2 := by nlinarith
+  suffices h : p < (b ^ 2) ^ (p - 1) by
+    have : 4 ≤ b ^ 2 := by nlinarith
     have : 0 < b ^ 2 := by linarith
     exact mul_lt_mul_of_pos_right h this
   rw [← pow_mul, Nat.mul_sub_left_distrib, mul_one]

Assume _ ≠ 1 instead of 1 < _ in Nat.not_prime_mul, Nat.not_prime_mul', Int.not_prime_of_int_mul.

@@ -216,7 +216,7 @@ private theorem psp_from_prime_psp {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_p
   have hi_bpowpsubone : 1 ≤ b ^ (p - 1) := Nat.one_le_pow (p - 1) b hi_b
   -- Other useful facts
   have p_odd : Odd p := p_prime.odd_of_ne_two p_gt_two.ne.symm
-  have AB_not_prime : ¬Nat.Prime (A * B) := Nat.not_prime_mul hi_A hi_B
+  have AB_not_prime : ¬Nat.Prime (A * B) := Nat.not_prime_mul hi_A.ne' hi_B.ne'
   have AB_id : A * B = (b ^ (2 * p) - 1) / (b ^ 2 - 1) := AB_id_helper _ _ b_ge_two p_odd
   have hd : b ^ 2 - 1 ∣ b ^ (2 * p) - 1 := by
     simpa only [one_pow, pow_mul] using nat_sub_dvd_pow_sub_pow _ 1 p

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

@@ -318,7 +318,7 @@ private theorem psp_from_prime_gt_p {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_
   suffices h : p * b ^ 2 < (b ^ 2) ^ (p - 1) * b ^ 2
   · apply gt_of_ge_of_gt
     · exact tsub_le_tsub_left (one_le_of_lt p_gt_two) ((b ^ 2) ^ (p - 1) * b ^ 2)
-    · have : p ≤ p * b ^ 2 := Nat.le_mul_of_pos_right (show 0 < b ^ 2 by nlinarith)
+    · have : p ≤ p * b ^ 2 := Nat.le_mul_of_pos_right _ (show 0 < b ^ 2 by nlinarith)
       exact tsub_lt_tsub_right_of_le this h
   suffices h : p < (b ^ 2) ^ (p - 1)
   · have : 4 ≤ b ^ 2 := by nlinarith
@@ -352,7 +352,7 @@ theorem exists_infinite_pseudoprimes {b : ℕ} (h : 1 ≤ b) (m : ℕ) :
     have h₄ : 0 < b * (b ^ 2 - 1) := mul_pos h₁ h₃
     have h₅ : b * (b ^ 2 - 1) < p := by linarith
     have h₆ : ¬p ∣ b * (b ^ 2 - 1) := Nat.not_dvd_of_pos_of_lt h₄ h₅
-    have h₇ : b ≤ b * (b ^ 2 - 1) := Nat.le_mul_of_pos_right h₃
+    have h₇ : b ≤ b * (b ^ 2 - 1) := Nat.le_mul_of_pos_right _ h₃
     have h₈ : 2 ≤ b * (b ^ 2 - 1) := le_trans b_ge_two h₇
     have h₉ : 2 < p := gt_of_gt_of_ge h₅ h₈
     have h₁₀ := psp_from_prime_gt_p b_ge_two hp₂ h₉

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.

Renames

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

Lemmas added

• 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.

Lemmas removed

• 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.

Other changes

• A bunch of proofs have been golfed.
• Some lemma assumptions have been turned from 0 < n or 1 ≤ n to n ≠ 0.
• A few Nat lemmas have been protected.
• One docstring has been fixed.

@@ -133,14 +133,11 @@ theorem fermatPsp_base_one {n : ℕ} (h₁ : 1 < n) (h₂ : ¬n.Prime) : FermatP
 -- pseudoprimes
 section HelperLemmas
 
-private theorem pow_gt_exponent {a : ℕ} (b : ℕ) (h : 2 ≤ a) : b < a ^ b :=
-  lt_of_lt_of_le (Nat.lt_two_pow b) <| Nat.pow_le_pow_of_le_left h _
-
 private theorem a_id_helper {a b : ℕ} (ha : 2 ≤ a) (hb : 2 ≤ b) : 2 ≤ (a ^ b - 1) / (a - 1) := by
   change 1 < _
   have h₁ : a - 1 ∣ a ^ b - 1 := by simpa only [one_pow] using nat_sub_dvd_pow_sub_pow a 1 b
   rw [Nat.lt_div_iff_mul_lt h₁, mul_one, tsub_lt_tsub_iff_right (Nat.le_of_succ_le ha)]
-  exact self_lt_pow (Nat.lt_of_succ_le ha) hb
+  exact lt_self_pow (Nat.lt_of_succ_le ha) hb
 
 private theorem b_id_helper {a b : ℕ} (ha : 2 ≤ a) (hb : 2 < b) : 2 ≤ (a ^ b + 1) / (a + 1) := by
   rw [Nat.le_div_iff_mul_le (Nat.zero_lt_succ _)]
@@ -148,7 +145,7 @@ private theorem b_id_helper {a b : ℕ} (ha : 2 ≤ a) (hb : 2 < b) : 2 ≤ (a ^
   calc
     2 * a + 1 ≤ a ^ 2 * a := by nlinarith
     _ = a ^ 3 := by rw [pow_succ a 2]
-    _ ≤ a ^ b := pow_le_pow (Nat.le_of_succ_le ha) hb
+    _ ≤ a ^ b := pow_le_pow_right (Nat.le_of_succ_le ha) hb
 
 private theorem AB_id_helper (b p : ℕ) (_ : 2 ≤ b) (hp : Odd p) :
     (b ^ p - 1) / (b - 1) * ((b ^ p + 1) / (b + 1)) = (b ^ (2 * p) - 1) / (b ^ 2 - 1) := by
@@ -331,7 +328,7 @@ private theorem psp_from_prime_gt_p {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_
   have : 2 ≤ 2 * p - 2 := le_tsub_of_add_le_left (show 4 ≤ 2 * p by linarith)
   have : 2 + p ≤ 2 * p := by linarith
   have : p ≤ 2 * p - 2 := le_tsub_of_add_le_left this
-  exact Nat.lt_of_le_of_lt this (pow_gt_exponent _ b_ge_two)
+  exact this.trans_lt (lt_pow_self b_ge_two _)
 
 /-- For all positive bases, there exist infinite **Fermat pseudoprimes** to that base.
 Given in this form: for all numbers `b ≥ 1` and `m`, there exists a pseudoprime `n` to base `b` such
@@ -350,7 +347,7 @@ theorem exists_infinite_pseudoprimes {b : ℕ} (h : 1 ≤ b) (m : ℕ) :
     cases' h with p hp
     cases' hp with hp₁ hp₂
     have h₁ : 0 < b := pos_of_gt (Nat.succ_le_iff.mp b_ge_two)
-    have h₂ : 4 ≤ b ^ 2 := pow_le_pow_of_le_left' b_ge_two 2
+    have h₂ : 4 ≤ b ^ 2 := pow_le_pow_left' b_ge_two 2
     have h₃ : 0 < b ^ 2 - 1 := tsub_pos_of_lt (gt_of_ge_of_gt h₂ (by norm_num))
     have h₄ : 0 < b * (b ^ 2 - 1) := mul_pos h₁ h₃
     have h₅ : b * (b ^ 2 - 1) < p := by linarith

@@ -333,7 +333,7 @@ private theorem psp_from_prime_gt_p {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_
   have : p ≤ 2 * p - 2 := le_tsub_of_add_le_left this
   exact Nat.lt_of_le_of_lt this (pow_gt_exponent _ b_ge_two)
 
-/-- For all positive bases, there exist Fermat infinite pseudoprimes to that base.
+/-- For all positive bases, there exist infinite **Fermat pseudoprimes** to that base.
 Given in this form: for all numbers `b ≥ 1` and `m`, there exists a pseudoprime `n` to base `b` such
 that `m ≤ n`. This form is similar to `Nat.exists_infinite_primes`.
 -/

We still have the exact_mod_cast tactic, used in a few places, which somehow (?) works a little bit harder to prevent the expected type influencing the elaboration of the term. I would like to get to the bottom of this, and it will be easier once the only usages of exact_mod_cast are the ones that don't work using the term elaborator by itself.

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

@@ -102,14 +102,14 @@ theorem coprime_of_probablePrime {n b : ℕ} (h : ProbablePrime n b) (h₁ : 1 
 theorem probablePrime_iff_modEq (n : ℕ) {b : ℕ} (h : 1 ≤ b) :
     ProbablePrime n b ↔ b ^ (n - 1) ≡ 1 [MOD n] := by
   have : 1 ≤ b ^ (n - 1) := one_le_pow_of_one_le h (n - 1)
-  -- For exact_mod_cast
+  -- For exact mod_cast
   rw [Nat.ModEq.comm]
   constructor
   · intro h₁
     apply Nat.modEq_of_dvd
-    exact_mod_cast h₁
+    exact mod_cast h₁
   · intro h₁
-    exact_mod_cast Nat.ModEq.dvd h₁
+    exact mod_cast Nat.ModEq.dvd h₁
 #align fermat_psp.probable_prime_iff_modeq Nat.probablePrime_iff_modEq
 
 /-- If `n` is a Fermat pseudoprime to base `b`, then `n` is coprime with `b`, assuming that `b` is
@@ -247,8 +247,8 @@ private theorem psp_from_prime_psp {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_p
     have : p.Coprime b := Or.resolve_right (Nat.coprime_or_dvd_of_prime p_prime b) this
     have : IsCoprime (b : ℤ) ↑p := this.symm.isCoprime
     have : ↑b ^ (p - 1) ≡ 1 [ZMOD ↑p] := Int.ModEq.pow_card_sub_one_eq_one p_prime this
-    have : ↑p ∣ ↑b ^ (p - 1) - ↑1 := by exact_mod_cast Int.ModEq.dvd (Int.ModEq.symm this)
-    exact_mod_cast this
+    have : ↑p ∣ ↑b ^ (p - 1) - ↑1 := mod_cast Int.ModEq.dvd (Int.ModEq.symm this)
+    exact mod_cast this
   -- Because `p - 1` is even, there is a `c` such that `2 * c = p - 1`. `nat_sub_dvd_pow_sub_pow`
   -- implies that `b ^ c - 1 ∣ (b ^ c) ^ 2 - 1`, and `(b ^ c) ^ 2 = b ^ (p - 1)`.
   have ha₄ : b ^ 2 - 1 ∣ b ^ (p - 1) - 1 := by

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

@@ -73,7 +73,7 @@ instance decidablePsp (n b : ℕ) : Decidable (FermatPsp n b) :=
 `n` and `b` are both positive.
 -/
 theorem coprime_of_probablePrime {n b : ℕ} (h : ProbablePrime n b) (h₁ : 1 ≤ n) (h₂ : 1 ≤ b) :
-    Nat.coprime n b := by
+    Nat.Coprime n b := by
   by_cases h₃ : 2 ≤ n
   · -- To prove that `n` is coprime with `b`, we need to show that for all prime factors of `n`,
     -- we can derive a contradiction if `n` divides `b`.
@@ -117,7 +117,7 @@ positive.
 
 This lemma is a small wrapper based on `coprime_of_probablePrime`
 -/
-theorem coprime_of_fermatPsp {n b : ℕ} (h : FermatPsp n b) (h₁ : 1 ≤ b) : Nat.coprime n b := by
+theorem coprime_of_fermatPsp {n b : ℕ} (h : FermatPsp n b) (h₁ : 1 ≤ b) : Nat.Coprime n b := by
   rcases h with ⟨hp, _, hn₂⟩
   exact coprime_of_probablePrime hp (by linarith) h₁
 #align fermat_psp.coprime_of_fermat_psp Nat.coprime_of_fermatPsp
@@ -244,7 +244,7 @@ private theorem psp_from_prime_psp {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_p
   -- to prove this.
   have ha₃ : p ∣ b ^ (p - 1) - 1 := by
     have : ¬p ∣ b := mt (fun h : p ∣ b => dvd_mul_of_dvd_left h _) not_dvd
-    have : p.coprime b := Or.resolve_right (Nat.coprime_or_dvd_of_prime p_prime b) this
+    have : p.Coprime b := Or.resolve_right (Nat.coprime_or_dvd_of_prime p_prime b) this
     have : IsCoprime (b : ℤ) ↑p := this.symm.isCoprime
     have : ↑b ^ (p - 1) ≡ 1 [ZMOD ↑p] := Int.ModEq.pow_card_sub_one_eq_one p_prime this
     have : ↑p ∣ ↑b ^ (p - 1) - ↑1 := by exact_mod_cast Int.ModEq.dvd (Int.ModEq.symm this)
@@ -266,12 +266,12 @@ private theorem psp_from_prime_psp {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_p
     -- We already proved that `b ^ 2 - 1 ∣ b ^ (p - 1) - 1`.
     -- Since `2 ∣ b ^ p + b` and `p ∣ b ^ p + b`, if we show that 2 and p are coprime, then we
     -- know that `2 * p ∣ b ^ p + b`
-    have q₁ : Nat.coprime p (b ^ 2 - 1) :=
+    have q₁ : Nat.Coprime p (b ^ 2 - 1) :=
       haveI q₂ : ¬p ∣ b ^ 2 - 1 := by
         rw [mul_comm] at not_dvd
         exact mt (fun h : p ∣ b ^ 2 - 1 => dvd_mul_of_dvd_left h _) not_dvd
       (Nat.Prime.coprime_iff_not_dvd p_prime).mpr q₂
-    have q₂ : p * (b ^ 2 - 1) ∣ b ^ (p - 1) - 1 := Nat.coprime.mul_dvd_of_dvd_of_dvd q₁ ha₃ ha₄
+    have q₂ : p * (b ^ 2 - 1) ∣ b ^ (p - 1) - 1 := Nat.Coprime.mul_dvd_of_dvd_of_dvd q₁ ha₃ ha₄
     have q₃ : p * (b ^ 2 - 1) * 2 ∣ (b ^ (p - 1) - 1) * (b ^ p + b) := mul_dvd_mul q₂ ha₂
     have q₄ : p * (b ^ 2 - 1) * 2 ∣ b * ((b ^ (p - 1) - 1) * (b ^ p + b)) :=
       dvd_mul_of_dvd_right q₃ _

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.

@@ -73,7 +73,7 @@ instance decidablePsp (n b : ℕ) : Decidable (FermatPsp n b) :=
 `n` and `b` are both positive.
 -/
 theorem coprime_of_probablePrime {n b : ℕ} (h : ProbablePrime n b) (h₁ : 1 ≤ n) (h₂ : 1 ≤ b) :
-    Nat.Coprime n b := by
+    Nat.coprime n b := by
   by_cases h₃ : 2 ≤ n
   · -- To prove that `n` is coprime with `b`, we need to show that for all prime factors of `n`,
     -- we can derive a contradiction if `n` divides `b`.
@@ -117,7 +117,7 @@ positive.
 
 This lemma is a small wrapper based on `coprime_of_probablePrime`
 -/
-theorem coprime_of_fermatPsp {n b : ℕ} (h : FermatPsp n b) (h₁ : 1 ≤ b) : Nat.Coprime n b := by
+theorem coprime_of_fermatPsp {n b : ℕ} (h : FermatPsp n b) (h₁ : 1 ≤ b) : Nat.coprime n b := by
   rcases h with ⟨hp, _, hn₂⟩
   exact coprime_of_probablePrime hp (by linarith) h₁
 #align fermat_psp.coprime_of_fermat_psp Nat.coprime_of_fermatPsp
@@ -244,7 +244,7 @@ private theorem psp_from_prime_psp {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_p
   -- to prove this.
   have ha₃ : p ∣ b ^ (p - 1) - 1 := by
     have : ¬p ∣ b := mt (fun h : p ∣ b => dvd_mul_of_dvd_left h _) not_dvd
-    have : p.Coprime b := Or.resolve_right (Nat.coprime_or_dvd_of_prime p_prime b) this
+    have : p.coprime b := Or.resolve_right (Nat.coprime_or_dvd_of_prime p_prime b) this
     have : IsCoprime (b : ℤ) ↑p := this.symm.isCoprime
     have : ↑b ^ (p - 1) ≡ 1 [ZMOD ↑p] := Int.ModEq.pow_card_sub_one_eq_one p_prime this
     have : ↑p ∣ ↑b ^ (p - 1) - ↑1 := by exact_mod_cast Int.ModEq.dvd (Int.ModEq.symm this)
@@ -266,12 +266,12 @@ private theorem psp_from_prime_psp {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_p
     -- We already proved that `b ^ 2 - 1 ∣ b ^ (p - 1) - 1`.
     -- Since `2 ∣ b ^ p + b` and `p ∣ b ^ p + b`, if we show that 2 and p are coprime, then we
     -- know that `2 * p ∣ b ^ p + b`
-    have q₁ : Nat.Coprime p (b ^ 2 - 1) :=
+    have q₁ : Nat.coprime p (b ^ 2 - 1) :=
       haveI q₂ : ¬p ∣ b ^ 2 - 1 := by
         rw [mul_comm] at not_dvd
         exact mt (fun h : p ∣ b ^ 2 - 1 => dvd_mul_of_dvd_left h _) not_dvd
       (Nat.Prime.coprime_iff_not_dvd p_prime).mpr q₂
-    have q₂ : p * (b ^ 2 - 1) ∣ b ^ (p - 1) - 1 := Nat.Coprime.mul_dvd_of_dvd_of_dvd q₁ ha₃ ha₄
+    have q₂ : p * (b ^ 2 - 1) ∣ b ^ (p - 1) - 1 := Nat.coprime.mul_dvd_of_dvd_of_dvd q₁ ha₃ ha₄
     have q₃ : p * (b ^ 2 - 1) * 2 ∣ (b ^ (p - 1) - 1) * (b ^ p + b) := mul_dvd_mul q₂ ha₂
     have q₄ : p * (b ^ 2 - 1) * 2 ∣ b * ((b ^ (p - 1) - 1) * (b ^ p + b)) :=
       dvd_mul_of_dvd_right q₃ _

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>

@@ -73,7 +73,7 @@ instance decidablePsp (n b : ℕ) : Decidable (FermatPsp n b) :=
 `n` and `b` are both positive.
 -/
 theorem coprime_of_probablePrime {n b : ℕ} (h : ProbablePrime n b) (h₁ : 1 ≤ n) (h₂ : 1 ≤ b) :
-    Nat.coprime n b := by
+    Nat.Coprime n b := by
   by_cases h₃ : 2 ≤ n
   · -- To prove that `n` is coprime with `b`, we need to show that for all prime factors of `n`,
     -- we can derive a contradiction if `n` divides `b`.
@@ -117,7 +117,7 @@ positive.
 
 This lemma is a small wrapper based on `coprime_of_probablePrime`
 -/
-theorem coprime_of_fermatPsp {n b : ℕ} (h : FermatPsp n b) (h₁ : 1 ≤ b) : Nat.coprime n b := by
+theorem coprime_of_fermatPsp {n b : ℕ} (h : FermatPsp n b) (h₁ : 1 ≤ b) : Nat.Coprime n b := by
   rcases h with ⟨hp, _, hn₂⟩
   exact coprime_of_probablePrime hp (by linarith) h₁
 #align fermat_psp.coprime_of_fermat_psp Nat.coprime_of_fermatPsp
@@ -244,7 +244,7 @@ private theorem psp_from_prime_psp {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_p
   -- to prove this.
   have ha₃ : p ∣ b ^ (p - 1) - 1 := by
     have : ¬p ∣ b := mt (fun h : p ∣ b => dvd_mul_of_dvd_left h _) not_dvd
-    have : p.coprime b := Or.resolve_right (Nat.coprime_or_dvd_of_prime p_prime b) this
+    have : p.Coprime b := Or.resolve_right (Nat.coprime_or_dvd_of_prime p_prime b) this
     have : IsCoprime (b : ℤ) ↑p := this.symm.isCoprime
     have : ↑b ^ (p - 1) ≡ 1 [ZMOD ↑p] := Int.ModEq.pow_card_sub_one_eq_one p_prime this
     have : ↑p ∣ ↑b ^ (p - 1) - ↑1 := by exact_mod_cast Int.ModEq.dvd (Int.ModEq.symm this)
@@ -266,12 +266,12 @@ private theorem psp_from_prime_psp {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_p
     -- We already proved that `b ^ 2 - 1 ∣ b ^ (p - 1) - 1`.
     -- Since `2 ∣ b ^ p + b` and `p ∣ b ^ p + b`, if we show that 2 and p are coprime, then we
     -- know that `2 * p ∣ b ^ p + b`
-    have q₁ : Nat.coprime p (b ^ 2 - 1) :=
+    have q₁ : Nat.Coprime p (b ^ 2 - 1) :=
       haveI q₂ : ¬p ∣ b ^ 2 - 1 := by
         rw [mul_comm] at not_dvd
         exact mt (fun h : p ∣ b ^ 2 - 1 => dvd_mul_of_dvd_left h _) not_dvd
       (Nat.Prime.coprime_iff_not_dvd p_prime).mpr q₂
-    have q₂ : p * (b ^ 2 - 1) ∣ b ^ (p - 1) - 1 := Nat.coprime.mul_dvd_of_dvd_of_dvd q₁ ha₃ ha₄
+    have q₂ : p * (b ^ 2 - 1) ∣ b ^ (p - 1) - 1 := Nat.Coprime.mul_dvd_of_dvd_of_dvd q₁ ha₃ ha₄
     have q₃ : p * (b ^ 2 - 1) * 2 ∣ (b ^ (p - 1) - 1) * (b ^ p + b) := mul_dvd_mul q₂ ha₂
     have q₄ : p * (b ^ 2 - 1) * 2 ∣ b * ((b ^ (p - 1) - 1) * (b ^ p + b)) :=
       dvd_mul_of_dvd_right q₃ _

Co-authored-by: Moritz Firsching <firsching@google.com>

@@ -140,8 +140,7 @@ private theorem a_id_helper {a b : ℕ} (ha : 2 ≤ a) (hb : 2 ≤ b) : 2 ≤ (a
   change 1 < _
   have h₁ : a - 1 ∣ a ^ b - 1 := by simpa only [one_pow] using nat_sub_dvd_pow_sub_pow a 1 b
   rw [Nat.lt_div_iff_mul_lt h₁, mul_one, tsub_lt_tsub_iff_right (Nat.le_of_succ_le ha)]
-  convert pow_lt_pow (Nat.lt_of_succ_le ha) hb
-  rw [pow_one]
+  exact self_lt_pow (Nat.lt_of_succ_le ha) hb
 
 private theorem b_id_helper {a b : ℕ} (ha : 2 ≤ a) (hb : 2 < b) : 2 ≤ (a ^ b + 1) / (a + 1) := by
   rw [Nat.le_div_iff_mul_le (Nat.zero_lt_succ _)]

Fix some definition and theorem names in NumberTheory/FermatPsp. Most of these definitions were previously under the FermatPsp namespace. This PR removes the FermatPsp namespace and places all the definitions under the Nat namespace.

The following are the main changes made to names:

• FermatPsp.ProbablePrime -> Nat.ProbablePrime
• FermatPsp -> Nat.FermatPsp
• FermatPsp.coprime_of_probablePrime -> Nat.coprime_of_probablePrime
• FermatPsp.probablePrime_iff_modEq -> Nat.probablePrime_iff_modEq
• FermatPsp.coprime_of_fermatPsp -> Nat.coprime_of_fermatPsp
• FermatPsp.base_one -> Nat.fermatPsp_base_one
• FermatPsp.exists_infinite_pseudoprimes -> Nat.exists_infinite_pseudoprimes
• FermatPsp.frequently_atTop_fermatPsp -> Nat.frequently_atTop_fermatPsp
• FermatPsp.infinite_setOf_prime_modeq_one -> Nat.infinite_setOf_pseudoprimes

The last name was originally a mistake that came from the proof I used as reference.

This PR additionally contains a few fixes for the proofs that were needed because they are now in the Nat namespace. It also removes the Mathlib.Data.Nat.Prime import because it is transitively included in the Mathlib.FieldTheory.Finite.Basic import.

@@ -3,7 +3,6 @@ Copyright (c) 2022 Niels Voss. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Niels Voss
 -/
-import Mathlib.Data.Nat.Prime
 import Mathlib.FieldTheory.Finite.Basic
 import Mathlib.Order.Filter.Cofinite
 
@@ -27,20 +26,21 @@ in this file).
 
 The main definitions for this file are
 
-- `FermatPsp.ProbablePrime`: A number `n` is a probable prime to base `b` if it passes the Fermat
+- `Nat.ProbablePrime`: A number `n` is a probable prime to base `b` if it passes the Fermat
   primality test; that is, if `n` divides `b ^ (n - 1) - 1`
-- `FermatPsp`: A number `n` is a pseudoprime to base `b` if it is a probable prime to base `b`, is
-  composite, and is coprime with `b` (this last condition is automatically true if `n` divides
+- `Nat.FermatPsp`: A number `n` is a pseudoprime to base `b` if it is a probable prime to base `b`,
+  is composite, and is coprime with `b` (this last condition is automatically true if `n` divides
   `b ^ (n - 1) - 1`, but some sources include it in the definition).
 
 Note that all composite numbers are pseudoprimes to base 0 and 1, and that the definition of
-`ProbablePrime` in this file implies that all numbers are probable primes to bases 0 and 1, and
+`Nat.ProbablePrime` in this file implies that all numbers are probable primes to bases 0 and 1, and
 that 0 and 1 are probable primes to any base.
 
 The main theorems are
-- `FermatPsp.exists_infinite_pseudoprimes`: there are infinite pseudoprimes to any base `b ≥ 1`
+- `Nat.exists_infinite_pseudoprimes`: there are infinite pseudoprimes to any base `b ≥ 1`
 -/
 
+namespace Nat
 
 /--
 `n` is a probable prime to base `b` if `n` passes the Fermat primality test; that is, `n` divides
@@ -48,9 +48,9 @@ The main theorems are
 This definition implies that all numbers are probable primes to base 0 or 1, and that 0 and 1 are
 probable primes to any base.
 -/
-def FermatPsp.ProbablePrime (n b : ℕ) : Prop :=
+def ProbablePrime (n b : ℕ) : Prop :=
   n ∣ b ^ (n - 1) - 1
-#align fermat_psp.probable_prime FermatPsp.ProbablePrime
+#align fermat_psp.probable_prime Nat.ProbablePrime
 
 /--
 `n` is a Fermat pseudoprime to base `b` if `n` is a probable prime to base `b` and is composite. By
@@ -58,18 +58,16 @@ this definition, all composite natural numbers are pseudoprimes to base 0 and 1.
 also permits `n` to be less than `b`, so that 4 is a pseudoprime to base 5, for example.
 -/
 def FermatPsp (n b : ℕ) : Prop :=
-  FermatPsp.ProbablePrime n b ∧ ¬n.Prime ∧ 1 < n
-#align fermat_psp FermatPsp
-
-namespace FermatPsp
+  ProbablePrime n b ∧ ¬n.Prime ∧ 1 < n
+#align fermat_psp Nat.FermatPsp
 
 instance decidableProbablePrime (n b : ℕ) : Decidable (ProbablePrime n b) :=
   Nat.decidable_dvd _ _
-#align fermat_psp.decidable_probable_prime FermatPsp.decidableProbablePrime
+#align fermat_psp.decidable_probable_prime Nat.decidableProbablePrime
 
 instance decidablePsp (n b : ℕ) : Decidable (FermatPsp n b) :=
   And.decidable
-#align fermat_psp.decidable_psp FermatPsp.decidablePsp
+#align fermat_psp.decidable_psp Nat.decidablePsp
 
 /-- If `n` passes the Fermat primality test to base `b`, then `n` is coprime with `b`, assuming that
 `n` and `b` are both positive.
@@ -99,7 +97,7 @@ theorem coprime_of_probablePrime {n b : ℕ} (h : ProbablePrime n b) (h₁ : 1 
   -- If `n = 1`, then it follows trivially that `n` is coprime with `b`.
   · rw [show n = 1 by linarith]
     norm_num
-#align fermat_psp.coprime_of_probable_prime FermatPsp.coprime_of_probablePrime
+#align fermat_psp.coprime_of_probable_prime Nat.coprime_of_probablePrime
 
 theorem probablePrime_iff_modEq (n : ℕ) {b : ℕ} (h : 1 ≤ b) :
     ProbablePrime n b ↔ b ^ (n - 1) ≡ 1 [MOD n] := by
@@ -112,7 +110,7 @@ theorem probablePrime_iff_modEq (n : ℕ) {b : ℕ} (h : 1 ≤ b) :
     exact_mod_cast h₁
   · intro h₁
     exact_mod_cast Nat.ModEq.dvd h₁
-#align fermat_psp.probable_prime_iff_modeq FermatPsp.probablePrime_iff_modEq
+#align fermat_psp.probable_prime_iff_modeq Nat.probablePrime_iff_modEq
 
 /-- If `n` is a Fermat pseudoprime to base `b`, then `n` is coprime with `b`, assuming that `b` is
 positive.
@@ -122,14 +120,14 @@ This lemma is a small wrapper based on `coprime_of_probablePrime`
 theorem coprime_of_fermatPsp {n b : ℕ} (h : FermatPsp n b) (h₁ : 1 ≤ b) : Nat.coprime n b := by
   rcases h with ⟨hp, _, hn₂⟩
   exact coprime_of_probablePrime hp (by linarith) h₁
-#align fermat_psp.coprime_of_fermat_psp FermatPsp.coprime_of_fermatPsp
+#align fermat_psp.coprime_of_fermat_psp Nat.coprime_of_fermatPsp
 
 /-- All composite numbers are Fermat pseudoprimes to base 1.
 -/
-theorem base_one {n : ℕ} (h₁ : 1 < n) (h₂ : ¬n.Prime) : FermatPsp n 1 := by
+theorem fermatPsp_base_one {n : ℕ} (h₁ : 1 < n) (h₂ : ¬n.Prime) : FermatPsp n 1 := by
   refine' ⟨show n ∣ 1 ^ (n - 1) - 1 from _, h₂, h₁⟩
   exact show 0 = 1 ^ (n - 1) - 1 by norm_num ▸ dvd_zero n
-#align fermat_psp.base_one FermatPsp.base_one
+#align fermat_psp.base_one Nat.fermatPsp_base_one
 
 -- Lemmas that are needed to prove statements in this file, but aren't directly related to Fermat
 -- pseudoprimes
@@ -150,7 +148,7 @@ private theorem b_id_helper {a b : ℕ} (ha : 2 ≤ a) (hb : 2 < b) : 2 ≤ (a ^
   apply Nat.succ_le_succ
   calc
     2 * a + 1 ≤ a ^ 2 * a := by nlinarith
-    _ = a ^ 3 := by rw [pow_succ' a 2]
+    _ = a ^ 3 := by rw [pow_succ a 2]
     _ ≤ a ^ b := pow_le_pow (Nat.le_of_succ_le ha) hb
 
 private theorem AB_id_helper (b p : ℕ) (_ : 2 ≤ b) (hp : Odd p) :
@@ -175,7 +173,7 @@ private theorem bp_helper {b p : ℕ} (hb : 0 < b) (hp : 1 ≤ p) :
     _ = (b ^ p + b) * (b ^ p - b) := by rw [Nat.sq_sub_sq]
     _ = (b ^ p - b) * (b ^ p + b) := by rw [mul_comm]
     _ = (b ^ (p - 1 + 1) - b) * (b ^ p + b) := by rw [Nat.sub_add_cancel hp]
-    _ = (b * b ^ (p - 1) - b) * (b ^ p + b) := by rw [pow_succ]
+    _ = (b * b ^ (p - 1) - b) * (b ^ p + b) := by rw [pow_succ']
     _ = (b * b ^ (p - 1) - b * 1) * (b ^ p + b) := by rw [mul_one]
     _ = b * (b ^ (p - 1) - 1) * (b ^ p + b) := by rw [Nat.mul_sub_left_distrib]
 
@@ -321,14 +319,13 @@ private theorem psp_from_prime_gt_p {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_
   rw [Nat.mul_sub_left_distrib, mul_one, pow_mul]
   conv_rhs => rw [← Nat.sub_add_cancel (show 1 ≤ p by linarith)]
   rw [pow_succ (b ^ 2)]
-  suffices h : p * b ^ 2 < b ^ 2 * (b ^ 2) ^ (p - 1)
+  suffices h : p * b ^ 2 < (b ^ 2) ^ (p - 1) * b ^ 2
   · apply gt_of_ge_of_gt
-    · exact tsub_le_tsub_left (show 1 ≤ p by linarith) (b ^ 2 * (b ^ 2) ^ (p - 1))
+    · exact tsub_le_tsub_left (one_le_of_lt p_gt_two) ((b ^ 2) ^ (p - 1) * b ^ 2)
     · have : p ≤ p * b ^ 2 := Nat.le_mul_of_pos_right (show 0 < b ^ 2 by nlinarith)
       exact tsub_lt_tsub_right_of_le this h
   suffices h : p < (b ^ 2) ^ (p - 1)
-  · rw [mul_comm (b ^ 2)]
-    have : 4 ≤ b ^ 2 := by nlinarith
+  · have : 4 ≤ b ^ 2 := by nlinarith
     have : 0 < b ^ 2 := by linarith
     exact mul_lt_mul_of_pos_right h this
   rw [← pow_mul, Nat.mul_sub_left_distrib, mul_one]
@@ -374,21 +371,21 @@ theorem exists_infinite_pseudoprimes {b : ℕ} (h : 1 ≤ b) (m : ℕ) :
     rw [h₁]
     use 2 * (m + 2)
     have : ¬Nat.Prime (2 * (m + 2)) := Nat.not_prime_mul (by norm_num) (by norm_num)
-    exact ⟨base_one (by linarith) this, by linarith⟩
-#align fermat_psp.exists_infinite_pseudoprimes FermatPsp.exists_infinite_pseudoprimes
+    exact ⟨fermatPsp_base_one (by linarith) this, by linarith⟩
+#align fermat_psp.exists_infinite_pseudoprimes Nat.exists_infinite_pseudoprimes
 
 theorem frequently_atTop_fermatPsp {b : ℕ} (h : 1 ≤ b) : ∃ᶠ n in Filter.atTop, FermatPsp n b := by
   -- Based on the proof of `Nat.frequently_atTop_modEq_one`
   refine' Filter.frequently_atTop.2 fun n => _
   obtain ⟨p, hp⟩ := exists_infinite_pseudoprimes h n
   exact ⟨p, hp.2, hp.1⟩
-#align fermat_psp.frequently_at_top_fermat_psp FermatPsp.frequently_atTop_fermatPsp
+#align fermat_psp.frequently_at_top_fermat_psp Nat.frequently_atTop_fermatPsp
 
-/-- Infinite set variant of `exists_infinite_pseudoprimes`
+/-- Infinite set variant of `Nat.exists_infinite_pseudoprimes`
 -/
-theorem infinite_setOf_prime_modeq_one {b : ℕ} (h : 1 ≤ b) :
+theorem infinite_setOf_pseudoprimes {b : ℕ} (h : 1 ≤ b) :
     Set.Infinite { n : ℕ | FermatPsp n b } :=
   Nat.frequently_atTop_iff_infinite.mp (frequently_atTop_fermatPsp h)
-#align fermat_psp.infinite_set_of_prime_modeq_one FermatPsp.infinite_setOf_prime_modeq_one
+#align fermat_psp.infinite_set_of_prime_modeq_one Nat.infinite_setOf_pseudoprimes
 
-end FermatPsp
+end Nat

• depends on: #5966

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

@@ -2,16 +2,13 @@
 Copyright (c) 2022 Niels Voss. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Niels Voss
-
-! This file was ported from Lean 3 source module number_theory.fermat_psp
-! leanprover-community/mathlib commit c0439b4877c24a117bfdd9e32faf62eee9b115eb
-! 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.FieldTheory.Finite.Basic
 import Mathlib.Order.Filter.Cofinite
 
+#align_import number_theory.fermat_psp from "leanprover-community/mathlib"@"c0439b4877c24a117bfdd9e32faf62eee9b115eb"
+
 /-!
 # Fermat Pseudoprimes
 

Changes are of the form

• some_tactic at h⊢ -> some_tactic at h ⊢
• some_tactic at h -> some_tactic at h

@@ -234,9 +234,9 @@ private theorem psp_from_prime_psp {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_p
   refine' ⟨_, AB_not_prime, hi_AB⟩
   -- Used to prove that `2 * p * (b ^ 2 - 1) ∣ (b ^ 2 - 1) * (A * B - 1)`.
   have ha₁ : (b ^ 2 - 1) * (A * B - 1) = b * (b ^ (p - 1) - 1) * (b ^ p + b) := by
-    apply_fun fun x => x * (b ^ 2 - 1)  at AB_id
+    apply_fun fun x => x * (b ^ 2 - 1) at AB_id
     rw [Nat.div_mul_cancel hd] at AB_id
-    apply_fun fun x => x - (b ^ 2 - 1)  at AB_id
+    apply_fun fun x => x - (b ^ 2 - 1) at AB_id
     nth_rw 2 [← one_mul (b ^ 2 - 1)] at AB_id
     rw [← Nat.mul_sub_right_distrib, mul_comm] at AB_id
     rw [AB_id]

@@ -244,15 +244,8 @@ private theorem psp_from_prime_psp {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_p
   -- If `b` is even, then `b^p` is also even, so `2 ∣ b^p + b`
   -- If `b` is odd, then `b^p` is also odd, so `2 ∣ b^p + b`
   have ha₂ : 2 ∣ b ^ p + b := by
-    by_cases h : Even b
-    · replace h : 2 ∣ b := even_iff_two_dvd.mp h
-      have : p ≠ 0 := by linarith
-      have : 2 ∣ b ^ p := dvd_pow h this
-      exact dvd_add this h
-    · have h : Odd b := Nat.odd_iff_not_even.mpr h
-      have : Odd (b ^ p) := Odd.pow h
-      have : Even (b ^ p + b) := Odd.add_odd this h
-      exact even_iff_two_dvd.mp this
+    -- Porting note: golfed
+    rw [← even_iff_two_dvd, Nat.even_add, Nat.even_pow' p_prime.ne_zero]
   -- Since `b` isn't divisible by `p`, `b` is coprime with `p`. we can use Fermat's Little Theorem
   -- to prove this.
   have ha₃ : p ∣ b ^ (p - 1) - 1 := by

These are all doc fixes

@@ -36,7 +36,7 @@ The main definitions for this file are
   composite, and is coprime with `b` (this last condition is automatically true if `n` divides
   `b ^ (n - 1) - 1`, but some sources include it in the definition).
 
-Note that all composite numbers are pseudoprimes to base 0 and 1, and that the definiton of
+Note that all composite numbers are pseudoprimes to base 0 and 1, and that the definition of
 `ProbablePrime` in this file implies that all numbers are probable primes to bases 0 and 1, and
 that 0 and 1 are probable primes to any base.