not_is_intersective_sq_add_one
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
- digit_exchange_walsh_root_poly_evalEvaluating the root polynomial C(v^2) + (X^2+X+C c)^2 * (C(s^2) + C(t^2) X^2 + C t X) at a gives v^2 + (a^2+a+c)^2 (s^2 + t^2 a^2 + t a).
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.
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).
uses
Polynomial.eval_add,Polynomial.eval_pow,Polynomial.eval_X,Polynomial.eval_oneintro 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
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.
uses
ZMod.intCast_eq_intCast_iffhave 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'
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.
have hnone : ¬ ∃ x : ZMod 3, x ^ 2 + 1 = 0 := by decide
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.
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.
- The nonexistence of roots in ZMod 3 on line 12 is proved by the `decide` tactic, which exhaustively checks the equation on all three elements 0, 1, and 2 of the finite ring.
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.
/-- 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⟩