Chinese Remainder Theorem Ontology

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

1. PURPOSE
Model systems of modular congruences, their compatibility, existence, uniqueness and constructive solutions, with explicitly typed mathematical entities and verifiable inference rules.

2. TYPED ENTITIES
Integer := Z
Modulus := {m in Z : m > 0}
Residue(m) := Z/mZ
Congruence := (a:Integer, m:Modulus) meaning x ≡ a (mod m)
CongruenceSystem := finite indexed sequence [(a_i,m_i)]
Solution := x:Integer satisfying every congruence
SolutionClass := equivalence class modulo lcm(m_1,...,m_k)
PairwiseCoprime := for all i != j, gcd(m_i,m_j)=1
Compatible := for all i,j, gcd(m_i,m_j) divides (a_i-a_j)

3. CORE RELATIONSHIPS
HAS_MODULUS(Congruence, Modulus)
HAS_RESIDUE(Congruence, Integer)
BELONGS_TO(Congruence, CongruenceSystem)
SATISFIES(Solution, Congruence)
EQUIVALENT_MODULO(Integer, Integer, Modulus)
IS_COPRIME_WITH(Modulus, Modulus)
IS_COMPATIBLE_WITH(Congruence, Congruence)
HAS_UNIQUE_RESIDUE_CLASS(CongruenceSystem, SolutionClass)

4. DEFINITIONS
CONGRUENT(x,a,m) := m | (x-a)
NORMALISE(a,m) := a mod m, chosen in [0,m-1]
SYSTEM_SATISFIED(x,S) := all CONGRUENT(x,a_i,m_i)
M := product_i m_i (pairwise-coprime case)
L := lcm_i m_i (general case)

5. CHINESE REMAINDER THEOREM — PAIRWISE COPRIME
PRECONDITION: k >= 1; each m_i > 0; gcd(m_i,m_j)=1 for i != j.
ASSERTION: For arbitrary residues a_i, there exists exactly one solution class modulo M = product_i m_i.
CONSTRUCT:
  M_i := M / m_i
  u_i := inverse(M_i modulo m_i)
  x := (sum_i a_i * M_i * u_i) mod M
POSTCONDITION: for each i, x ≡ a_i (mod m_i).
UNIQUENESS: if x and y satisfy S, then x ≡ y (mod M).

6. GENERALISED CHINESE REMAINDER THEOREM
PRECONDITION: all m_i > 0 (not necessarily coprime).
EXISTENCE_IFF: for every i,j, a_i ≡ a_j (mod gcd(m_i,m_j)).
WHEN_COMPATIBLE: one unique solution class exists modulo L = lcm_i m_i.
WHEN_INCOMPATIBLE: no integer satisfies the complete system.

7. TWO-CONGRUENCE MERGE
INPUT: x ≡ a (mod m), x ≡ b (mod n); m,n > 0.
LET: g := gcd(m,n).
IF (b-a) mod g != 0: return INCONSISTENT.
ELSE:
  Solve (m/g)*t ≡ (b-a)/g (mod n/g).
  Because gcd(m/g,n/g)=1, the inverse of m/g modulo n/g exists (unless n/g=1, in which case choose t=0).
  t := ((b-a)/g) * inverse(m/g mod n/g) mod (n/g), when n/g>1.
  x := a + m*t.
  modulus := lcm(m,n).
  return NORMALISE(x,modulus), modulus.
Merge compatible congruences iteratively to solve a finite system.

8. ALGEBRAIC LAWS
CONGRUENCE_REFLEXIVITY: x ≡ x (mod m).
CONGRUENCE_SYMMETRY: x ≡ y (mod m) => y ≡ x (mod m).
CONGRUENCE_TRANSITIVITY: x ≡ y and y ≡ z (mod m) => x ≡ z (mod m).
RESIDUE_ADDITION: x ≡ a and y ≡ b (mod m) => x+y ≡ a+b (mod m).
RESIDUE_MULTIPLICATION: x ≡ a and y ≡ b (mod m) => xy ≡ ab (mod m).
MODULUS_PRODUCT: pairwise coprime => lcm_i(m_i) = product_i(m_i).
SOLUTION_PERIODICITY: x solves S iff x+tL solves S for any integer t, provided S is compatible.

