-- Mathlib/NumberTheory/FermatPsp.lean
theorem psp_from_prime_gt_p {b : ℕ} (b_ge_two : 2 ≤ b) {p : ℕ} (p_prime : p.Prime)
    (p_gt_two : 2 < p) : p < psp_from_prime b p

Proof state:
b : ℕ
b_ge_two : 2 ≤ b
p : ℕ
p_prime : Prime p
p_gt_two : 2 < p
A : ℕ := (b ^ p - 1) / (b - 1)
B : ℕ := (b ^ p + 1) / (b + 1)
AB_dvd : b ^ 2 - 1 ∣ b ^ (2 * p) - 1
⊢ p * b ^ 2 < (b ^ 2) ^ (p - 1) * b ^ 2

Tactic:
suffices h : p < (b ^ 2) ^ (p - 1) by gcongr

Result:
b : ℕ
b_ge_two : 2 ≤ b
p : ℕ
p_prime : Prime p
p_gt_two : 2 < p
A : ℕ := (b ^ p - 1) / (b - 1)
B : ℕ := (b ^ p + 1) / (b + 1)
AB_dvd : b ^ 2 - 1 ∣ b ^ (2 * p) - 1
⊢ p < (b ^ 2) ^ (p - 1)

Proof state:
case h₁
b : ℕ
b_ge_two : 2 ≤ b
p : ℕ
p_prime : Prime p
p_gt_two : 2 < p
A : ℕ := (b ^ p - 1) / (b - 1)
B : ℕ := (b ^ p + 1) / (b + 1)
AB_dvd : b ^ 2 - 1 ∣ b ^ (2 * p) - 1
h : p * b ^ 2 < (b ^ 2) ^ (p - 1) * b ^ 2
⊢ (b ^ 2) ^ (p - 1) * b ^ 2 - 1 ≥ ?b

Tactic:
exact tsub_le_tsub_left (one_le_of_lt p_gt_two) ((b ^ 2) ^ (p - 1) * b ^ 2)

Result:
no goals

Proof state:
b : ℕ
b_ge_two : 2 ≤ b
p : ℕ
p_prime : Prime p
p_gt_two : 2 < p
A : ℕ := (b ^ p - 1) / (b - 1)
B : ℕ := (b ^ p + 1) / (b + 1)
AB_dvd : b ^ 2 - 1 ∣ b ^ (2 * p) - 1
⊢ 4 ≤ 2 * p

Tactic:
omega

Result:
no goals

Proof state:
b : ℕ
b_ge_two : 2 ≤ b
p : ℕ
p_prime : Prime p
p_gt_two : 2 < p
A : ℕ := (b ^ p - 1) / (b - 1)
B : ℕ := (b ^ p + 1) / (b + 1)
AB_dvd : b ^ 2 - 1 ∣ b ^ (2 * p) - 1
h : p * (b ^ 2 - 1) < b ^ (2 * p) - 1
h₁ : p * (b ^ 2 - 1) / (b ^ 2 - 1) < (b ^ (2 * p) - 1) / (b ^ 2 - 1)
⊢ 4 ≤ b ^ 2

Tactic:
nlinarith

Result:
no goals

Proof state:
b : ℕ
b_ge_two : 2 ≤ b
p : ℕ
p_prime : Prime p
p_gt_two : 2 < p
A : ℕ := (b ^ p - 1) / (b - 1)
B : ℕ := (b ^ p + 1) / (b + 1)
AB_dvd : b ^ 2 - 1 ∣ b ^ (2 * p) - 1
h : p * (b ^ 2 - 1) < b ^ (2 * p) - 1
h₁ : p * (b ^ 2 - 1) / (b ^ 2 - 1) < (b ^ (2 * p) - 1) / (b ^ 2 - 1)
h₂ : 0 < b ^ 2 - 1
⊢ p < (b ^ (2 * p) - 1) / (b ^ 2 - 1)

Tactic:
rwa [Nat.mul_div_cancel _ h₂] at h₁

