AFTD Auto-Formalizing Theoretical Domains

not_is_intersective_sq_add_one

theoremverified

The polynomial $X^2 + 1$ does not have an integer root modulo every positive integer (in particular modulo 3).

Statement

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

Read back from the Lean

It is false that for every natural number $m > 0$, there exists an integer $n$ such that the polynomial $X^2 + 1 \in \mathbb{Z}[X]$ evaluated at $n$ is congruent to $0$ modulo $m$ (as integers).

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

The theorem is proved by contradiction by testing the modulus m = 3. If X^2 + 1 had an integer root modulo every positive integer, it would have one modulo 3, yielding an element x ∈ ℤ/3ℤ such that x^2 + 1 = 0. However, exhaustive evaluation over the three elements of ℤ/3ℤ shows that no such root exists.

  1. Assuming the theorem false gives an integer root n modulo 3 satisfying n^2 + 1 ≡ 0 (mod 3).

    We argue by contradiction, assuming that X^2 + 1 has an integer root modulo every positive integer m. Specializing this hypothesis to m = 3 (since 0 < 3) yields an integer n such that eval(n, X^2 + 1) ≡ 0 (mod 3). Expanding the evaluation across the polynomial's addition, squaring, indeterminate X, and constant 1 simplifies this congruence to n^2 + 1 ≡ 0 (mod 3).

    lines 4–6

    uses Polynomial.eval_add, Polynomial.eval_pow, Polynomial.eval_X, Polynomial.eval_one

      intro h
      obtain ⟨n, hn⟩ := h 3 (by norm_num)
      simp only [Polynomial.eval_add, Polynomial.eval_pow, Polynomial.eval_X, Polynomial.eval_one] at hn
  2. The residue of n modulo 3 satisfies n^2 + 1 = 0 in ℤ/3ℤ.

    Applying ZMod.intCast_eq_intCast_iff to n^2 + 1 ≡ 0 (mod 3) equates the canonical images of n^2 + 1 and 0 in ℤ/3ℤ. Pushing the integer cast through the ring operations yields (n : ℤ/3ℤ)^2 + 1 = 0.

    lines 7–11

    uses ZMod.intCast_eq_intCast_iff

      have hz : (n : ZMod 3) ^ 2 + 1 = 0 := by
        have h' : ((n ^ 2 + 1 : ℤ) : ZMod 3) = ((0 : ℤ) : ZMod 3) :=
          (ZMod.intCast_eq_intCast_iff (n ^ 2 + 1) 0 3).mpr hn
        push_cast at h' ⊢
        exact h'
  3. No element x in ℤ/3ℤ satisfies x^2 + 1 = 0. automation

    Because ℤ/3ℤ is a finite ring of order 3, checking x = 0, 1, 2 gives 0^2 + 1 = 1, 1^2 + 1 = 2, and 2^2 + 1 = 5 ≡ 2, none of which is 0. The `decide` tactic checks this finite quantification automatically.

    line 12

      have hnone : ¬ ∃ x : ZMod 3, x ^ 2 + 1 = 0 := by decide
  4. Contradiction.

    The residue of n in ℤ/3ℤ provides a witness to ∃ x : ℤ/3ℤ, x^2 + 1 = 0, directly contradicting the fact that no such root exists.

    line 13

      exact hnone ⟨n, hz⟩
Polynomial.eval_add
Evaluating the sum of two polynomials at an element equals the sum of the individual evaluations.
Polynomial.eval_pow
Evaluating the n-th power of a polynomial at an element equals the n-th power of its evaluation.
Polynomial.eval_X
Evaluating the indeterminate polynomial X at an element returns that element.
Polynomial.eval_one
Evaluating the constant polynomial 1 at an element returns 1.
ZMod.intCast_eq_intCast_iff
Two integers have equal images under the canonical map to ℤ/cℤ if and only if they are congruent modulo c.

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 + 1 does not have a root modulo every positive integer. -/theorem not_is_intersective_sq_add_one :    ¬ (∀ m : ℕ, 0 < m → ∃ n : ℤ, (Polynomial.X ^ 2 + 1 : Polynomial ℤ).eval n ≡ 0 [ZMOD m]) := by  intro h  obtain ⟨n, hn⟩ := h 3 (by norm_num)  simp only [Polynomial.eval_add, Polynomial.eval_pow, Polynomial.eval_X, Polynomial.eval_one] at hn  have hz : (n : ZMod 3) ^ 2 + 1 = 0 := by    have h' : ((n ^ 2 + 1 : ℤ) : ZMod 3) = ((0 : ℤ) : ZMod 3) :=      (ZMod.intCast_eq_intCast_iff (n ^ 2 + 1) 0 3).mpr hn    push_cast at h' ⊢    exact h'  have hnone : ¬ ∃ x : ZMod 3, x ^ 2 + 1 = 0 := by decide  exact hnone ⟨n, hz⟩
See it in the graphDiscuss this resultChallenge it