import Mathlib def Gt (b : ℕ) : ℕ → ℕ → Prop | 0, x => x = 0 | j+1, x => ∃ d, d ≤ (b-1)/2 ∧ ∃ y, Gt b j y ∧ x = d * b^j + y def Gb (b : ℕ) : ℕ → ℕ → Prop | 0, x => x = 0 | j+1, x => ∃ d, d ≤ (b-1)/2 ∧ ∃ y, Gb b j y ∧ x = d + b * y lemma Gb_top (b d : ℕ) (hd : d ≤ (b-1)/2) : ∀ j y, Gb b j y → Gb b (j+1) (d * b^j + y) := by intro j induction j with | zero => intro y hy; simp only [Gb] at hy; subst hy; exact ⟨d, hd, 0, rfl, by simp⟩ | succ j ih => intro y hy obtain ⟨d0, hd0, y', hy', rfl⟩ := hy exact ⟨d0, hd0, d * b^j + y', ih y' hy', by ring⟩ lemma Gt_Gb (b : ℕ) : ∀ j x, Gt b j x → Gb b j x := by intro j induction j with | zero => intro x hx; exact hx | succ j ih => intro x hx obtain ⟨d, hd, y, hy, rfl⟩ := hx exact Gb_top b d hd j y (ih y hy) lemma Gb_cop (p : ℕ) (hp : p.Prime) (ho : Odd p) : ∀ j x, Gb p j x → p.Coprime (Nat.centralBinom x) := by have := Fact.mk hp intro j induction j with | zero => intro x hx; simp only [Gb] at hx; subst hx; simp | succ j ih => intro x hx obtain ⟨d, hd, y, hy, rfl⟩ := hx have hp0 : 0 < p := hp.pos obtain ⟨r, hr⟩ := ho have h2d : 2 * d < p := by omega have hd' : d < p := by omega have e1 : 2 * (d + p * y) = 2 * d + p * (2 * y) := by ring have hl := @Choose.choose_modEq_choose_mod_mul_choose_div_nat (2 * (d + p*y)) (d + p*y) p _ rw [e1, Nat.add_mul_mod_self_left, Nat.add_mul_mod_self_left, Nat.mod_eq_of_lt h2d, Nat.mod_eq_of_lt hd', Nat.add_mul_div_left _ _ hp0, Nat.add_mul_div_left _ _ hp0, Nat.div_eq_of_lt h2d, Nat.div_eq_of_lt hd'] at hl simp only [zero_add] at hl rw [Nat.centralBinom_eq_two_mul_choose, hp.coprime_iff_not_dvd] intro hdv have h1 := ih y hy rw [Nat.centralBinom_eq_two_mul_choose, hp.coprime_iff_not_dvd] at h1 have h0 := hp.coprime_choose_of_lt h2d (by omega : d ≤ 2*d) rw [hp.coprime_iff_not_dvd] at h0 have : p ∣ (2*d).choose d * (2*y).choose y := by rw [Nat.dvd_iff_mod_eq_zero] at hdv ⊢ unfold Nat.ModEq at hl rw [e1] at hdv omega rcases hp.dvd_mul.1 this with h | h · exact h0 h · exact h1 h lemma mfact (b j : ℕ) (hb : Odd b) : b^j = 2*((b^j-1)/2)+1 := by have := (hb.pow (n := j)) rw [Nat.odd_iff] at this omega lemma mstep (b j : ℕ) (hb : Odd b) : (b^(j+1)-1)/2 = (b-1)/2 * b^j + (b^j-1)/2 := by obtain ⟨h, rfl⟩ := hb have hB := mfact (2*h+1) j ⟨h, rfl⟩ have e : (2*h+1-1)/2 = h := by omega rw [e, pow_succ] generalize (2*h+1)^j = B at hB ⊢ generalize (B-1)/2 = M at hB ⊢ subst hB have : (2*M+1)*(2*h+1) = 2*(h*(2*M+1)+M) + 1 := by ring rw [this] omega lemma mmono (b j : ℕ) (hb : 1 ≤ b) : (b^(j-1)-1)/2 ≤ (b^j-1)/2 := by apply Nat.div_le_div_right have := Nat.pow_le_pow_right hb (Nat.sub_le j 1) omega lemma pick (h g m' t : ℕ) (hg : g = 2*m'+1) (ht : t ≤ h*g+m') : ∃ d ≤ h, d*g ≤ t + m' ∧ t ≤ d*g+m' := by induction h with | zero => exact ⟨0, le_rfl, by simp, by simpa using ht⟩ | succ h ih => by_cases hc : t ≤ h*g+m' · obtain ⟨d, hd, h1, h2⟩ := ih hc exact ⟨d, by omega, h1, h2⟩ · refine ⟨h+1, le_rfl, ?_, ?_⟩ · rw [add_mul, one_mul]; omega · rw [add_mul, one_mul] at ht ⊢; omega lemma gap (p q : ℕ) (hp : Odd p) (hq : Odd q) (hp3 : 3 ≤ p) (hq3 : 3 ≤ q) : ∀ s j k c e, j + k = s → (p^(j-1)-1)/2 ≤ (q^k-1)/2 → (q^(k-1)-1)/2 ≤ (p^j-1)/2 → c ≤ e + (q^k-1)/2 → e ≤ c + (p^j-1)/2 → ∃ x y, Gt p j x ∧ Gt q k y ∧ c + x = e + y := by intro s induction s with | zero => intro j k c e hs _ _ h1 h2 have hj : j = 0 := by omega have hk : k = 0 := by omega subst hj hk simp at h1 h2 exact ⟨0, 0, rfl, rfl, by omega⟩ | succ s ih => intro j k c e hs P1 P2 h1 h2 by_cases hA : 1 ≤ j ∧ (k = 0 ∨ (q^(k-1)-1)/2 ≤ (p^(j-1)-1)/2) · obtain ⟨j', rfl⟩ : ∃ j', j = j' + 1 := ⟨j-1, by omega⟩ simp only [Nat.add_sub_cancel] at P1 hA have hg := mfact p j' hp have hs' := mstep p j' hp obtain ⟨d, hd, hc1, hc2⟩ : ∃ d ≤ (p-1)/2, c + d*p^j' ≤ e + (q^k-1)/2 ∧ e ≤ c + d*p^j' + (p^j'-1)/2 := by by_cases hec : e ≤ c · exact ⟨0, Nat.zero_le _, by simpa using h1, by omega⟩ · obtain ⟨d, hd, a1, a2⟩ := pick ((p-1)/2) (p^j') ((p^j'-1)/2) (e - c) hg (by omega) exact ⟨d, hd, by omega, by omega⟩ have P2' : (q^(k-1)-1)/2 ≤ (p^j'-1)/2 := by rcases hA.2 with h | h · subst h; simp · exact h obtain ⟨x, y, hx, hy, hxy⟩ := ih j' k (c + d*p^j') e (by omega) ((mmono p j' (by omega)).trans P1) P2' hc1 hc2 exact ⟨d * p^j' + x, y, ⟨d, hd, x, hx, rfl⟩, hy, by omega⟩ · have hk1 : 1 ≤ k := by by_contra hk0 have : k = 0 := by omega subst this have : j ≠ 0 := by omega exact hA ⟨by omega, Or.inl rfl⟩ obtain ⟨k', rfl⟩ : ∃ k', k = k' + 1 := ⟨k-1, by omega⟩ simp only [Nat.add_sub_cancel] at P2 hA have hg := mfact q k' hq have hs' := mstep q k' hq have P1' : (p^(j-1)-1)/2 ≤ (q^k'-1)/2 := by by_cases hj : j = 0 · subst hj; simp · have := not_and.1 hA (by omega) push_neg at this exact this.2.le obtain ⟨d, hd, hc1, hc2⟩ : ∃ d ≤ (q-1)/2, e + d*q^k' ≤ c + (p^j-1)/2 ∧ c ≤ e + d*q^k' + (q^k'-1)/2 := by by_cases hec : c ≤ e · exact ⟨0, Nat.zero_le _, by simpa using h2, by omega⟩ · obtain ⟨d, hd, a1, a2⟩ := pick ((q-1)/2) (q^k') ((q^k'-1)/2) (c - e) hg (by omega) exact ⟨d, hd, by omega, by omega⟩ obtain ⟨x, y, hx, hy, hxy⟩ := ih j k' c (e + d*q^k') (by omega) P1' ((mmono q k' (by omega)).trans P2) (by omega) hc1 exact ⟨x, d * q^k' + y, hx, ⟨d, hd, y, hy, rfl⟩, by omega⟩ lemma far (p q : ℕ) (hp : Odd p) (hq : Odd q) (hp3 : 3 ≤ p) (hq3 : 3 ≤ q) (j k : ℕ) (a1 : q^(k-1) ≤ p^j) (a2 : 2*p^j+1 ≤ q^k) : ∃ n, p^j ≤ n ∧ (∃ j, Gt p j n) ∧ (∃ k, Gt q k n) := by have P1 : (p^(j-1)-1)/2 ≤ (q^k-1)/2 := by apply Nat.div_le_div_right have := Nat.pow_le_pow_right (by omega : 1 ≤ p) (Nat.sub_le j 1) omega have P2 : (q^(k-1)-1)/2 ≤ (p^j-1)/2 := Nat.div_le_div_right (by omega) obtain ⟨x, y, hx, hy, hxy⟩ := gap p q hp hq hp3 hq3 _ j k (p^j) 0 rfl P1 P2 (by omega) (by omega) refine ⟨y, by omega, ⟨j+1, 1, by omega, x, hx, by omega⟩, ⟨k, hy⟩⟩ lemma big (p q : ℕ) (hp : Odd p) (hq : Odd q) (hp5 : 5 ≤ p) (hq3 : 3 ≤ q) (N : ℕ) : ∃ n, N < n ∧ (∃ j, Gt p j n) ∧ (∃ k, Gt q k n) := by have hN : N < p^N := Nat.lt_pow_self (by omega) have l1 := Nat.pow_log_le_self q (x := p^N) (by positivity) have l2 : p^N < q^(Nat.log q (p^N) + 1) := Nat.lt_pow_succ_log_self (by omega : 1 < q) (p^N) set k := Nat.log q (p^N) by_cases hc : 2*p^N+1 ≤ q^(k+1) · obtain ⟨n, hn, h⟩ := far p q hp hq (by omega) hq3 N (k+1) (by simpa using l1) hc exact ⟨n, by omega, h⟩ · have h3 : 2 * q^(k+1) + 1 ≤ p^(N+1) := by rw [pow_succ p] have := Nat.mul_le_mul_left (p^N) hp5 omega obtain ⟨n, hn, h1, h2⟩ := far q p hq hp hq3 (by omega) (k+1) (N+1) (by simp; omega) h3 exact ⟨n, by omega, h2, h1⟩ theorem erdos_task : ∀ {p q : ℕ} (h₁ : p.Prime) (h₂ : Odd p) (h₃ : q.Prime) (h₄ : Odd q), { (n : ℕ) | n.centralBinom.Coprime (p * q) }.Infinite := by intro p q h₁ h₂ h₃ h₄ apply Set.infinite_of_forall_exists_gt intro N have hp3 : 3 ≤ p := by have := h₁.two_le; obtain ⟨r, hr⟩ := h₂; omega have hq3 : 3 ≤ q := by have := h₃.two_le; obtain ⟨r, hr⟩ := h₄; omega obtain ⟨n, hn, ⟨j, hj⟩, ⟨k, hk⟩⟩ : ∃ n, N < n ∧ (∃ j, Gt p j n) ∧ (∃ k, Gt q k n) := by by_cases h5 : 5 ≤ p · exact big p q h₂ h₄ h5 hq3 N by_cases h5' : 5 ≤ q · obtain ⟨n, hn, a, b⟩ := big q p h₄ h₂ h5' hp3 N exact ⟨n, hn, b, a⟩ have hp : p = 3 := by obtain ⟨r, hr⟩ := h₂; omega have hq : q = 3 := by obtain ⟨r, hr⟩ := h₄; omega subst hp hq have := Nat.lt_pow_self (n := N) (by omega : 1 < 3) obtain ⟨n, hn, h⟩ := far 3 3 h₂ h₄ le_rfl le_rfl N (N+1) (by simp) (by rw [pow_succ]; omega) exact ⟨n, by omega, h⟩ refine ⟨n, ?_, hn⟩ show Nat.Coprime _ _ apply Nat.Coprime.mul_right · exact (Gb_cop p h₁ h₂ j n (Gt_Gb p j n hj)).symm · exact (Gb_cop q h₃ h₄ k n (Gt_Gb q k n hk)).symm