AFTD Auto-Formalizing Theoretical Domains

prime_shift_multiples_bijective

theoremverified

In the finite field ZMod n where n is prime, multiplication by any non-zero element s induces a bijection on ZMod n.

Statement

theorem prime_shift_multiples_bijective (n : ℕ) [Fact n.Prime] (s : ZMod n) (hs : s ≠ 0) :
    Function.Bijective (fun (k : ZMod n) => k * s)
Source
arXiv:2610.24758 Lemma 1 proof
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1
  • good_slopes_mem_iffA slope m is good for the permutation f of ℤ/nℤ exactly when x ↦ f(x) + m·x is a bijection of ℤ/nℤ: m ∈ D_n(f) ↔ Function.Bijective (fun x…

Read back from the Lean

For any natural number $n$ such that $n$ is prime (given by Fact n.Prime), and for any non-zero element $s \in \mathbb{Z}/n\mathbb{Z}$ (i.e. $s \neq 0$), the function from $\mathbb{Z}/n\mathbb{Z}$ to $\mathbb{Z}/n\mathbb{Z}$ given by $k \mapsto k \cdot s$ is bijective.

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

Since $n$ is prime, $\mathbb{Z}/n\mathbb{Z}$ is a field, which makes it a group with zero. The result follows immediately from the library equivalence `Equiv.mulRight₀`, which establishes that right multiplication by any non-zero element in a group with zero is an equivalence (and hence a bijection).

  1. Right multiplication by $s$ is a bijection on $\mathbb{Z}/n\mathbb{Z}$.

    Since $n$ is prime, $\mathbb{Z}/n\mathbb{Z}$ is a field, hence a group with zero. In any group with zero, right multiplication by a non-zero element $s$ forms a permutation (an equivalence) of the underlying set via `Equiv.mulRight₀`. Since every equivalence is a bijection, its underlying function $k \mapsto k \cdot s$ is bijective.

    line 4

    uses Equiv.mulRight₀

      exact (Equiv.mulRight₀ s hs).bijective
Equiv.mulRight₀
Right multiplication by a non-zero element in a structure with multiplication and zero (such as a field) is an equivalence (permutation).

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

/-- Multiplication by a non-zero element in ZMod n is bijective for prime n. -/theorem prime_shift_multiples_bijective (n : ℕ) [Fact n.Prime] (s : ZMod n) (hs : s ≠ 0) :    Function.Bijective (fun (k : ZMod n) => k * s) := by  exact (Equiv.mulRight₀ s hs).bijective
See it in the graphDiscuss this resultChallenge it