AFTD Auto-Formalizing Theoretical Domains

zmod_mul_unit_half_eq_zero_iff

theoremverified

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

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.

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

    lines 3–7

    uses mul_one, mul_zero

      constructor
      · intro hx
        calc x = x * (2 * u) := by rw [hu, mul_one]
          _ = 2 * (x * u) := by ring
          _ = 0 := by rw [hx, mul_zero]
  2. 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.

    line 8

    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

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