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

Recorded description

If p is prime and p divides a*b, then p divides a or p divides b. Here `p is prime` means 2 <= p and every divisor of p is 1 or p.

Formal statement
theorem Nat.euclid_lemma : ((p : AxNat) -> ((a : AxNat) -> ((b : AxNat) -> ((hp : (And (AxNat.le (AxNat.succ (AxNat.succ AxNat.zero)) p) ((d : AxNat) -> ((hd : AxNat.dvd d p) -> Or (Eq.{1} AxNat d (AxNat.succ AxNat.zero)) (Eq.{1} AxNat d p))))) -> ((h : AxNat.dvd p (AxNat.mul a b)) -> Or (AxNat.dvd p a) (AxNat.dvd p b))))))

Dependencies

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

Evidence

kernel-Nat.euclid_lemma

Kind
kernel-term
Status
checked

Supports: If p is prime and p divides a*b, then p divides a or p divides b.

Checker command
test "$(cargo run -q -p axeyum-lean-kernel --example nat_theorem_inventory -- euclid_lemma 2>/dev/null | grep -xFc 'Nat.euclid_lemma	7	((x0 : AxNat) -> ((x1 : AxNat) -> ((x2 : AxNat) -> ((x3 : And (AxNat.le (AxNat.succ (AxNat.succ AxNat.zero)) x0) (((x3 : AxNat) -> ((x4 : AxNat.dvd x3 x0) -> Or (Eq.{1} AxNat x3 (AxNat.succ AxNat.zero)) (Eq.{1} AxNat x3 x0))))) -> ((x4 : AxNat.dvd x0 (AxNat.mul x1 x2)) -> Or (AxNat.dvd x0 x1) (AxNat.dvd x0 x2))))))')" -ge 1
Evidence notes

`build_nat_prelude` admits this through the trusted `Kernel::add_declaration` gate, which re-checks the proof term against the stated type, so producing the row is a machine-checked proof. Primality is spelled inline as `2 <= p AND forall d, d | p -> d = 1 OR d = p`, matching this fact's `formal.statement` rather than a `Prime` abbreviation -- a fact is only closed by the statement it actually makes. Proof: let g = gcd p a; g | p, so primality splits g = 1 or g = p. If g = p then p = gcd p a | a. If g = 1, Bezout gives naturals with (1 + p*mn) + a*nn = p*mp + a*np; scaling by b puts it in the form b + X = Y with p | X and p | Y (using p | a*b on the a-terms), and `dvd_add_right_cancel_of_pos` yields p | b WITHOUT forming a difference, which is what makes the argument valid over the naturals. The command names its own subject twice over: the example exits non-zero for a name that does not exist, and the grep requires the admitted declaration to be printed. TIGHTENED 2026-08-17: the command matched the NAME only, which a weakened statement survives. Lane `nat-prime-divisor` measured this concretely on its own theorem — spelling a primality bound `1 <= p` instead of `2 <= p` still type-checks, still admits, and passes every name-only checker, while being satisfied by p = 1. The kernel cannot see a weaker statement; only comparing the rendered TYPE can. This now matches the full type exactly (grep -qxF), so any change to the proposition breaks it.

footprint-Nat.euclid_lemma

Kind
exhaustive-enumeration
Status
checked

Supports: axiom_footprint: [] -- the Nat prelude's trusted surface is empty

Checker command
cargo run -q -p axeyum-lean-kernel --example nat_axiom_inventory -- --require-axiom-free nat
Evidence notes

`theorem_axiom_footprint` reports `nat Nat.euclid_lemma 0` and `integer Nat.euclid_lemma 0` directly. `nat_axiom_inventory` bounds it: the enumeration reports `nat: axiom=0 opaque=0 quotient=0 total_trusted=0`, and a theorem cannot depend on a trusted declaration the environment does not contain. Counting `Declaration::Axiom` alone would NOT suffice -- `Opaque` has no proof body and `Quotient` admits `Quot.sound` -- so the enumeration covers all three.

Provenance

{
  "date": "2026-08-14",
  "established_by": "not established in this ledger",
  "source": "proposition extracted from the S:number strand of the math-education concept graph; statement authored here, nothing copied",
  "prior_art": [
    {
      "who": "Euclid",
      "what": "Elements, Book VII, Proposition 30",
      "year": -300,
      "attribution": "standard textbook attribution; this lane did not consult the primary source"
    }
  ]
}