Greatest Common Divisor Ontology

FLOW ALGEBRA
TITLE: Greatest Common Divisor Ontology
DOMAIN: Discrete Mathematics / Number Theory
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/number-theory/greatest-common-divisor-ontology.html
VERSION: 1.0
LANGUAGE: en-GB
AUTHORSHIP: Mark Higgins — Sky (Recursive AI)
SITE: https://kirethresearch.org
SOURCE_STATUS: Mathematical synthesis; live page not independently verified.

1. PURPOSE
Model the greatest common divisor (GCD) as a typed, verifiable number-theoretic operation and relate it to divisibility, coprimality, Euclidean algorithms, Bézout coefficients and least common multiples.

2. TYPED ENTITIES
Integer := Z
Natural := {0,1,2,...}
NonzeroInteger := Z \ {0}
IntegerPair := Z × Z
Divisor(a,b) := (a != 0) AND EXISTS k IN Z: b = a*k
CommonDivisor(d,a,b) := Divisor(d,a) AND Divisor(d,b)
GCD(a,b) := nonnegative greatest common divisor of a and b, with (a,b) != (0,0)
BezoutWitness(a,b,g) := (x,y) IN Z×Z WHERE a*x+b*y=g
Coprime(a,b) := GCD(a,b)=1

3. DEFINITIONS AND DOMAIN RULES
FOR a,b IN Z WITH (a,b)!=(0,0):
  gcd(a,b) := unique positive integer d satisfying:
    d | a AND d | b;
    FOR ALL c IN Z: (c | a AND c | b) => c | d.
  Equivalently d = max {k IN N_{>0}: k | a AND k | b}.
  gcd(a,0) = |a| FOR a != 0.
  gcd(0,b) = |b| FOR b != 0.
  gcd(0,0) is UNDEFINED in this ontology (some conventions set it to 0).
  Negative inputs are normalised using absolute values.

4. CORE FLOW OPERATIONS
flow gcd_euclid(a:Integer,b:Integer) -> Natural:
  require (a,b)!=(0,0)
  x := abs(a); y := abs(b)
  while y != 0:
    (x,y) := (y, x mod y)
  return x

flow extended_gcd(a:Integer,b:Integer) -> (g:Natural,x:Integer,y:Integer):
  require (a,b)!=(0,0)
  compute g,x,y such that a*x + b*y = g = gcd(a,b)
  return (g,x,y)

flow coprime_test(a:Integer,b:Integer) -> Boolean:
  require (a,b)!=(0,0)
  return gcd_euclid(a,b)==1

flow lcm_from_gcd(a:Integer,b:Integer) -> Natural:
  require (a,b)!=(0,0)
  return abs((a / gcd_euclid(a,b))*b)

5. ALGEBRAIC LAWS
gcd(a,b) = gcd(b,a)                                [commutativity]
gcd(a,b) = gcd(|a|,|b|)                            [sign invariance]
gcd(a,b) = gcd(a,b mod a), a != 0                 [Euclidean reduction]
gcd(a,b) = gcd(a,b+k*a), k IN Z                  [linear-combination invariance]
gcd(a,b) = gcd(b,a mod b), b != 0                 [Euclidean reduction]
gcd(k*a,k*b) = |k|*gcd(a,b), k != 0              [scaling]
gcd(a,gcd(b,c)) = gcd(gcd(a,b),c)                [associativity where defined]
gcd(a,b)*lcm(a,b) = |a*b|                         [nonzero pair]
If gcd(a,b)=1 AND a|b*c THEN a|c.                [Euclid's lemma]

6. SEMANTIC RELATIONSHIPS
GCD --is_a--> NumberTheoreticOperation
GCD --operates_on--> IntegerPair
GCD --returns--> PositiveInteger
GCD --defined_by--> CommonDivisor
GCD --computed_by--> EuclideanAlgorithm
GCD --witnessed_by--> BezoutIdentity
GCD --determines--> Coprimality
GCD --relates_to--> LeastCommonMultiple
GCD --supports--> ModularArithmetic
GCD --supports--> FractionSimplification
GCD --supports--> DiophantineEquationSolvability

7. INFERENCE RULES
R1: d=gcd(a,b) => d|a AND d|b.
R2: c|a AND c|b => c|gcd(a,b).
R3: gcd(a,b)=1 => a,b are coprime.
R4: gcd(a,b)=d => EXISTS x,y IN Z: ax+by=d.
R5: ax+by=c has an integer solution IFF gcd(a,b)|c, for (a,b)!=(0,0).
R6: gcd(a,m)=1 => a has a multiplicative inverse modulo m, m>=2.
R7: gcd(a,b)=g AND a,b!=0 => lcm(a,b)=|ab|/g.

8. WORKED EXAMPLES
EXAMPLE A: gcd(48,18)
48=2*18+12; 18=1*12+6; 12=2*6+0; result=6.
Bézout: 48*(-1)+18*3=6.
EXAMPLE B: gcd(-21,14)=7.
EXAMPLE C: gcd(35,64)=1 => coprime.
EXAMPLE D: gcd(0,9)=9.

9. VALIDATION
V1: Reject gcd(0,0) under the declared domain policy.
V2: Output g must be a positive integer.
V3: Assert a mod g=0 AND b mod g=0.
V4: Verify Bézout witness ax+by=g.
V5: For finite test ranges compare Euclid output with divisor enumeration.
V6: Verify symmetry, sign invariance and Euclidean reduction.
V7: For nonzero a,b verify gcd(a,b)*lcm(a,b)=|a*b|.
V8: Reject modular-inverse inference when modulus <2.

10. SEMANTIC_EQUIVALENCE
"greatest common divisor" <=> "greatest common factor" <=> "highest common factor" (integer-number-theory context).
"gcd(a,b)=1" <=> "a and b are relatively prime" <=> "a and b are coprime".
Equivalence is contextual; do not conflate GCD with LCM or general divisibility.

11. CONFIDENCE
Formal definitions and listed standard theorems: HIGH, conditional on stated domains.
Worked arithmetic examples: HIGH, directly checkable.
Alignment to source webpage wording: UNVERIFIED.
Do not treat confidence as proof; validation obligations remain mandatory.

12. FLOW_HASH
canonicalise: UTF-8; LF newlines; stable field ordering; preserve formula and domain semantics.
algorithm: SHA-256
value: COMPUTE_ON_PUBLISH (not fabricated)

13. UPDATE_MODEL
trigger: source-page revision | ontology-schema revision | mathematical correction
procedure: compare semantic definitions; update dependent inference rules; rerun V1-V8; increment version; regenerate FLOW_HASH; retain provenance and changelog.

14. AI_CONSUMPTION
entity_id: discrete-mathematics.number-theory.greatest-common-divisor
machine_tasks: concept retrieval | symbolic reasoning | arithmetic verification | proof support | dependency mapping
input_contract: two integers not both zero
output_contract: positive gcd, optional Bézout witness and proof trace
safety: preserve assumptions; report undefined cases; do not infer unproved claims
provenance: SOURCE_URL above; mathematical synthesis not a verified transcription

END FLOW ALGEBRA