English
There is an equivalence between the integers and ℤ × Fin n for nonzero n: a ↦ (a/n, a.natMod n) with inverse (q,r) ↦ q·n + r.
Русский
Существет эквив between целые и ℤ × Fin(n) для не нулевого n: a ↦ (a/n, a.natMod n) и обратное (q,r) ↦ q·n + r.
LaTeX
$$$ \\mathbb{Z} \\cong \\mathbb{Z} \\times Fin(n) $ with $a \\mapsto (a/n, Fin.ofNat(n, a.natMod n))$ and inverse $(q,r) \\mapsto q\\,n + r$$$
Lean4
/-- The equivalence induced by `a ↦ (a / n, a % n)` for nonzero `n`.
See `Int.ediv_emod_unique` for a similar propositional statement. -/
@[simps]
def divModEquiv (n : ℕ) [NeZero n] : ℤ ≃ ℤ × Fin n where
-- TODO: could cast from int directly if we import `Data.ZMod.Defs`, though there are few lemmas
-- about that coercion.
toFun a := (a / n, Fin.ofNat n (a.natMod n))
invFun p := p.1 * n + ↑p.2
left_inv
a := by
simp_rw [Fin.val_ofNat, natCast_mod, natMod, toNat_of_nonneg (emod_nonneg _ <| natCast_eq_zero.not.2 (NeZero.ne n)),
emod_emod, ediv_mul_add_emod]
right_inv := fun ⟨q, r, hrn⟩ => by
simp only [Prod.mk_inj, Fin.ext_iff]
obtain ⟨h1, h2⟩ := Int.natCast_nonneg r, Int.ofNat_lt.2 hrn
rw [Int.add_comm, add_mul_ediv_right _ _ (natCast_eq_zero.not.2 (NeZero.ne n)), ediv_eq_zero_of_lt h1 h2, natMod,
add_mul_emod_self_right, emod_eq_of_lt h1 h2, toNat_natCast]
exact ⟨q.zero_add, Fin.val_cast_of_lt hrn⟩
