Foundation Primitive Recognition Calculus Orbit Euclidean Divides Gcd Of Divides

The shared divisor rule

The greatest common divisor of two numbers is the largest number that divides both of them. A basic fact about this concept is that any number which divides both of the original numbers also divides their greatest common divisor. For example, 3 divides both 12 and 18, and 3 also divides 6, the greatest common divisor of 12 and 18. This property is so fundamental to arithmetic that it appears in any careful treatment of divisibility.

In the Recognition Science framework, arithmetic is rebuilt on a discrete record of events called a ledger, a finite counting system where numbers are generated by repeated steps. Within this system, the framework's machine-checked library of formal theorems proves the same shared divisor rule. The theorem, named divides_gcd_of_divides_left_right, states that if a number c divides both a and b, then c divides the greatest common divisor of a and b. The proof works by translating the statement into the ordinary natural numbers, where the standard result Nat.dvd_gcd already holds, and then carrying the conclusion back into the ledger system.

The framework's library also proves the companion facts that the greatest common divisor divides each of the original numbers, and that the greatest common divisor computed in the ledger matches the one computed in ordinary arithmetic. These results together establish that the ledger's notion of divisibility and greatest common divisor behaves exactly like the familiar one from elementary number theory. The shared divisor rule is the key step that makes this correspondence complete, because it shows that the ledger's greatest common divisor is not just a divisor of both numbers, but the greatest one in the divisibility order.

This theorem does not claim anything about the physical world. It is a statement about a formal counting system, and its proof is a matter of logic, not experiment. The rule holds for any two numbers in the ledger, but it says nothing about which numbers correspond to physical quantities, nor does it derive any physical constant. It is a piece of pure mathematics, useful because it shows that the framework's arithmetic is consistent with the arithmetic everyone already uses.

/-- Any common native divisor divides the native GCD. -/
theorem divides_gcd_of_divides_left_right {c a b : DistinctionNat}
    (hca : divides c a) (hcb : divides c b) :
    divides c (gcd a b) := by
  rw [divides_iff_toNat_dvd, gcd_toNat]
  exact Nat.dvd_gcd
    ((divides_iff_toNat_dvd c a).mp hca)
    ((divides_iff_toNat_dvd c b).mp hcb)

/-- Any common native divisor divides the native GCD. -/
theorem divides_gcd_of_divides_left_right {c a b : DistinctionNat}
    (hca : divides c a) (hcb : divides c b) :
    divides c (gcd a b) := by
  rw [divides_iff_toNat_dvd, gcd_toNat]
  exact Nat.dvd_gcd
    ((divides_iff_toNat_dvd c a).mp hca)
    ((divides_iff_toNat_dvd c b).mp hcb)

/-- The native GCD divides the left input. -/
theorem gcd_divides_left (a b : DistinctionNat) :
    divides (gcd a b) a := by
  rw [divides_iff_toNat_dvd, gcd_toNat]
  exact Nat.gcd_dvd_left a.toNat b.toNat

/-- The native GCD divides the right input. -/
theorem gcd_divides_right (a b : DistinctionNat) :
    divides (gcd a b) b := by
  rw [divides_iff_toNat_dvd, gcd_toNat]
  exact Nat.gcd_dvd_right a.toNat b.toNat

theorem gcd_toNat (a b : DistinctionNat) :
    (gcd a b).toNat = Nat.gcd a.toNat b.toNat := by
  unfold gcd
  apply gcdFuel_toNat_aux
  rw [toNat_add]

What this page does not claim

This theorem does not claim any physical interpretation or derivation of physical constants. The theorem does not claim that the ledger's arithmetic is the only way to define divisibility. The proof does not claim to be independent of the ambient type theory's axioms.

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: