Euclidean division exists for a nonnegative dividend

Identifier: F:int-euclid-of-nat
Proof route: kernel-lean
External status: proved
Axiom footprint: Empty

Recorded description

For naturals a and b, there exist integers q and r with a = (b+1)*q + r and 0 <= r < b+1 -- the division algorithm's existence half, specialized to a dividend represented by the ofNat constructor (so nonnegative) and a positive divisor b+1.

Formal statement

theorem Int.euclid_of_nat : ((x0 : AxNat) -> ((x1 : AxNat) -> Exists.{1} Int (fun (x2 : Int) => Exists.{1} Int (fun (x3 : Int) => And (Eq.{1} Int (Int.ofNat x0) (Int.add (Int.mul (Int.ofNat (AxNat.succ x1)) x2) x3)) (And (Int.le Int.zero x3) (Int.lt x3 (Int.ofNat (AxNat.succ x1))))))))

Dependencies

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

3 direct dependencies 1 direct dependents

Evidence

kernel-Int.euclid_of_nat

Kind: kernel-term
Status: checked

Supports: Int.euclid_of_nat is admitted by the trusted kernel gate with the type recorded in formal.statement.

Checker command

cargo run -q --release -p axeyum-lean-kernel --example theorem_dependency_inventory -- Int.euclid_of_nat 2>/dev/null | grep -cE '^Int\.euclid_of_nat[[:space:]]'

Evidence notes

`build_int_prelude` admits Int.euclid_of_nat through the trusted `Kernel::add_declaration` gate, which re-checks the proof term against the stated type, so a line in `theorem_dependency_inventory`'s output for the exact name is a machine-checked proof having been admitted. That tool exits non-zero for a named filter matching nothing (a deleted theorem cannot read as a re-derived one), and `grep -c` (never `-q`) both avoids a SIGPIPE-under-pipefail false negative and independently asserts the exact tab-anchored line is present. `--release` is MANDATORY: this tool unconditionally also builds `creal`/`complex`/`cpoint`, which recurse deep enough in a debug build to overflow the default thread stack (measured: release exits 0, debug SIGABRTs at 134).

footprint-Int.euclid_of_nat

Kind: exhaustive-enumeration
Status: checked

Supports: axiom_footprint: [] -- Int.euclid_of_nat lives in the Int prelude's trusted surface, which is empty.

Checker command

cargo run -q -p axeyum-lean-kernel --example nat_axiom_inventory -- --require-axiom-free integer

Evidence notes

`nat_axiom_inventory --require-axiom-free integer` builds the Int environment as its own group and reports `integer: axiom=0 opaque=0 quotient=0 total_trusted=0` (re-measured on this tree), exiting 0 with `ok: integer trusted surface = 0`. That bounds every individual Int theorem's footprint by [], since Int.euclid_of_nat cannot depend on a trusted declaration the environment does not contain. `--require-axiom-free <name>` is an error (not a silent pass) for a prelude this run never built, which is what makes `integer` here a claim rather than an absence.

Provenance

{
  "date": "2026-08-25",
  "established_by": "axeyum-lean-kernel build_int_prelude",
  "source": "theorem name and dependency edges from theorem_dependency_inventory; canonical type read via int_theorem_inventory, which already prints Int declarations with their canonical type and axiom footprint -- no probe crate was needed for this batch."
}