AFTD Auto-Formalizing Theoretical Domains

is_intersective_of_root

theoremverified

Every integer polynomial with an integer root has a root modulo every positive integer m.

Statement

theorem is_intersective_of_root (h : Polynomial ℤ) (r : ℤ) (hr : h.eval r = 0) :
    is_intersective h
Source
step towards op_153_subexp_bound_intersective_quadratic
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • is_intersectiveAn integer polynomial $h \in \mathbb{Z}[X]$ is intersective if for every positive integer $m$, there exists an integer $n$ such that…

The proof, explained

To show that an integer polynomial with an integer root r is intersective, we must show that it has a root modulo every positive integer m. Since r is an exact integer root, evaluating the polynomial at r gives zero, which is congruent to zero modulo every positive integer m. Taking r as the witness modulo m completes the proof.

  1. To show that h is intersective, it suffices to find an integer root modulo an arbitrary positive integer m.

    By definition, an integer polynomial h is intersective if for every integer m > 0, there exists an integer n such that h(n) ≡ 0 (mod m). We introduce an arbitrary positive integer m.

    line 4

      intro m _
  2. The integer root r satisfies h(r) ≡ 0 (mod m).

    We choose n = r as the witness. Since h(r) = 0 by hypothesis, the condition reduces to 0 ≡ 0 (mod m), which holds trivially.

    lines 5–6

      use r
      rw [hr]

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

/-- An integer polynomial with an integer root is intersective. -/theorem is_intersective_of_root (h : Polynomial ℤ) (r : ℤ) (hr : h.eval r = 0) :    is_intersective h := by  intro m _  use r  rw [hr]
See it in the graphDiscuss this resultChallenge it