Result:
no goals

Proof state:
b : ℕ
b_ge_two : 2 ≤ b
p : ℕ
p_prime : Prime p
p_gt_two : 2 < p
⊢ p < (b ^ p - 1) / (b - 1) * ((b ^ p + 1) / (b + 1))

Tactic:
set A := (b ^ p - 1) / (b - 1)

Result:
b : ℕ
b_ge_two : 2 ≤ b
p : ℕ
p_prime : Prime p
p_gt_two : 2 < p
A : ℕ := (b ^ p - 1) / (b - 1)
⊢ p < A * ((b ^ p + 1) / (b + 1))

Proof state:
b : ℕ
b_ge_two : 2 ≤ b
p : ℕ
p_prime : Prime p
p_gt_two : 2 < p
A : ℕ := (b ^ p - 1) / (b - 1)
B : ℕ := (b ^ p + 1) / (b + 1)
AB_dvd : b ^ 2 - 1 ∣ b ^ (2 * p) - 1
⊢ p < b ^ (2 * p - 2)

Tactic:
have : 2 ≤ 2 * p - 2 := le_tsub_of_add_le_left (show 4 ≤ 2 * p by omega)

Result:
b : ℕ
b_ge_two : 2 ≤ b
p : ℕ
p_prime : Prime p
p_gt_two : 2 < p
A : ℕ := (b ^ p - 1) / (b - 1)
B : ℕ := (b ^ p + 1) / (b + 1)
AB_dvd : b ^ 2 - 1 ∣ b ^ (2 * p) - 1
this : 2 ≤ 2 * p - 2
⊢ p < b ^ (2 * p - 2)

Proof state:
b : ℕ
b_ge_two : 2 ≤ b
p : ℕ
p_prime : Prime p
p_gt_two : 2 < p
A : ℕ := (b ^ p - 1) / (b - 1)
B : ℕ := (b ^ p + 1) / (b + 1)
AB_dvd : b ^ 2 - 1 ∣ b ^ (2 * p) - 1
h : p * (b ^ 2 - 1) < b ^ (2 * p) - 1
h₁ : p * (b ^ 2 - 1) / (b ^ 2 - 1) < (b ^ (2 * p) - 1) / (b ^ 2 - 1)
⊢ p < (b ^ (2 * p) - 1) / (b ^ 2 - 1)

Tactic:
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)]

Result:
b : ℕ
b_ge_two : 2 ≤ b
p : ℕ
p_prime : Prime p
p_gt_two : 2 < p
A : ℕ := (b ^ p - 1) / (b - 1)
B : ℕ := (b ^ p + 1) / (b + 1)
AB_dvd : b ^ 2 - 1 ∣ b ^ (2 * p) - 1
h : p * (b ^ 2 - 1) < b ^ (2 * p) - 1
h₁ : p * (b ^ 2 - 1) / (b ^ 2 - 1) < (b ^ (2 * p) - 1) / (b ^ 2 - 1)
h₂ : 0 < b ^ 2 - 1
⊢ p < (b ^ (2 * p) - 1) / (b ^ 2 - 1)

Proof state:
b : ℕ
b_ge_two : 2 ≤ b
p : ℕ
p_prime : Prime p
p_gt_two : 2 < p
A : ℕ := (b ^ p - 1) / (b - 1)
B : ℕ := (b ^ p + 1) / (b + 1)
AB_dvd : b ^ 2 - 1 ∣ b ^ (2 * p) - 1
⊢ p < (b ^ 2) ^ (p - 1)

Tactic:
rw [← pow_mul, Nat.mul_sub_left_distrib, mul_one]

Result:
b : ℕ
b_ge_two : 2 ≤ b
p : ℕ
p_prime : Prime p
p_gt_two : 2 < p
A : ℕ := (b ^ p - 1) / (b - 1)
B : ℕ := (b ^ p + 1) / (b + 1)
AB_dvd : b ^ 2 - 1 ∣ b ^ (2 * p) - 1
⊢ p < b ^ (2 * p - 2)

