zmod_mul_unit_half_eq_zero_iff
In ZMod n, if 2u = 1 then x u = 0 iff x = 0.
Statement
theorem zmod_mul_unit_half_eq_zero_iff {n : ℕ} {u : ZMod n} (hu : 2 * u = 1) (x : ZMod n) :
x * u = 0 ↔ x = 0- Source
- lemma for arXiv:2610.23958 Proposition 6.2 (PR-301)
- Verified
- 20 Oct 2026
- Axioms
Quot.soundpropext- Used by 1
- perm_offset_avoiding_count_neg_one_one_eq_menage_of_oddFor odd n >= 3 the number of permutations avoiding the offsets {-1, 1} mod n equals the menage number U(n).
The proof, explained
The equivalence is established in two directions. For the forward direction, since 2u = 1, we can write x as x(2u), which rearranges to 2(xu) by the ring properties of ZMod n. When xu = 0, this expression evaluates to 0, showing x = 0. The reverse direction is immediate since multiplying zero by u yields zero.
If x * u = 0, then x = 0.
We split the equivalence into two implications and first prove the forward direction. Assume x * u = 0 (named hx). Since 2 * u = 1 (by hypothesis hu), we rewrite x as x * (2 * u) using mul_one. Associativity and commutativity of multiplication in ZMod n allow ring arithmetic to rewrite x * (2 * u) as 2 * (x * u). Substituting the assumption x * u = 0 into this product yields 2 * 0, which equals 0 by mul_zero, establishing x = 0.
uses
mul_one,mul_zeroconstructor · intro hx calc x = x * (2 * u) := by rw [hu, mul_one] _ = 2 * (x * u) := by ring _ = 0 := by rw [hx, mul_zero]
If x = 0, then x * u = 0.
For the reverse implication, assume x = 0 (named hx). Substituting 0 for x gives 0 * u, which equals 0 by zero_mul.
uses
zero_mul· intro hx; rw [hx, zero_mul]
mul_one- Multiplying any element by 1 on the right leaves it unchanged: a * 1 = a.
mul_zero- Multiplying any element by 0 on the right gives 0: a * 0 = 0.
zero_mul- Multiplying 0 on the left by any element gives 0: 0 * a = 0.
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_mul_unit_half_eq_zero_iff {n : ℕ} {u : ZMod n} (hu : 2 * u = 1) (x : ZMod n) : x * u = 0 ↔ x = 0 := by constructor · intro hx calc x = x * (2 * u) := by rw [hu, mul_one] _ = 2 * (x * u) := by ring _ = 0 := by rw [hx, mul_zero] · intro hx; rw [hx, zero_mul]