is_intersective_exists_pos
If h ∈ ℤ[X] is intersective and m is a positive integer, there exists a positive integer n > 0 such that h(n) ≡ 0 (mod m).
Statement
theorem is_intersective_exists_pos (h : Polynomial ℤ) (hh : is_intersective h) (m : ℕ) (hm : 0 < m) :
∃ n : ℕ, 0 < n ∧ h.eval (n : ℤ) ≡ 0 [ZMOD m]- Source
- step towards op_153_subexp_bound_intersective_quadratic
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - is_intersectiveAn integer polynomial $h \in \mathbb{Z}[X]$ is intersective if for every positive integer $m$, there exists an integer $n$ such that…
- Cslib.SKI.Polynomial.evalSubstitute terms for the free variables of a polynomial
- TotalPreorderA total preorder: a preorder where
- Used by 1
- is_intersective_exists_evenEvery intersective polynomial $h \in \mathbb{Z}[X]$ takes an even value at some positive natural number $n > 0$.
The proof, explained
By definition, an intersective polynomial h has an integer root r modulo any given positive integer m. To produce a strictly positive natural number root n > 0, we take the non-negative remainder r % m and add m, setting n = r % m + m. This ensures n > 0 while preserving the congruence n ≡ r (mod m). Since polynomial evaluation preserves congruences modulo m, it follows that h(n) ≡ h(r) ≡ 0 (mod m).
Polynomial evaluation preserves congruence modulo m.
To show that p(a) ≡ p(b) (mod m) whenever a ≡ b (mod m), we rewrite modular equivalence in terms of divisibility (Int.modEq_iff_dvd), meaning m ∣ b - a. Since b - a divides p(b) - p(a) for any integer polynomial p, transitivity of divisibility (dvd_trans) implies m ∣ p(b) - p(a), which gives p(a) ≡ p(b) (mod m).
uses
Int.modEq_iff_dvd,dvd_transrw [Int.modEq_iff_dvd] at * exact dvd_trans h (p.sub_dvd_eval_sub b a)
Obtain an integer root r modulo m and define a strictly positive candidate natural number n.
By intersectivity of h, there exists an integer r such that h(r) ≡ 0 (mod m). Since m > 0 as an integer (Int.natCast_pos.mpr), m is non-zero (ne_of_gt), so the remainder r % m is non-negative (Int.emod_nonneg). Linear arithmetic then shows that r % m + m > 0 and 0 ≤ r % m + m. We define n as the natural number obtained by truncating this integer to ℕ.
uses
Int.natCast_pos.mpr,ne_of_gt,Int.emod_nonnegrcases hh m hm with ⟨r, hr⟩ have hm_pos : 0 < (m : ℤ) := Int.natCast_pos.mpr hm have h_emod_nonneg := Int.emod_nonneg r (ne_of_gt hm_pos) have h_pos : 0 < r % (m : ℤ) + (m : ℤ) := by linarith have h_nonneg : 0 ≤ r % (m : ℤ) + (m : ℤ) := by linarith set n := (r % (m : ℤ) + (m : ℤ)).toNat with hn_def
The candidate natural number n satisfies n > 0.
Providing n as the existential witness reduces the goal to proving 0 < n and h(n) ≡ 0 (mod m). For 0 < n, since r % m + m ≥ 0, converting to ℕ and casting back to ℤ is the identity (Int.toNat_of_nonneg). Thus 0 < n in ℕ is equivalent to 0 < r % m + m in ℤ (Int.natCast_pos), which was established in the previous step.
uses
Int.toNat_of_nonneg,Int.natCast_posrefine ⟨n, ?_, ?_⟩ · rw [hn_def, ← Int.natCast_pos, Int.toNat_of_nonneg h_nonneg] exact h_pos
As integers, n is congruent to r modulo m.
Unfolding the definition of integer modular equivalence (Int.ModEq) and using non-negativity to rewrite n as r % m + m (Int.toNat_of_nonneg), the congruence reduces to (r % m + m) % m = r % m. This holds because adding a multiple of m does not change the remainder modulo m, which simplification closes.
uses
Int.ModEq,Int.toNat_of_nonneg· have hnr : (n : ℤ) ≡ r [ZMOD m] := by rw [Int.ModEq, hn_def, Int.toNat_of_nonneg h_nonneg] simp
Evaluating h at n yields h(n) ≡ 0 (mod m), completing the theorem.
Applying the helper lemma is_intersective_exists_pos_eval_modEq to n ≡ r (mod m) shows that h(n) ≡ h(r) (mod m). Combining this with h(r) ≡ 0 (mod m) by transitivity of modular equivalence completes the proof.
uses
is_intersective_exists_pos_eval_modEqexact (is_intersective_exists_pos_eval_modEq h (n : ℤ) r m hnr).trans hr
Int.modEq_iff_dvd- Two integers are congruent modulo n if and only if n divides their difference.
dvd_trans- Divisibility is transitive: if a divides b and b divides c, then a divides c.
Int.natCast_pos.mpr- If a natural number is strictly positive, its coercion to an integer is strictly positive.
Int.emod_nonneg- For any integer a and non-zero integer b, the remainder a % b is non-negative.
ne_of_gt- A strictly greater element is not equal to the lesser one; in particular, a strictly positive integer is non-zero.
Int.natCast_pos- A natural number n is strictly positive if and only if its integer coercion is strictly positive.
Int.toNat_of_nonneg- If an integer a is non-negative, casting its natural-number conversion back to the integers returns a.
Int.ModEq- Modular equivalence of integers: a ≡ b [ZMOD m] means that a % m = b % m.
is_intersective_exists_pos_eval_modEq- Evaluating an integer polynomial at congruent inputs modulo m produces congruent outputs modulo m.
- A minor formal detail is the conversion between integers and natural numbers: the candidate n is defined by truncating the integer r % m + m to ℕ using Int.toNat, and its properties are proved by showing that non-negativity allows casting back to ℤ without change via Int.toNat_of_nonneg.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
lemma is_intersective_exists_pos_eval_modEq (p : Polynomial ℤ) (a b : ℤ) (m : ℤ) (h : a ≡ b [ZMOD m]) : p.eval a ≡ p.eval b [ZMOD m] := by rw [Int.modEq_iff_dvd] at * exact dvd_trans h (p.sub_dvd_eval_sub b a)/-- An intersective polynomial has a positive integer root modulo every positive integer m. -/theorem is_intersective_exists_pos (h : Polynomial ℤ) (hh : is_intersective h) (m : ℕ) (hm : 0 < m) : ∃ n : ℕ, 0 < n ∧ h.eval (n : ℤ) ≡ 0 [ZMOD m] := by rcases hh m hm with ⟨r, hr⟩ have hm_pos : 0 < (m : ℤ) := Int.natCast_pos.mpr hm have h_emod_nonneg := Int.emod_nonneg r (ne_of_gt hm_pos) have h_pos : 0 < r % (m : ℤ) + (m : ℤ) := by linarith have h_nonneg : 0 ≤ r % (m : ℤ) + (m : ℤ) := by linarith set n := (r % (m : ℤ) + (m : ℤ)).toNat with hn_def refine ⟨n, ?_, ?_⟩ · rw [hn_def, ← Int.natCast_pos, Int.toNat_of_nonneg h_nonneg] exact h_pos · have hnr : (n : ℤ) ≡ r [ZMOD m] := by rw [Int.ModEq, hn_def, Int.toNat_of_nonneg h_nonneg] simp exact (is_intersective_exists_pos_eval_modEq h (n : ℤ) r m hnr).trans hr