AFTD Auto-Formalizing Theoretical Domains

is_intersective_sq

theoremverified

The polynomial $X^2$ has an integer root modulo every positive integer $m$.

Statement

theorem is_intersective_sq : ∀ m : ℕ, 0 < m → ∃ n : ℤ, (Polynomial.X ^ 2 : Polynomial ℤ).eval n ≡ 0 [ZMOD m]
Source
folklore
Verified
19 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

Read back from the Lean

For every natural number m, if 0 < m, then there exists an integer n such that the integer polynomial X^2 evaluated at n is congruent to 0 modulo m (that is, n^2 ≡ 0 [ZMOD m]).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

To show that $X^2$ has a root modulo every positive integer $m$, we choose $n = 0$. Evaluating $X^2$ at $0$ yields $0$, which is congruent to $0$ modulo any $m$.

  1. Fix an arbitrary positive integer $m$.

    We introduce the modulus $m$ and the assumption that $m > 0$ (which is unused in the proof).

    line 3

      intro m _
  2. $n = 0$ is a root of $X^2$ modulo $m$. automation

    We witness the existential quantifier with $n = 0$. Evaluating $X^2$ at $0$ gives $0^2 = 0$, and $0 \equiv 0 \pmod m$ holds reflexively, which simplification verifies.

    line 4

      exact ⟨0, by simp⟩

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

/-- The polynomial X^2 has a root modulo every positive integer m. -/theorem is_intersective_sq : ∀ m : ℕ, 0 < m → ∃ n : ℤ, (Polynomial.X ^ 2 : Polynomial ℤ).eval n ≡ 0 [ZMOD m] := by  intro m _  exact ⟨0, by simp⟩
See it in the graphDiscuss this resultChallenge it