AFTD Auto-Formalizing Theoretical Domains

scalar_sampler_integrality_of_modEq

theoremverified

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 LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…

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.

  1. 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)$.

    lines 5–7

      rcases hB.dvd with ⟨k, hk⟩
      have hk' : m_j * A + B = m_j^2 * (-k) := by
        linarith
  2. 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.

    line 8

      refine ⟨-k, ?_⟩
  3. 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.

    lines 9–10

      have hq : (m_j : ℚ) * (A : ℚ) + (B : ℚ) = (m_j : ℚ)^2 * (-(k : ℚ)) := by
        exact_mod_cast hk'
  4. 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.

    lines 11–12

    uses mul_comm, mul_left_comm, mul_assoc

      field_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

/-- 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
See it in the graphDiscuss this resultChallenge it