Modular Arithmetic Ontology

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

1. PURPOSE
Represent integer congruence, residue classes and arithmetic modulo a positive integer as typed, verifiable semantic operations.

2. TYPED ENTITIES
Integer := Z
Modulus := {n in Z | n > 0}
Residue(n) := {0,1,...,n-1}
Congruence(a,b,n) := Boolean, where a,b in Z and n in Modulus
ResidueClass(a,n) := {x in Z | x congruent a (mod n)}
QuotientRing(n) := Z/nZ
Unit(n) := residue class [a] with gcd(a,n)=1
ModularInverse(a,n) := residue [b] satisfying ab congruent 1 (mod n), if it exists

3. CORE DEFINITIONS
CONGRUENT(a,b,n) := (n divides (a-b))
NORMALISE(a,n) := unique r in Residue(n) with CONGRUENT(a,r,n)
ADD_MOD(a,b,n) := NORMALISE(a+b,n)
SUB_MOD(a,b,n) := NORMALISE(a-b,n)
MUL_MOD(a,b,n) := NORMALISE(a*b,n)
POW_MOD(a,k,n) := NORMALISE(a^k,n), k >= 0
INVERSE_MOD(a,n) := b if gcd(a,n)=1 and MUL_MOD(a,b,n)=1 mod n; otherwise UNDEFINED
DIV_MOD(a,b,n) := MUL_MOD(a,INVERSE_MOD(b,n),n) only if gcd(b,n)=1

4. FORMAL LAWS
REFLEXIVE: a congruent a (mod n)
SYMMETRIC: a congruent b => b congruent a (mod n)
TRANSITIVE: a congruent b and b congruent c => a congruent c (mod n)
ADDITION: a congruent b and c congruent d => a+c congruent b+d (mod n)
MULTIPLICATION: a congruent b and c congruent d => ac congruent bd (mod n)
POWERS: a congruent b => a^k congruent b^k (mod n), k>=0
DISTRIBUTIVITY: a(b+c) congruent ab+ac (mod n)
ADDITIVE_IDENTITY: a+0 congruent a (mod n)
MULTIPLICATIVE_IDENTITY: a*1 congruent a (mod n)
ADDITIVE_INVERSE: a+(-a) congruent 0 (mod n)
CANCELLATION: ac congruent bc (mod n) implies a congruent b (mod n) only if gcd(c,n)=1

5. SEMANTIC RELATIONSHIPS
ModularArithmetic IS_A NumberTheoryConcept
Congruence IS_A EquivalenceRelation
Congruence PARTITIONS Integers INTO ResidueClasses
ResidueClass ELEMENT_OF QuotientRing
QuotientRing HAS_OPERATIONS ModularAddition, ModularMultiplication
ModularInverse EXISTS_IF Coprime(operand,modulus)
ChineseRemainderTheorem RELATES SystemsOfCongruences
EuclideanAlgorithm COMPUTES GreatestCommonDivisor
ExtendedEuclideanAlgorithm COMPUTES ModularInverse WHEN Coprime

6. INFERENCE RULES
R1: n>0 and n|(a-b) -> CONGRUENT(a,b,n)
R2: CONGRUENT(a,b,n) -> NORMALISE(a,n)=NORMALISE(b,n)
R3: gcd(a,n)=1 -> INVERSE_MOD(a,n) is defined
R4: gcd(a,n)>1 -> INVERSE_MOD(a,n) is undefined
R5: ax congruent b (mod n), d=gcd(a,n) -> solvable iff d|b; when solvable, exactly d distinct solutions modulo n
R6: Pairwise coprime positive moduli -> Chinese remainder system has a unique solution modulo their product

7. EXECUTABLE VALIDATION CASES
CASE_01: NORMALISE(-3,7)=4 -> PASS
CASE_02: CONGRUENT(17,5,12)=true -> PASS
CASE_03: ADD_MOD(8,9,7)=3 -> PASS
CASE_04: MUL_MOD(4,5,7)=6 -> PASS
CASE_05: POW_MOD(3,4,5)=1 -> PASS
CASE_06: INVERSE_MOD(3,7)=5 -> PASS
CASE_07: INVERSE_MOD(2,6)=UNDEFINED -> PASS
CASE_08: DIV_MOD(4,2,6)=UNDEFINED (division by nonunit) -> PASS
CASE_09: 2*x congruent 4 (mod 6) -> x in {2,5} modulo 6 -> PASS

8. CONSTRAINTS AND EDGE CASES
Modulus must be strictly positive; n=1 is valid and gives the zero ring with one residue class.
Modulo is not ordinary division; division requires an invertible divisor.
Negative operands must be normalised to canonical nonnegative residues.
Do not infer cancellability without checking coprimality.
Avoid assuming every nonzero residue is a unit for composite moduli.
Fermat's little theorem requires prime modulus and a nondivisible base for the a^(p-1) formulation.
Euler's theorem requires gcd(a,n)=1.

9. SEMANTIC_EQUIVALENCE
'a = b mod n' EQUIVALENT_TO 'n divides (a-b)' when '=' denotes congruence.
'a mod n' EQUIVALENT_TO NORMALISE(a,n) under canonical residue convention.
'Z/nZ' EQUIVALENT_TO quotient ring of integers by nZ.
'Invertible residue' EQUIVALENT_TO 'residue coprime to modulus'.
Do not equate integer equality with congruence.

10. CONFIDENCE
MATHEMATICAL_DEFINITIONS: 1.00 (standard definitions)
FORMAL_LAWS: 1.00 (subject to stated preconditions)
PAGE_ALIGNMENT: UNVERIFIED (live source not inspected)
CONFIDENCE_POLICY: Distinguish theorem certainty from confidence about webpage-specific coverage.

11. FLOW_HASH
ALGORITHM: SHA-256
INPUT: canonical UTF-8 representation of this flow excluding any stored hash value
VALUE: COMPUTE_ON_INGEST (not fabricated)

12. UPDATE_MODEL
TRIGGER: change to definitions, proofs, domain constraints, examples or source-page content
PROCESS: version_increment -> validate_types -> verify_inference_rules -> execute_test_cases -> regenerate_FLOW_HASH -> publish
PROVENANCE: preserve source URL, revision timestamp and author attribution

13. AI_CONSUMPTION
INPUT: integer operands, positive modulus, requested operation
PIPELINE: parse -> type_check -> normalise -> apply_rule -> verify_preconditions -> calculate -> validate -> explain
OUTPUT: result, canonical residue, proof/witness, confidence, relevant constraints
FAILURE: explicit error for invalid modulus or undefined inverse/division; never silently approximate
INTEROPERABILITY: Set Theory, Equivalence Relations, Rings, Divisibility, GCD, Prime Numbers, Cryptography

END FLOW ALGEBRA