Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Integer divisibility read off congruences modulo n

Definition
TauCeti_Data_ZMod_Divisibility

by riccardo.brasca · Sep 29, 2026 · Mathlib 0df444a (Lean v4.33.1)

number-theorytauceti-chebotarev

If integers z,wz,wz,w have nonnegative product and are congruent modulo mmm, then their absolute values are congruent modulo mmm:

zw≥0,z≡w(modm)⟹∣z∣≡∣w∣(modm).zw\geq0,\quad z\equiv w\pmod m\quad\Longrightarrow\quad |z|\equiv|w|\pmod m.zw≥0,z≡w(modm)⟹∣z∣≡∣w∣(modm).

This supports congruence calculations involving absolute norms.

Formalization Note. These foundational declarations are transplanted from the Tau Ceti contributors' original source (Apache-2.0, commit 948fe4751b1fe528b6d580c522ca5d743d47f185), with compatibility adaptations for Lean 4.33.1. Mathematical proofs requiring separate theorem nodes are published separately.

Definition code
/- Transplanted from https://github.com/TauCetiProject/TauCeti at 948fe4751b1fe528b6d580c522ca5d743d47f185.
Original source copyright/license notices are retained below.
Generated exclusively from compiler declaration, command, and reference facts. -/
import Mathlib.Data.ZMod.Basic
import Mathlib.Data.ZMod.Units

section
set_option autoImplicit true
/-
Copyright (c) 2026 Chris Birkbeck. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Chris Birkbeck
-/
/-!
# Integer divisibility read off congruences modulo `n`

Facts about integers read off congruences in `ZMod n`.

A linear congruence with unit coefficient is solvable: if `b` is a unit modulo `n`, then some
residue `j : ZMod n` satisfies `n ∣ a - j.val * b` over `ℤ`. The solution is `j = a b⁻¹`, and it
is returned as a residue class together with its canonical representative `j.val`, which is the
form a coset representative indexed by `Fin n` needs.

`ZMod.exists_dvd_sub_val_mul` was extracted from
`TauCeti/NumberTheory/ModularForms/CongruenceSubgroups.lean`, where it was private; that index
calculation was ported from the AINTLIB `LeanModularForms` project
(`LeanModularForms/HeckeRIngs/GL2/CongruenceIndex.lean`, Chris Birkbeck, Apache-2.0). The lemma is
consumed there and in `HeckeRing/GL2/Gamma1/CoprimeCosets.lean`.

`ZMod.natCast_dvd_val_sub_of_unitsMap_eq` is adapted from the same project (Chris Birkbeck,
`github.com/CBirkbeck/AINTLIB`, Apache-2.0) at commit `2baa76f74`, file
`projects/LeanModularForms/LeanModularForms/Eigenforms/ConductorTheorem.lean`, declaration
`natCast_val_sub_dvd_of_unitsMap_eq` (:665). Two departures from the source: it is stated for an
arbitrary divisor `d ∣ N` rather than only for the reduction modulo `N / l`, which is all its
proof uses, and the name places the divisibility in Mathlib's operand order.

## Main results

* `ZMod.exists_dvd_sub_val_mul`: the congruence `j b ≡ a (mod n)` has a solution `j : ZMod n`
  whenever `b` is a unit modulo `n`.
* `ZMod.natCast_dvd_val_sub_of_unitsMap_eq`: two units with the same image under `ZMod.unitsMap`
  along `d ∣ N` have representatives congruent modulo `d`, as integers.
* `ZMod.intCast_lcm_eq_of_eq_of_eq`: one residue modulo `lcm a b` from the residues modulo `a`
  and `b` — the Chinese remainder theorem for a single integer.
* `ZMod.natCast_natAbs_eq_of_mul_nonneg`: congruent integers with nonnegative product have
  congruent absolute values.
-/

 section

namespace ZMod







/-- **Congruent integers with nonnegative product have congruent absolute values.** If
`z * w ≥ 0` and `z ≡ w` modulo `m`, then `|z| ≡ |w|` modulo `m`. -/
theorem natCast_natAbs_eq_of_mul_nonneg {m : ℕ} {z w : ℤ} (hzw : 0 ≤ z * w)
    (h : (z : ZMod m) = w) : (z.natAbs : ZMod m) = w.natAbs := by
  rcases hzw.lt_or_eq with hzw | hzw
  · rcases pos_and_pos_or_neg_and_neg_of_mul_pos hzw with ⟨hz, hw⟩ | ⟨hz, hw⟩ <;>
      simp [← Int.cast_natCast (R := ZMod m), abs_of_pos, abs_of_neg, hz, hw, h]
  -- if one of them vanishes, both are divisible by `m`, and so are their absolute values
  rcases mul_eq_zero.mp hzw.symm with rfl | rfl
  · rw [Int.cast_zero, eq_comm, ZMod.intCast_zmod_eq_zero_iff_dvd] at h
    rw [Int.natAbs_zero, Nat.cast_zero, eq_comm, ZMod.natCast_eq_zero_iff]
    exact Int.natCast_dvd.mp h
  · rw [Int.cast_zero, ZMod.intCast_zmod_eq_zero_iff_dvd] at h
    rw [Int.natAbs_zero, Nat.cast_zero, ZMod.natCast_eq_zero_iff]
    exact Int.natCast_dvd.mp h

end ZMod

end
end
Source
https://github.com/TauCetiProject/TauCeti/blob/948fe4751b1fe528b6d580c522ca5d743d47f185/TauCeti/Data/ZMod/Divisibility.lean

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me