is_intersective_of_root
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.
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.
intro m _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.
use r rw [hr]
- In line 6, after rewriting with the hypothesis hr, Lean's rw tactic automatically closes the resulting trivial congruence 0 ≡ 0 [ZMOD m] by reflexivity.
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.
/-- 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]