9. SEMANTIC_EQUIVALENCE
"Chinese Remainder Theorem" == "CRT" (within number-theory context).
"pairwise relatively prime moduli" == "pairwise coprime moduli".
"simultaneous modular congruences" == "system of congruences" (contextual).
"unique solution modulo M" != "unique integer solution".
"pairwise coprime" != "collectively gcd equal to 1".

10. INFERENCE RULES
R1: PAIRWISE_COPRIME(S) => COMPATIBLE(S).
R2: COMPATIBLE(S) => EXISTS_SOLUTION(S).
R3: EXISTS_SOLUTION(S) => UNIQUE_CLASS_MODULO(S,L).
R4: exists i,j with gcd(m_i,m_j) not dividing (a_i-a_j) => INCONSISTENT(S).
R5: VALID_CRT_CONSTRUCTION(S,x) => SYSTEM_SATISFIED(x,S).
R6: SYSTEM_SATISFIED(x,S) and SYSTEM_SATISFIED(y,S) => L divides (x-y).

11. WORKED VALIDATION
S := [(2,3),(3,5),(2,7)].
M = 105; M_1=35, M_2=21, M_3=15.
Inverses: 35^-1 mod 3 = 2; 21^-1 mod 5 = 1; 15^-1 mod 7 = 1.
x = (2*35*2 + 3*21 + 2*15) mod 105 = 233 mod 105 = 23.
CHECK: 23 mod 3 = 2; 23 mod 5 = 3; 23 mod 7 = 2.
GENERAL_CASE: x ≡ 1 (mod 4), x ≡ 3 (mod 6) => gcd=2 divides 2; x ≡ 9 (mod 12).
INCONSISTENT_CASE: x ≡ 0 (mod 4), x ≡ 1 (mod 6) => gcd=2 does not divide 1.

12. VALIDATION
CHECK all moduli are positive integers.
CHECK each residue is normalised when a canonical form is required.
CHECK pairwise coprimality before applying product-form CRT.
CHECK pairwise compatibility for noncoprime moduli.
CHECK every output residue against every input congruence.
CHECK uniqueness only modulo the product (coprime case) or lcm (general case).
CHECK arithmetic uses arbitrary-precision integers when required.
CHECK empty-system conventions are explicitly declared by implementation.

13. CONFIDENCE
MATHEMATICAL_DEFINITIONS: 1.00 (standard definitions)
THEOREM_STATEMENTS: 1.00 (standard theorems under stated hypotheses)
EXAMPLE_VERIFICATION: 1.00 (arithmetic checked)
SOURCE_PAGE_ALIGNMENT: unverified
NOTE: Confidence values refer to formal mathematical claims, not independent verification of the linked webpage.

14. FLOW_HASH
METHOD: SHA-256 of UTF-8 bytes of canonicalised flow payload, excluding the FLOW_HASH value itself.
STATUS: compute on publication; no fabricated hash supplied.

15. UPDATE_MODEL
VERSION_POLICY: increment version for changes to definitions, rules, or examples.
ON_UPDATE: rerun congruence tests, compatibility checks and construction verification.
PROVENANCE: preserve source URL, revision date, author credit and canonical hash.

16. AI_CONSUMPTION
INPUT: typed congruence system.
PROCESS: validate -> normalise -> test coprimality/compatibility -> construct/merge -> verify.
OUTPUT: {status: SOLVED|INCONSISTENT|INVALID_INPUT, representative?: Integer, modulus?: Modulus, proof_trace: sequence, confidence: metadata}.
SAFETY: never infer solvability from coprimality of the full collection alone; require pairwise coprimality or general compatibility.

END FLOW ALGEBRA