Foundation Primitive Recognition Calculus Orbit Euclidean Gcd Ne Zero Of Right N

The nonzero divisor guarantee

The greatest common divisor (gcd) of two natural numbers is the largest number that divides both. For example, the gcd of 12 and 18 is 6, and the gcd of 5 and 7 is 1. A basic fact about this operation is that the gcd of two numbers is zero only when both numbers are zero. The theorem gcd_ne_zero_of_right_ne_zero states this in the framework's own arithmetic system: if the second of two numbers is not zero, then their gcd is not zero.

This sounds trivial, but it is a load-bearing condition. In the framework's ledger, a discrete record of counting events, division and ratio normalization require a divisor that is provably nonzero. When the framework computes the gcd of a ratio's numerator and denominator, it needs to know that this gcd is not zero before it can divide by it. The theorem supplies exactly that guarantee, using the fact that the denominator of any ratio is never zero.

The proof is short and mechanical. It assumes the gcd is zero, translates the statement into the ordinary natural numbers, uses the standard fact that a gcd of zero forces both inputs to be zero, and then contradicts the assumption that the second input is nonzero. The framework's machine-checked library of formal theorems records this proof as a theorem, not as a definition or a hypothesis.

What the theorem does not claim is broader. It does not say that the gcd is nonzero when only the first input is nonzero; that would be false, since gcd(0, 5) is 5 but gcd(5, 0) is 5 as well. It does not assert that the gcd is always positive, only that it is not zero under the stated condition. And it says nothing about the value of the gcd, only about its nonzero status. The theorem is a small but necessary brick in the framework's construction of ratio normalization, where every division must be justified by a nonzero divisor.

theorem gcd_ne_zero_of_right_ne_zero (a b : DistinctionNat) (hb : b ≠ zero) :
    gcd a b ≠ zero := by
  intro h
  have hnat : (gcd a b).toNat = 0 := by
    rw [h, toNat_zero]
  rw [gcd_toNat] at hnat
  have hb0 : b.toNat = 0 := (Nat.gcd_eq_zero_iff.mp hnat).2
  apply hb
  apply toNat_inj
  rw [hb0, toNat_zero]

theorem gcd_ne_zero_of_right_ne_zero (a b : DistinctionNat) (hb : b ≠ zero) :
    gcd a b ≠ zero := by
  intro h
  have hnat : (gcd a b).toNat = 0 := by
    rw [h, toNat_zero]
  rw [gcd_toNat] at hnat
  have hb0 : b.toNat = 0 := (Nat.gcd_eq_zero_iff.mp hnat).2
  apply hb
  apply toNat_inj
  rw [hb0, toNat_zero]

What this page does not claim

The theorem does not claim the gcd is nonzero when only the first input is nonzero. The theorem does not assert the gcd is positive, only that it is not zero. The theorem does not say anything about the value of the gcd, only its nonzero status.

Verify this page

Every tagged claim above names its theorem. To check one yourself rather than trust this page, elaborate the source module with Lean 4 and audit its axiom basis:

$ lake env lean IndisputableMonolith/Foundation/PrimitiveRecognitionCalculus/OrbitEuclidean.lean
expected axiom basis: [propext, Classical.choice, Quot.sound] (the Lean kernel's standard three; no RS-specific axioms)

A page whose claims cannot be reproduced this way does not ship. In production, every anchor links to the exact declaration in the public source release, and this block carries the build receipt for the page itself.

Derived articles

This page is generated by a question-recursion engine: the questions its answers raise become the next pages. The current agenda, with open targets marked red: