quadratic_red_mod17_certificate
No three elements x,y,z of {0,3,6} modulo 17 satisfy x − 2y + z = 2.
Statement
theorem quadratic_red_mod17_certificate : ∀ x y z : ZMod 17, x ∈ ({0, 3, 6} : Finset (ZMod 17)) → y ∈ ({0, 3, 6} : Finset (ZMod 17)) → z ∈ ({0, 3, 6} : Finset (ZMod 17)) → x - 2 * y + z ≠ 2- Source
- Exact finite modular computation for the rational quadratic approach to OP-1482.
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The theorem asserts that no triple $(x, y, z)$ chosen from $\{0, 3, 6\} \subseteq \mathbb{Z}/17\mathbb{Z}$ satisfies the linear relation $x - 2y + z = 2$. Because the domain is finite, the proof proceeds by exhaustive computation via Lean's `decide` tactic under increased resource limits.
For all $x, y, z \in \mathbb{Z}/17\mathbb{Z}$, if $x, y, z \in \{0, 3, 6\}$, then $x - 2y + z \neq 2$ in $\mathbb{Z}/17\mathbb{Z}$. automation
Since $\mathbb{Z}/17\mathbb{Z}$ is a finite type and membership in the finset $\{0, 3, 6\}$ as well as equality in $\mathbb{Z}/17\mathbb{Z}$ are decidable, the entire universal statement is decidable by exhaustive case analysis. The tactic `decide` evaluates this proposition by brute-force computation across all triples, completing under the increased limits on recursion depth and heartbeats.
set_option maxRecDepth 32768 in set_option maxHeartbeats 3000000 in decide
- The universal statement is quantified over all triples $(x, y, z) \in (\mathbb{Z}/17\mathbb{Z})^3$, so Lean's decision procedure evaluates all $17^3 = 4913$ cases rather than restricting in advance to the $3^3 = 27$ triples in $\{0, 3, 6\}^3$. This large search space explains why the recursion depth (`maxRecDepth`) and heartbeat (`maxHeartbeats`) limits had to be explicitly raised.
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.
theorem quadratic_red_mod17_certificate : ∀ x y z : ZMod 17, x ∈ ({0, 3, 6} : Finset (ZMod 17)) → y ∈ ({0, 3, 6} : Finset (ZMod 17)) → z ∈ ({0, 3, 6} : Finset (ZMod 17)) → x - 2 * y + z ≠ 2 := by set_option maxRecDepth 32768 in set_option maxHeartbeats 3000000 in decide