import Mathlib noncomputable def Nat.maxPrimeFac (n : ℕ) : ℕ := sSup {p : ℕ | p.Prime ∧ p ∣ n} lemma mpf_aux {m q : ℕ} (hq : q ≠ 0) (h : m.maxPrimeFac = q) : q ∈ {p : ℕ | p.Prime ∧ p ∣ m} ∧ BddAbove {p : ℕ | p.Prime ∧ p ∣ m} := by unfold Nat.maxPrimeFac at h set S := {p : ℕ | p.Prime ∧ p ∣ m} have hne : S.Nonempty := by by_contra hc rw [Set.not_nonempty_iff_eq_empty] at hc rw [hc, csSup_empty] at h exact hq h.symm have hb : BddAbove S := by by_contra hc rw [Nat.sSup_of_not_bddAbove hc] at h exact hq h.symm refine ⟨?_, hb⟩ rw [← h] exact Nat.sSup_mem hne hb lemma pow2mod7 (k : ℕ) : 2^k % 7 = 1 ∨ 2^k % 7 = 2 ∨ 2^k % 7 = 4 := by induction k with | zero => simp | succ k ih => rw [pow_succ, Nat.mul_mod] rcases ih with h | h | h <;> rw [h] <;> norm_num open Nat in theorem erdos_task : ¬ ∀ p q : ℕ, p.Prime → q.Prime → p ≠ q → ∃ n : ℕ, n.maxPrimeFac = p ∧ (n + 1).maxPrimeFac = q := by intro h obtain ⟨n, h1, h2⟩ := h 2 7 Nat.prime_two (by norm_num) (by norm_num) obtain ⟨⟨_, h7⟩, _⟩ := mpf_aux (by norm_num) h2 obtain ⟨⟨_, h2d⟩, hb⟩ := mpf_aux (by norm_num) h1 have hn : n ≠ 0 := by rintro rfl apply Nat.not_bddAbove_setOfPred_prime refine hb.mono ?_ intro p hp exact ⟨hp, dvd_zero p⟩ have hpow : n = 2 ^ n.primeFactorsList.length := by apply Nat.eq_prime_pow_of_unique_prime_dvd hn intro d hd hdn have : d ≤ 2 := by rw [← h1] exact le_csSup hb ⟨hd, hdn⟩ have := hd.two_le omega rw [hpow] at h7 have := pow2mod7 n.primeFactorsList.length omega