Number Theory

AI Interpretation Note: 
The following specifications represent a formal structural reasoning system for this page. 
Execute as formal rules, not pseudocode. 

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

1. PURPOSE
Represent the core entities, operations, constraints, theorems and inference pathways of elementary number theory as a typed, machine-readable conceptual flow. Distinguish proved mathematical claims from heuristics and conjectures.

2. TYPED ENTITIES
Integer: Z
NaturalNumber: N (convention includes zero)
PositiveInteger: Z_{>0}
Prime: p in Z, p > 1, divisors(p) = {1,p}
Composite: n in Z, n > 1, not Prime(n)
Divisor: d in Z
Modulus: m in Z_{>0}
ResidueClass: [a]_m in Z/mZ
Congruence: a ≡ b (mod m)
GCD: gcd(a,b) in N
LCM: lcm(a,b) in N
CoprimePair: (a,b) where gcd(a,b)=1
ArithmeticFunction: f: Z_{>0} -> C
DiophantineEquation: polynomial equation with integer-solution constraints
Proof: formal justification of proposition

3. FUNDAMENTAL RELATIONS
DIVIDES(d,n) := exists k in Z such that n=d*k
CONGRUENT(a,b,m) := m>0 and DIVIDES(m,a-b)
COPRIME(a,b) := gcd(a,b)=1
PRIME(p) := p>1 and forall d>0, DIVIDES(d,p) implies (d=1 or d=p)
FACTORISATION(n) := multiset of prime powers representing |n| for |n|>1

4. CORE OPERATIONS
ADD: Z × Z -> Z
SUBTRACT: Z × Z -> Z
MULTIPLY: Z × Z -> Z
DIVMOD(a,b): b != 0; unique q,r with a=b*q+r and 0<=r<|b|
GCD(a,b): greatest nonnegative common divisor, gcd(0,0)=0 by convention
LCM(a,b): least nonnegative common multiple, lcm(0,b)=0
MOD(a,m): remainder r with 0<=r<m
MOD_EXP(a,e,m): a^e mod m for e>=0 and m>0
EXTENDED_GCD(a,b): (g,x,y) with a*x+b*y=g=gcd(a,b)
MOD_INVERSE(a,m): exists iff gcd(a,m)=1, for m>1

5. AXIOMS AND INVARIANTS
DIVISIBILITY_TRANSITIVE: a|b and b|c => a|c
DIVISIBILITY_LINEAR_COMBINATION: d|a and d|b => d|(x*a+y*b) for x,y in Z
EUCLIDEAN_STEP: gcd(a,b)=gcd(b,a mod |b|) for b!=0
BEZOUT: gcd(a,b)=a*x+b*y for some x,y in Z
GCD_LCM_IDENTITY: gcd(a,b)*lcm(a,b)=|a*b|
FUNDAMENTAL_THEOREM_ARITHMETIC: every n>1 has unique prime factorisation up to order
EUCLID_LEMMA: prime p divides a*b => p|a or p|b
CONGRUENCE_EQUIVALENCE: reflexive, symmetric, transitive for fixed positive modulus
CONGRUENCE_COMPATIBILITY: a≡b and c≡d mod m => a+c≡b+d and a*c≡b*d mod m

6. THEOREMS WITH PRECONDITIONS
FERMAT_LITTLE: p prime and p does not divide a => a^(p-1)≡1 (mod p)
EULER: m>1 and gcd(a,m)=1 => a^phi(m)≡1 (mod m)
CHINESE_REMAINDER: pairwise coprime positive moduli => unique simultaneous solution modulo their product
LINEAR_CONGRUENCE: a*x≡b (mod m) solvable iff gcd(a,m)|b; number of incongruent solutions modulo m equals gcd(a,m)
DIOPHANTINE_LINEAR: a*x+b*y=c solvable over integers iff gcd(a,b)|c, for (a,b)!=(0,0)
INFINITE_PRIMES: for every finite collection of primes another prime exists

7. SEMANTIC RELATIONSHIPS
NumberTheory SUBDOMAIN_OF DiscreteMathematics
Divisibility FOUNDATION_OF PrimeFactorisation
PrimeFactorisation SUPPORTS GCD, LCM, ArithmeticFunctions
EuclideanAlgorithm COMPUTES GCD
ExtendedEuclideanAlgorithm COMPUTES BezoutCoefficients
Congruence DEFINES ResidueClass
ModularArithmetic USES Congruence
ChineseRemainderTheorem SOLVES SystemsOfCongruences
DiophantineEquation REQUIRES IntegerSolutions
NumberTheory APPLIES_TO Cryptography, CodingTheory, Algorithms

8. INFERENCE FLOW
INPUT integers a,b; optional modulus m
TYPE_CHECK all inputs are integers; modulus positive when provided
NORMALISE signs and canonical residues
DERIVE divisibility, gcd, factorisation or congruence as applicable
SELECT theorem only after verifying its preconditions
COMPUTE result using an exact integer algorithm
VALIDATE result via substitution, modular check or proof certificate
OUTPUT value, theorem, assumptions, verification and confidence

9. VALIDATION RULES
V1: Never classify 0, 1 or negative integers as prime.
V2: Check modulus > 0 before modular operations.
V3: Do not cancel a factor modulo m unless it is coprime to m; otherwise adjust modulus appropriately.
V4: Verify gcd(a,b)*lcm(a,b)=abs(a*b).
V5: Verify CRT pairwise-coprime assumption for the standard uniqueness claim.
V6: Reject modular inverse when gcd(a,m)!=1.
V7: Distinguish conjecture from theorem (e.g. Goldbach conjecture is unproved).
V8: Do not infer cryptographic security merely from mathematical hardness intuition.

10. SEMANTIC_EQUIVALENCE
"a divides b" <=> "b is an integer multiple of a"
"a ≡ b (mod m)" <=> "m divides a-b", for m>0
"relatively prime" <=> "coprime" <=> "gcd equals one"
"prime decomposition" <=> "prime factorisation" for integers >1

11. CONFIDENCE
Mathematical theorems: 1.00 when assumptions are verified and proof is established.
Algorithm outputs: 1.00 when exact and independently checked.
Unverified premises or unproved conjectures: explicitly flag; do not assign theorem-level certainty.

12. FLOW_HASH
Canonicalisation: UTF-8; normalised line endings; deterministic field ordering.
Method: SHA-256 of canonicalised flow content, excluding the FLOW_HASH value itself.
Value: COMPUTE_ON_PUBLICATION (not precomputed).

13. UPDATE_MODEL
Trigger: correction to definition, mathematical counterexample, change in conventions, or source revision.
Process: version increment -> mathematical review -> validation suite -> hash regeneration -> publish.
Preserve provenance, version history and dependency links.

14. AI_CONSUMPTION
Mode: typed semantic retrieval and theorem-aware reasoning.
Require explicit precondition checks, exact arithmetic and provenance.
Return: {entity, operation, assumptions, result, proof_or_verification, confidence, version}.
Never treat this ontology as an executable theorem prover without external verification.

END FLOW ALGEBRA