scalar_sampler_integrality_of_modEq
If an integer B satisfies B ≡ -m_j * A (mod m_j^2) with m_j ≠ 0, then A / m_j + B / m_j^2 is an integer.
Statement
theorem scalar_sampler_integrality_of_modEq (m_j A B : ℤ) (hm : m_j ≠ 0)
(hB : B ≡ - m_j * A [ZMOD m_j^2]) :
∃ z : ℤ, (A : ℚ) / (m_j : ℚ) + (B : ℚ) / ((m_j : ℚ)^2) = (z : ℚ)- Source
- arXiv:2611.13281, Lemma 2.1 proof, step 1
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- LinearOrder.toTotalPreorderEvery
Read back from the Lean
For all integers $m_j$, $A$, and $B$, if $m_j \neq 0$ and $B \equiv -m_j \cdot A \pmod{m_j^2}$, then there exists an integer $z$ such that $\frac{A}{m_j} + \frac{B}{m_j^2} = z$ in the rational numbers $\mathbb{Q}$.
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 modular congruence $B \equiv -m_j A \pmod{m_j^2}$ implies that $-m_j A - B = m_j^2 k$ for some integer $k$, which rearranges to $m_j A + B = m_j^2 (-k)$. Choosing $-k$ as the integer witness, clearing denominators in the rational sum $A / m_j + B / m_j^2$ using $m_j \neq 0$ reduces the goal to this identity, completing the proof.
There exists an integer $k$ such that $m_j A + B = m_j^2 (-k)$.
By definition of the modular congruence $B \equiv -m_j A \pmod{m_j^2}$, the modulus $m_j^2$ divides $-m_j A - B$, which gives an integer quotient $k$ satisfying $-m_j A - B = m_j^2 k$. Multiplying by $-1$ and rearranging terms via linear arithmetic yields $m_j A + B = m_j^2 (-k)$.
rcases hB.dvd with ⟨k, hk⟩ have hk' : m_j * A + B = m_j^2 * (-k) := by linarith
It suffices to show that $(A : ℚ) / (m_j : ℚ) + (B : ℚ) / ((m_j : ℚ)^2) = (-k : ℚ)$.
We provide $-k$ as the explicit integer witness $z$ for the existential goal.
refine ⟨-k, ?_⟩The equality $(m_j : ℚ) \cdot (A : ℚ) + (B : ℚ) = (m_j : ℚ)^2 \cdot (-(k : ℚ))$ holds in $\mathbb{Q}$.
We cast the integer identity $m_j A + B = m_j^2 (-k)$ into the rational numbers.
have hq : (m_j : ℚ) * (A : ℚ) + (B : ℚ) = (m_j : ℚ)^2 * (-(k : ℚ)) := by exact_mod_cast hk'
The rational equality $(A : ℚ) / (m_j : ℚ) + (B : ℚ) / ((m_j : ℚ)^2) = (-k : ℚ)$ holds.
Since $m_j \neq 0$, clearing denominators transforms the sum of fractions into $A \cdot m_j + B = m_j^2 \cdot (-k)$. This matches our rational equality via the commutativity and associativity of multiplication.
uses
mul_comm,mul_left_comm,mul_assocfield_simp [hm] simpa [mul_comm, mul_left_comm, mul_assoc] using hq
mul_comm- Multiplication is commutative: $a \cdot b = b \cdot a$.
mul_left_comm- Multiplication satisfies the left-commutativity identity: $a \cdot (b \cdot c) = b \cdot (a \cdot c)$.
mul_assoc- Multiplication is associative: $(a \cdot b) \cdot c = a \cdot (b \cdot 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
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.
/-- If B ≡ -m_j * A mod m_j^2, then A / m_j + B / m_j^2 is an integer. -/theorem scalar_sampler_integrality_of_modEq (m_j A B : ℤ) (hm : m_j ≠ 0) (hB : B ≡ - m_j * A [ZMOD m_j^2]) : ∃ z : ℤ, (A : ℚ) / (m_j : ℚ) + (B : ℚ) / ((m_j : ℚ)^2) = (z : ℚ) := by rcases hB.dvd with ⟨k, hk⟩ have hk' : m_j * A + B = m_j^2 * (-k) := by linarith refine ⟨-k, ?_⟩ have hq : (m_j : ℚ) * (A : ℚ) + (B : ℚ) = (m_j : ℚ)^2 * (-(k : ℚ)) := by exact_mod_cast hk' field_simp [hm] simpa [mul_comm, mul_left_comm, mul_assoc] using hq