Proof state:
b : ℕ
b_ge_two : 2 ≤ b
p : ℕ
p_prime : Prime p
p_gt_two : 2 < p
A : ℕ := (b ^ p - 1) / (b - 1)
B : ℕ := (b ^ p + 1) / (b + 1)
AB_dvd : b ^ 2 - 1 ∣ b ^ (2 * p) - 1
⊢ p * b ^ 2 - p < (b ^ 2) ^ p - 1

Tactic:
conv_rhs => rw [← Nat.sub_add_cancel (show 1 ≤ p by omega)]

Result:
b : ℕ
b_ge_two : 2 ≤ b
p : ℕ
p_prime : Prime p
p_gt_two : 2 < p
A : ℕ := (b ^ p - 1) / (b - 1)
B : ℕ := (b ^ p + 1) / (b + 1)
AB_dvd : b ^ 2 - 1 ∣ b ^ (2 * p) - 1
⊢ p * b ^ 2 - p < (b ^ 2) ^ (p - 1 + 1) - 1

Proof state:
b : ℕ
b_ge_two : 2 ≤ b
p : ℕ
p_prime : Prime p
p_gt_two : 2 < p
A : ℕ := (b ^ p - 1) / (b - 1)
B : ℕ := (b ^ p + 1) / (b + 1)
AB_dvd : b ^ 2 - 1 ∣ b ^ (2 * p) - 1
h : p < (b ^ 2) ^ (p - 1)
⊢ p * b ^ 2 < (b ^ 2) ^ (p - 1) * b ^ 2

Tactic:
gcongr

Result:
no goals

Proof state:
b : ℕ
b_ge_two : 2 ≤ b
p : ℕ
p_prime : Prime p
p_gt_two : 2 < p
A : ℕ := (b ^ p - 1) / (b - 1)
B : ℕ := (b ^ p + 1) / (b + 1)
AB_dvd : b ^ 2 - 1 ∣ b ^ (2 * p) - 1
h : p * b ^ 2 < (b ^ 2) ^ (p - 1) * b ^ 2
⊢ p * b ^ 2 - p < (b ^ 2) ^ (p - 1) * b ^ 2 - 1

Tactic:
apply gt_of_ge_of_gt

Result:
case h₁
b : ℕ
b_ge_two : 2 ≤ b
p : ℕ
p_prime : Prime p
p_gt_two : 2 < p
A : ℕ := (b ^ p - 1) / (b - 1)
B : ℕ := (b ^ p + 1) / (b + 1)
AB_dvd : b ^ 2 - 1 ∣ b ^ (2 * p) - 1
h : p * b ^ 2 < (b ^ 2) ^ (p - 1) * b ^ 2
⊢ (b ^ 2) ^ (p - 1) * b ^ 2 - 1 ≥ ?b

case h₂
b : ℕ
b_ge_two : 2 ≤ b
p : ℕ
p_prime : Prime p
p_gt_two : 2 < p
A : ℕ := (b ^ p - 1) / (b - 1)
B : ℕ := (b ^ p + 1) / (b + 1)
AB_dvd : b ^ 2 - 1 ∣ b ^ (2 * p) - 1
h : p * b ^ 2 < (b ^ 2) ^ (p - 1) * b ^ 2
⊢ ?b > p * b ^ 2 - p

case b
b : ℕ
b_ge_two : 2 ≤ b
p : ℕ
p_prime : Prime p
p_gt_two : 2 < p
A : ℕ := (b ^ p - 1) / (b - 1)
B : ℕ := (b ^ p + 1) / (b + 1)
AB_dvd : b ^ 2 - 1 ∣ b ^ (2 * p) - 1
h : p * b ^ 2 < (b ^ 2) ^ (p - 1) * b ^ 2
⊢ ℕ

