Congruence Ontology

FLOW ALGEBRA
CONGRUENCE ONTOLOGY — DISCRETE MATHEMATICS / NUMBER THEORY
Version: 1.0
Source URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/number-theory/congruence-ontology.html
Authors: Mark Higgins — Sky (Recursive AI)
Site: https://kirethresearch.org
Scope: Mathematical model based on established number theory; source page not independently verified.

1. ONTOLOGY IDENTITY
ontology_id: discrete_math.number_theory.congruence
concept: Congruence modulo a positive integer
notation: a ≡ b (mod n)
context: integers a,b and modulus n ∈ Z_{>0}
meaning: n divides (a-b)

2. TYPED ENTITIES
Integer := Z
Modulus := {n ∈ Z | n > 0}
ResidueClass(n) := Z/nZ
Congruence(a:Integer,b:Integer,n:Modulus) := Boolean
Remainder(a:Integer,n:Modulus) := Integer in [0,n-1]
UnitResidue(n) := {[a] ∈ Z/nZ | gcd(a,n)=1}

3. DEFINITIONS AND OPERATORS
CONGRUENT(a,b,n) := EXISTS k ∈ Z: a-b = k*n
RESIDUE(a,n) := a mod n (canonical nonnegative remainder)
CLASS(a,n) := {a+k*n | k ∈ Z}
ADD_CLASS([a],[b]) := [a+b]
MUL_CLASS([a],[b]) := [a*b]
NEG_CLASS([a]) := [-a]
MOD_INVERSE(a,n) := x in [0,n-1] with a*x ≡ 1 (mod n), when gcd(a,n)=1

4. FORMAL AXIOMS AND LAWS
REFLEXIVE: a ≡ a (mod n)
SYMMETRIC: a ≡ b (mod n) => b ≡ a (mod n)
TRANSITIVE: a ≡ b (mod n) AND b ≡ c (mod n) => a ≡ c (mod n)
ADDITION: a ≡ b (mod n) AND c ≡ d (mod n) => a+c ≡ b+d (mod n)
MULTIPLICATION: a ≡ b (mod n) AND c ≡ d (mod n) => ac ≡ bd (mod n)
POWERS: a ≡ b (mod n) => a^k ≡ b^k (mod n), k ∈ Z_{>=0}
EQUIVALENCE_CLASS: a ≡ b (mod n) iff CLASS(a,n)=CLASS(b,n)
MODULUS_DIVISOR: m|n AND a ≡ b (mod n) => a ≡ b (mod m), m>0
CANCELLATION: ac ≡ bc (mod n) => a ≡ b (mod n/gcd(c,n)), c != 0
STRONG_CANCELLATION: gcd(c,n)=1 AND ac ≡ bc (mod n) => a ≡ b (mod n)

5. INFERENCE RULES
R1: DIVIDES(n,a-b) -> CONGRUENT(a,b,n)
R2: CONGRUENT(a,b,n) -> RESIDUE(a,n)=RESIDUE(b,n)
R3: CONGRUENT(a,b,n) -> CONGRUENT(a+t,b+t,n)
R4: CONGRUENT(a,b,n) -> CONGRUENT(a*t,b*t,n)
R5: gcd(a,n)=1 -> EXISTS unique x in [0,n-1]: ax ≡ 1 (mod n)
R6: ax ≡ b (mod n) has a solution iff gcd(a,n) divides b; when solvable, exactly gcd(a,n) distinct residue solutions modulo n
R7: For pairwise coprime positive moduli n_i, simultaneous congruences x ≡ a_i (mod n_i) have a unique solution modulo product(n_i)

6. RELATIONSHIPS
Congruence IS_A EquivalenceRelation on Integer for fixed positive modulus
Congruence DEFINES ResidueClass
ResidueClass MEMBER_OF QuotientRing(Z/nZ)
ModularArithmetic USES Congruence
Divisibility DEFINES Congruence
GreatestCommonDivisor DETERMINES ModularInvertibility
ChineseRemainderTheorem COMBINES CongruenceSystems

7. EXECUTION MODEL
flow "CongruenceReasoning" v1.0
input: a:Integer, b:Integer, n:Integer
precondition: n > 0
steps:
  - delta := a-b
  - congruent := (delta mod n == 0)
  - residue_a := a mod n
  - residue_b := b mod n
  - class_equal := (residue_a == residue_b)
  - assert congruent == class_equal
output: {congruent, residue_a, residue_b, modulus:n}

8. VALIDATION AND EDGE CASES
V1: n=0 or n<0 -> reject under positive-modulus convention
V2: a=-7,b=5,n=12 -> true (difference=-12)
V3: a=14,b=2,n=6 -> true (difference=12)
V4: a=7,b=2,n=4 -> false (difference=5)
V5: modulus n=1 -> all integers congruent
V6: zero-divisor cancellation without coprimality is not generally valid
V7: never infer integer equality from congruence alone
V8: negative inputs use canonical residues 0..n-1

9. SEMANTIC_EQUIVALENCE
"a is congruent to b modulo n" <=> "n divides a-b"
"a and b have the same remainder modulo n" <=> "a ≡ b (mod n)" for n>0
"[a]_n=[b]_n" <=> "a ≡ b (mod n)"
NOT_EQUIVALENT: congruence modulo n versus numerical equality
NOT_EQUIVALENT: modular inverse versus ordinary multiplicative inverse

10. CONFIDENCE
formal_definitions: 1.00 (conditional on stated integer domain and positive modulus)
proved_algebraic_laws: 1.00 (under stated preconditions)
source_page_alignment: unverified
confidence_policy: distinguish mathematical certainty from page-content verification

11. FLOW_HASH
hash_algorithm: SHA-256
hash_scope: canonical UTF-8 content excluding computed hash field
hash_value: COMPUTE_AT_INGESTION
hash_purpose: integrity, deduplication, version tracking

12. UPDATE_MODEL
version: 1.0
change_policy: preserve stable ontology_id; increment version on substantive changes
review_triggers: corrected proofs, notation, domain restrictions, algorithmic updates
provenance: authored mathematical synthesis; source page unverified

13. AI_CONSUMPTION
primary_intent: recognise, evaluate and reason about modular congruences
input_types: Integer, Integer, PositiveInteger
output_types: Boolean, ResidueClass, Explanation, ProofTrace
required_checks: modulus positivity, divisibility, gcd prerequisites, quantifier scope
retrieval_terms: congruence; modular equivalence; residue class; modulo; quotient ring
explainability: retain divisibility witness k where a-b=k*n
safety: reject invalid cancellation and unsupported inferences

END FLOW ALGEBRA