AFTD Auto-Formalizing Theoretical Domains

zmod_intCast_eq_intCast_iff_of_abs_sub_lt

theoremverified

Two integers a, b with |a − b| < n are equal modulo n only if they are equal.

Statement

theorem zmod_intCast_eq_intCast_iff_of_abs_sub_lt (n : ℕ) (a b : ℤ) (h : |a - b| < n) :
    ((a : ZMod n) = (b : ZMod n)) ↔ a = b
Source
Helper for simple_graph_cycle_power_three_cover_three_tight_dvd (thread RT-1, the k = 3 case of OP-205, arXiv:2610.15635).
Verified
17 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 22

The proof, explained

The equivalence reduces to the forward implication: if two integers are congruent modulo n and have distance strictly less than n, they must be equal. Congruence modulo n means n divides their difference, but the only multiple of n with absolute value strictly less than n is zero.

  1. It suffices to show that if a ≡ b (mod n), then a = b.

    The reverse direction is trivial: if a = b, their images in ZMod n are identical by reflexivity. Thus, it suffices to prove the forward implication.

    line 3

      refine ⟨fun hab => ?_, fun hab => hab ▸ rfl⟩
  2. The difference b - a is zero.

    The assumption that a and b are equal modulo n means that n divides b - a (by ZMod.intCast_eq_intCast_iff_dvd_sub). Since |b - a| = |a - b| < n by symmetry of absolute difference (abs_sub_comm), b - a is a multiple of n whose absolute value is strictly less than n. By Int.eq_zero_of_abs_lt_dvd, this forces b - a = 0.

    lines 4–5

    uses ZMod.intCast_eq_intCast_iff_dvd_sub, Int.eq_zero_of_abs_lt_dvd, abs_sub_comm

      rw [ZMod.intCast_eq_intCast_iff_dvd_sub] at hab
      have := Int.eq_zero_of_abs_lt_dvd hab (by rwa [abs_sub_comm])
  3. a = b

    From b - a = 0, linear integer arithmetic immediately concludes that a = b.

    line 6

      omega
ZMod.intCast_eq_intCast_iff_dvd_sub
Two integers have the same residue modulo c if and only if c divides their difference.
Int.eq_zero_of_abs_lt_dvd
If an integer m divides x and |x| < m, then x = 0.
abs_sub_comm
The absolute difference is symmetric: |a - b| = |b - a|.

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

theorem zmod_intCast_eq_intCast_iff_of_abs_sub_lt (n : ℕ) (a b : ℤ) (h : |a - b| < n) :    ((a : ZMod n) = (b : ZMod n)) ↔ a = b := by  refine ⟨fun hab => ?_, fun hab => hab ▸ rfl⟩  rw [ZMod.intCast_eq_intCast_iff_dvd_sub] at hab  have := Int.eq_zero_of_abs_lt_dvd hab (by rwa [abs_sub_comm])  omega
See it in the graphDiscuss this resultChallenge it