Proof state:
b : ℕ
b_ge_two : 2 ≤ b
p : ℕ
p_prime : Prime p
p_gt_two : 2 < p
A : ℕ := (b ^ p - 1) / (b - 1)
B : ℕ := (b ^ p + 1) / (b + 1)
AB_dvd : b ^ 2 - 1 ∣ b ^ (2 * p) - 1
⊢ 1 ≤ p

Tactic:
omega

Result:
no goals

Proof state:
b : ℕ
b_ge_two : 2 ≤ b
p : ℕ
p_prime : Prime p
p_gt_two : 2 < p
A : ℕ := (b ^ p - 1) / (b - 1)
B : ℕ := (b ^ p + 1) / (b + 1)
AB_dvd : b ^ 2 - 1 ∣ b ^ (2 * p) - 1
h : p * (b ^ 2 - 1) < b ^ (2 * p) - 1
⊢ p < (b ^ (2 * p) - 1) / (b ^ 2 - 1)

Tactic:
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

Result:
b : ℕ
b_ge_two : 2 ≤ b
p : ℕ
p_prime : Prime p
p_gt_two : 2 < p
A : ℕ := (b ^ p - 1) / (b - 1)
B : ℕ := (b ^ p + 1) / (b + 1)
AB_dvd : b ^ 2 - 1 ∣ b ^ (2 * p) - 1
h : p * (b ^ 2 - 1) < b ^ (2 * p) - 1
h₁ : p * (b ^ 2 - 1) / (b ^ 2 - 1) < (b ^ (2 * p) - 1) / (b ^ 2 - 1)
⊢ p < (b ^ (2 * p) - 1) / (b ^ 2 - 1)

Proof state:
b : ℕ
b_ge_two : 2 ≤ b
p : ℕ
p_prime : Prime p
p_gt_two : 2 < p
A : ℕ := (b ^ p - 1) / (b - 1)
B : ℕ := (b ^ p + 1) / (b + 1)
AB_dvd : b ^ 2 - 1 ∣ b ^ (2 * p) - 1
h : p * b ^ 2 < (b ^ 2) ^ (p - 1) * b ^ 2
⊢ 0 < b ^ 2

Tactic:
positivity

Result:
no goals

Proof state:
b : ℕ
b_ge_two : 2 ≤ b
p : ℕ
p_prime : Prime p
p_gt_two : 2 < p
A : ℕ := (b ^ p - 1) / (b - 1)
B : ℕ := (b ^ p + 1) / (b + 1)
AB_dvd : b ^ 2 - 1 ∣ b ^ (2 * p) - 1
this✝ : 2 ≤ 2 * p - 2
this : 2 + p ≤ 2 * p
⊢ p < b ^ (2 * p - 2)

Tactic:
have : p ≤ 2 * p - 2 := le_tsub_of_add_le_left this

Result:
b : ℕ
b_ge_two : 2 ≤ b
p : ℕ
p_prime : Prime p
p_gt_two : 2 < p
A : ℕ := (b ^ p - 1) / (b - 1)
B : ℕ := (b ^ p + 1) / (b + 1)
AB_dvd : b ^ 2 - 1 ∣ b ^ (2 * p) - 1
this✝¹ : 2 ≤ 2 * p - 2
this✝ : 2 + p ≤ 2 * p
this : p ≤ 2 * p - 2
⊢ p < b ^ (2 * p - 2)

Proof state:
case h₂
b : ℕ
b_ge_two : 2 ≤ b
p : ℕ
p_prime : Prime p
p_gt_two : 2 < p
A : ℕ := (b ^ p - 1) / (b - 1)
B : ℕ := (b ^ p + 1) / (b + 1)
AB_dvd : b ^ 2 - 1 ∣ b ^ (2 * p) - 1
h : p * b ^ 2 < (b ^ 2) ^ (p - 1) * b ^ 2
this : p ≤ p * b ^ 2
⊢ (b ^ 2) ^ (p - 1) * b ^ 2 - p > p * b ^ 2 - p

Tactic:
exact tsub_lt_tsub_right_of_le this h

Result:
no goals