zmod_intCast_eq_intCast_iff_of_abs_sub_lt
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
- simple_graph_cycle_power_clique_arcFor n at least 3k+1, every nonempty clique of the k-th cycle power lies in a forward arc of k+1 vertices whose first vertex belongs to the…
- simple_graph_cycle_power_seven_adj_iffFor n ≥ 22, u and v are adjacent in C_n^7 iff v = u + e for an integer e with 0 < |e| ≤ 7.
- simple_graph_cycle_power_seven_cover_four_tight_alternateIn a tight cover of C_n^7 (n >= 22) by 4 equivalence subgraphs in which every class starting at i (the class of the distance-7 pair (i,…
- simple_graph_cycle_power_dyadic_cover_fibre_endpoint_uniqueIn any clique labeling of the cycle power C_n^{2^m-1} with n ≥ 3(2^m-1)+1, each clique contains at most one pair at distance 2^m-1.
- simple_graph_cycle_power_seven_cover_four_tight_one_iff_sixIn a tight cover of C_n^7 (n ≥ 22) by 4 equivalence subgraphs (every distance-7, 6, 4 pair covered exactly once, every class spanned by a…
- simple_graph_cycle_power_dyadic_layer_weight_leIn any clique labelling of a cycle power with dyadic bandwidth 2^m-1 and n at least three times the bandwidth plus one, the total layer…
- simple_graph_cycle_power_dyadic_cover_class_modelEvery optimal dyadic cycle-power equivalence cover admits a faithful periodic integer class model with the original rooted classes and…
- simple_graph_cycle_power_seven_layer_weight_leLet n ≥ 22 and let c label the vertices of C_n^7 so that every label class is a clique. Then Σ_i (2·[i ~ i+7] + [i ~ i+6] + [i ~ i+4]) ≤…
- simple_graph_cycle_power_fifteen_adj_iffFor n at least 46, adjacency in the fifteenth power of the cycle is displacement by a nonzero integer of absolute value at most 15.
- simple_graph_cycle_power_three_layer_weight_eq_impIn the situation of the weight inequality, if Σ_i (2·[c i = c(i+3)] + [c i = c(i+2)]) = n then every class contains a pair at distance 3…
- simple_graph_cycle_power_dyadic_cover_edge_spanIf a monochromatic clique contains v and v+d with 1 ≤ d < 2^m, its root v-a (with a ≤ 2^m-1) satisfies a < 2^m - d, so the entire edge {v,…
- cycle_strong_product_not_has_equivalence_cover_threeFor every m ≥ 6 and n ≥ 5, the strong product of cycles C_m and C_n (simple_graph_strong_prod of simple_graph_cycle_power m 1 and…
- simple_graph_cycle_power_dyadic_class_model_exact_dyadicFor every j < m and every integer vertex v there is exactly one offset a < 2^j such that the rooted class at a from v is active at both a…
- simple_graph_cycle_power_seven_cover_four_tight_dvdA tight cover of C_n^7 (n ≥ 22) by 4 equivalence subgraphs (every distance-7, 6, 4 pair covered exactly once, every class spanned by a…
- simple_graph_cycle_power_seven_cover_four_tightIn any cover of C_n^7 (n ≥ 22) by 4 equivalence subgraphs, every pair at distance 7, 6 or 4 is covered by exactly one layer, and every…
- simple_graph_cycle_power_seven_layer_weight_eq_class_five_imp_one_two_imp_sixLet c label the vertices of C_n^7 (n ≥ 22) so that every label class is a clique, with total weight Σ_i (2·[i ~ i+7] + [i ~ i+6] + [i ~…
- simple_graph_cycle_power_dyadic_cover_layer_root_uniqueIn an optimal (m+1)-layer cover of C_n^{2^m-1}, for each layer s and each vertex v, there is a unique offset a ≤ 2^m-1 such that v-a is…
- simple_graph_cycle_power_three_layer_weight_leLet n ≥ 10 and let c label the vertices of C_n^3 so that every label class is a clique. Then Σ_i (2·[i and i+3 share a class] + [i and i+2…
- simple_graph_cycle_power_three_cover_three_tight_dvdIf three labellings with clique classes satisfy the tight structure (each distance-3 pair and each distance-2 pair in exactly one layer,…
- simple_graph_cycle_power_dyadic_class_model_disjoint_coloursTwo active rooted classes at a common vertex with distinct offsets have distinct layer colours.
- simple_graph_cycle_power_adj_iff_of_bandwidth_ltWhen k<n, two vertices of the k-th cycle power are adjacent exactly when their difference has a nonzero signed integer representative of…
- simple_graph_cycle_power_three_adj_iffFor n ≥ 10, u and v are adjacent in C_n^3 iff v = u + e for an integer e with 0 < |e| ≤ 3.
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.
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.
refine ⟨fun hab => ?_, fun hab => hab ▸ rfl⟩
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.
uses
ZMod.intCast_eq_intCast_iff_dvd_sub,Int.eq_zero_of_abs_lt_dvd,abs_sub_commrw [ZMod.intCast_eq_intCast_iff_dvd_sub] at hab have := Int.eq_zero_of_abs_lt_dvd hab (by rwa [abs_sub_comm])
a = b
From b - a = 0, linear integer arithmetic immediately concludes that a = b.
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
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 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