/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/
module
public import FormalConjecturesUtilErdős Problem 676
References:
[Er79] Erdős, Paul, Some unconventional problems in number theory. Math. Mag. (1979), 67–70.
[Er79d] Erdős, P., Some unconventional problems in number theory. Acta Math. Acad. Sci. Hungar. (1979), 71–80.
[Er80] Erdős, Paul, A survey of problems in combinatorial number theory. Ann. Discrete Math. (1980), 89–115.
@[expose] public sectionnamespace Erdos676open FilterAn integer has a representation $ap^2+b$ with $p$ prime, $a \geq 1$, and $b < p$ if and only if $p^2 \leq n$ and $n \bmod p^2 < p$ for some prime $p$.
mp.refine_2 a:ℕp:ℕb:ℕhp:Nat.Prime pha:1 ≤ ahb:b < phb':b < p ^ 2⊢ (a * p ^ 2 + b) % p ^ 2 < p
simpa [Nat.add_mod, Nat.mul_mod, Nat.mod_eq_of_lt hb'] using hb All goals completed! 🐙
· mpr n:ℕ⊢ (∃ p, Nat.Prime p ∧ p ^ 2 ≤ n ∧ n % p ^ 2 < p) → ∃ a p b, Nat.Prime p ∧ 1 ≤ a ∧ b < p ∧ n = a * p ^ 2 + b rintro ⟨p, hp, hn, hr⟩ mpr n:ℕp:ℕhp:Nat.Prime phn:p ^ 2 ≤ nhr:n % p ^ 2 < p⊢ ∃ a p b, Nat.Prime p ∧ 1 ≤ a ∧ b < p ∧ n = a * p ^ 2 + b
refine ⟨n / p ^ 2, p, n % p ^ 2, hp, ?_, hr, ?_⟩ mpr.refine_1 n:ℕp:ℕhp:Nat.Prime phn:p ^ 2 ≤ nhr:n % p ^ 2 < p⊢ 1 ≤ n / p ^ 2mpr.refine_2 n:ℕp:ℕhp:Nat.Prime phn:p ^ 2 ≤ nhr:n % p ^ 2 < p⊢ n = n / p ^ 2 * p ^ 2 + n % p ^ 2
· mpr.refine_1 n:ℕp:ℕhp:Nat.Prime phn:p ^ 2 ≤ nhr:n % p ^ 2 < p⊢ 1 ≤ n / p ^ 2 exact Nat.div_pos hn (pow_pos hp.pos _) All goals completed! 🐙
· mpr.refine_2 n:ℕp:ℕhp:Nat.Prime phn:p ^ 2 ≤ nhr:n % p ^ 2 < p⊢ n = n / p ^ 2 * p ^ 2 + n % p ^ 2 simpa [Nat.mul_comm, Nat.add_comm] using (Nat.mod_add_div n (p ^ 2)).symm All goals completed! 🐙The integer $35$ has no representation $ap^2+b$ of the required form.
@[category test, AMS 11]
theorem not_representable_35 :
¬ ∃ a p b : ℕ, p.Prime ∧ 1 ≤ a ∧ b < p ∧ 35 = a * p ^ 2 + b := by ⊢ ¬∃ a p b, Nat.Prime p ∧ 1 ≤ a ∧ b < p ∧ 35 = a * p ^ 2 + b
rw [representation_iff_mod ⊢ ¬∃ p, Nat.Prime p ∧ p ^ 2 ≤ 35 ∧ 35 % p ^ 2 < p ⊢ ¬∃ p, Nat.Prime p ∧ p ^ 2 ≤ 35 ∧ 35 % p ^ 2 < p] ⊢ ¬∃ p, Nat.Prime p ∧ p ^ 2 ≤ 35 ∧ 35 % p ^ 2 < p
rintro ⟨p, hp, hn, hr⟩ p:ℕhp:Nat.Prime phn:p ^ 2 ≤ 35hr:35 % p ^ 2 < p⊢ False
have hp6 : p < 6 := by ⊢ ¬∃ a p b, Nat.Prime p ∧ 1 ≤ a ∧ b < p ∧ 35 = a * p ^ 2 + b p:ℕhp:Nat.Prime phn:p ^ 2 ≤ 35hr:35 % p ^ 2 < php6:p < 6⊢ False nlinarith p:ℕhp:Nat.Prime phn:p ^ 2 ≤ 35hr:35 % p ^ 2 < php6:p < 6⊢ False p:ℕhp:Nat.Prime phn:p ^ 2 ≤ 35hr:35 % p ^ 2 < php6:p < 6⊢ False
have hc : ∀ q : Fin 6, ¬ (q.val.Prime ∧ q.val ^ 2 ≤ 35 ∧ 35 % q.val ^ 2 < q.val) :=
by ⊢ ¬∃ a p b, Nat.Prime p ∧ 1 ≤ a ∧ b < p ∧ 35 = a * p ^ 2 + b p:ℕhp:Nat.Prime phn:p ^ 2 ≤ 35hr:35 % p ^ 2 < php6:p < 6hc:∀ (q : Fin 6), ¬(Nat.Prime ↑q ∧ ↑q ^ 2 ≤ 35 ∧ 35 % ↑q ^ 2 < ↑q)⊢ False decide p:ℕhp:Nat.Prime phn:p ^ 2 ≤ 35hr:35 % p ^ 2 < php6:p < 6hc:∀ (q : Fin 6), ¬(Nat.Prime ↑q ∧ ↑q ^ 2 ≤ 35 ∧ 35 % ↑q ^ 2 < ↑q)⊢ False p:ℕhp:Nat.Prime phn:p ^ 2 ≤ 35hr:35 % p ^ 2 < php6:p < 6hc:∀ (q : Fin 6), ¬(Nat.Prime ↑q ∧ ↑q ^ 2 ≤ 35 ∧ 35 % ↑q ^ 2 < ↑q)⊢ False
exact hc ⟨p, hp6⟩ ⟨hp, hn, hr⟩ All goals completed! 🐙The integer $899$ has no representation $ap^2+b$ of the required form.
@[category test, AMS 11]
theorem not_representable_899 :
¬ ∃ a p b : ℕ, p.Prime ∧ 1 ≤ a ∧ b < p ∧ 899 = a * p ^ 2 + b := by ⊢ ¬∃ a p b, Nat.Prime p ∧ 1 ≤ a ∧ b < p ∧ 899 = a * p ^ 2 + b
rw [representation_iff_mod ⊢ ¬∃ p, Nat.Prime p ∧ p ^ 2 ≤ 899 ∧ 899 % p ^ 2 < p ⊢ ¬∃ p, Nat.Prime p ∧ p ^ 2 ≤ 899 ∧ 899 % p ^ 2 < p] ⊢ ¬∃ p, Nat.Prime p ∧ p ^ 2 ≤ 899 ∧ 899 % p ^ 2 < p
rintro ⟨p, hp, hn, hr⟩ p:ℕhp:Nat.Prime phn:p ^ 2 ≤ 899hr:899 % p ^ 2 < p⊢ False
have hp30 : p < 30 := by ⊢ ¬∃ a p b, Nat.Prime p ∧ 1 ≤ a ∧ b < p ∧ 899 = a * p ^ 2 + b p:ℕhp:Nat.Prime phn:p ^ 2 ≤ 899hr:899 % p ^ 2 < php30:p < 30⊢ False nlinarith p:ℕhp:Nat.Prime phn:p ^ 2 ≤ 899hr:899 % p ^ 2 < php30:p < 30⊢ False p:ℕhp:Nat.Prime phn:p ^ 2 ≤ 899hr:899 % p ^ 2 < php30:p < 30⊢ False
have hc : ∀ q : Fin 30, ¬ (q.val.Prime ∧ q.val ^ 2 ≤ 899 ∧ 899 % q.val ^ 2 < q.val) :=
by ⊢ ¬∃ a p b, Nat.Prime p ∧ 1 ≤ a ∧ b < p ∧ 899 = a * p ^ 2 + b p:ℕhp:Nat.Prime phn:p ^ 2 ≤ 899hr:899 % p ^ 2 < php30:p < 30hc:∀ (q : Fin 30), ¬(Nat.Prime ↑q ∧ ↑q ^ 2 ≤ 899 ∧ 899 % ↑q ^ 2 < ↑q)⊢ False decide p:ℕhp:Nat.Prime phn:p ^ 2 ≤ 899hr:899 % p ^ 2 < php30:p < 30hc:∀ (q : Fin 30), ¬(Nat.Prime ↑q ∧ ↑q ^ 2 ≤ 899 ∧ 899 % ↑q ^ 2 < ↑q)⊢ False p:ℕhp:Nat.Prime phn:p ^ 2 ≤ 899hr:899 % p ^ 2 < php30:p < 30hc:∀ (q : Fin 30), ¬(Nat.Prime ↑q ∧ ↑q ^ 2 ≤ 899 ∧ 899 % ↑q ^ 2 < ↑q)⊢ False
exact hc ⟨p, hp30⟩ ⟨hp, hn, hr⟩ All goals completed! 🐙Is every sufficiently large integer of the form $ap^2+b$ for some prime $p$ and integers $a \geq 1$ and $0 \leq b < p$?
@[category research open, question, AMS 11]
theorem erdos_676 : ∀ᶠ n in atTop,
∃ a p b : ℕ, p.Prime ∧ 1 ≤ a ∧ b < p ∧ n = a * p ^ 2 + b := by ⊢ ∀ᶠ (n : ℕ) in atTop, ∃ a p b, Nat.Prime p ∧ 1 ≤ a ∧ b < p ∧ n = a * p ^ 2 + b
sorry All goals completed! 🐙/- TODO: Formalize the source's additional variants: the quantitative almost-all result, the
version without primality, the general pair $(A,f)$, and the questions about the minimal $c_n$. -/
end Erdos676