Mathlib v4.30 source proposition Nat.exists_mul_mod_eq_gcd

Identifier: F:ml430-nat-exists-mul-mod-eq-gcd-8bf9ec7e
Proof route: kernel-lean
External status: proved
Axiom footprint: Empty

Recorded description

The proposition declared as `Nat.exists_mul_mod_eq_gcd` in the pinned Mathlib v4.30 source.

Formal statement

∀ {k n : ℕ}, n.gcd k < k → ∃ m < k, n * m % k = n.gcd k

Dependencies

The graph shows direct ledger edges. Follow a node to open its artifact page.

15 direct dependencies 0 direct dependents Graph shows the first 8 on each side.

Evidence

kernel-Nat.exists_mul_mod_eq_gcd

Kind: kernel-term
Status: checked

Supports: The proposition declared as `Nat.exists_mul_mod_eq_gcd` in the pinned Mathlib v4.30 source.

Checker command

cargo test -p axeyum-lean-kernel --lib int_prelude::

Evidence notes

`Nat.exists_mul_mod_eq_gcd` in `crates/axeyum-lean-kernel/src/int_prelude/gcd.rs` (`declare_exists_mul_mod_eq_gcd`). Genuine work, not a corollary of the Bezout-witness landing: the Bezout identity `ofNat (gcd n k) = ofNat n * gcdA n k + ofNat k * gcdB n k` gives an INTEGER coefficient `gcdA n k` (possibly negative, possibly out of range), not the bounded NATURAL witness the statement demands. The bridge is reducing `gcdA n k` modulo `k` (`Int.ModEq.mul_left` to replace the coefficient by its residue, `Int.mod_modEq`/`Int.ModEq.symm` to name that residue, `Int.modEq_add_mul_left` to discard the `ofNat k * gcdB n k` summand as an exact multiple of the modulus, and `emod_eq_self_of_in_range` -- already `pub(super)` in `wilson.rs` -- to identify `emod (ofNat (gcd n k)) (ofNat k)` with `ofNat (gcd n k)` under the `gcd n k < k` hypothesis) then descending the resulting `Int` equation `ofNat (gcd n k) = ofNat (n * m % k)` to the stated `Nat` equation by `natAbs`, which is the identity on `ofNat` by computation. No new axiom, no new public lemma outside `gcd.rs`; every intermediate lemma used (`Int.modEq_add_mul_left`, `Int.ModEq.mul_left`, `Int.mod_modEq`, `Int.ModEq.symm`, `Int.emod_nonneg`, `Int.emod_lt_of_pos`, `Int.of_nat_nat_abs_of_nonneg`) already existed.

footprint-Nat.exists_mul_mod_eq_gcd

Kind: exhaustive-enumeration
Status: checked

Supports: axiom_footprint: [] -- this theorem's trusted closure is empty

Checker command

test "$(cargo run --release -q -p axeyum-lean-kernel --example theorem_axiom_footprint -- Nat.exists_mul_mod_eq_gcd 2>/dev/null | grep -xFc $'integer\tNat.exists_mul_mod_eq_gcd\t0\t')" -ge 1

Evidence notes

The matched row is `integer<TAB>Nat.exists_mul_mod_eq_gcd<TAB>0<TAB>` with an EMPTY trailing footprint column, so a nonzero footprint or an absent declaration both give a count of 0 and fail. Filed under the `integer` prelude key because the declaration is made by `int_prelude::gcd`, even though the interned name lives in the `Nat` namespace (mirrors `Int.gcd_eq_gcd_ab_witnesses`'s own `nat_gcd_a`/`nat_gcd_b` siblings). Run `--release`: in debug, building the full constructed environment stack-overflows, which is a resource limit and not a fact about this theorem.

Provenance

{
  "date": "2026-08-29",
  "established_by": "the `int-gcd-div` lane, by reducing the Bezout coefficient `Nat.gcdA n k` modulo `k` through the already-proved `Int.ModEq` congruence lemmas",
  "source": "statement-only extraction of `Nat.exists_mul_mod_eq_gcd` from Mathlib v4.30.0; no proof value was exposed",
  "prior_art": [
    {
      "who": "the Mathlib contributors",
      "what": "the theorem declaration `Nat.exists_mul_mod_eq_gcd`",
      "where": "mathlib4 commit c5ea00351c28e24afc9f0f84379aa41082b1188f (v4.30.0)",
      "year": 2026,
      "attribution": "the proposition was read from the pinned statement-only inventory; the proof term and tactic trace were not consulted"
    }
  ]
}