AFTD Auto-Formalizing Theoretical Domains

is_intersective_exists_pos

theoremverified

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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • 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
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).

  1. 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).

    lines 3–4

    uses Int.modEq_iff_dvd, dvd_trans

      rw [Int.modEq_iff_dvd] at *
      exact dvd_trans h (p.sub_dvd_eval_sub b a)
  2. 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 ℕ.

    lines 9–14

    uses Int.natCast_pos.mpr, ne_of_gt, Int.emod_nonneg

      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
  3. 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.

    lines 15–17

    uses Int.toNat_of_nonneg, Int.natCast_pos

      refine ⟨n, ?_, ?_⟩
      · rw [hn_def, ← Int.natCast_pos, Int.toNat_of_nonneg h_nonneg]
        exact h_pos
  4. 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.

    lines 18–20

    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
  5. 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.

    line 21

    uses is_intersective_exists_pos_eval_modEq

        exact (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.

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

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
See it in the graphDiscuss this resultChallenge it