Fermat's Little Theorem Ontology

FLOW ALGEBRA
TITLE: Fermat's Little Theorem Ontology
DOMAIN: Discrete Mathematics / Number Theory
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/number-theory/fermats-little-theorem-ontology.html
VERSION: 1.0
LANGUAGE: en-GB
AUTHORS: Mark Higgins — Sky (Recursive AI)
SOURCE_STATUS: Formal mathematical synthesis; live page not independently verified.

1. ONTOLOGY
ontology FermatsLittleTheorem {
  parent: NumberTheoryOntology
  concepts: [Prime, Integer, Coprime, Congruence, ModularExponentiation,
             MultiplicativeGroupModuloPrime, ModularInverse, EulerTotient]
  theorem: "For prime p and integer a, a^p ≡ a (mod p)."
  equivalent_coprime_form: "For prime p and p ∤ a, a^(p-1) ≡ 1 (mod p)."
}

2. TYPED ENTITIES
entity Integer { value: Z }
entity Prime { value: Z; constraint: value > 1 and prime(value) }
entity Residue { value: Z; modulus: Prime }
entity Congruence { lhs: Integer; rhs: Integer; modulus: Prime }
entity TheoremApplication { base: Integer; modulus: Prime; conclusion: Congruence }
entity ProofCertificate { premises: List[Statement]; conclusion: Statement; rule: String }

3. RELATIONSHIPS
Prime(p) -> establishes_modulus -> Z_mod_p
Coprime(a,p) -> enables -> ReducedExponentForm
FermatsLittleTheorem -> generalises_to -> EulerTheorem
ModularExponentiation -> evaluated_under -> Congruence
NonzeroResidueModuloPrime -> member_of -> MultiplicativeGroupModuloPrime

4. FORMAL RULES
rule FLT_GENERAL:
  pre: prime(p) and integer(a)
  infer: mod(pow(a,p),p) == mod(a,p)

rule FLT_COPRIME:
  pre: prime(p) and integer(a) and gcd(a,p) == 1
  infer: mod(pow(a,p-1),p) == 1

rule EXPONENT_REDUCTION:
  pre: prime(p) and gcd(a,p) == 1 and n >= 0
  infer: mod(pow(a,n),p) == mod(pow(a,n mod (p-1)),p)

rule MODULAR_INVERSE:
  pre: prime(p) and gcd(a,p) == 1
  infer: inverse_mod(a,p) == mod(pow(a,p-2),p)

rule COMPOSITE_WITNESS:
  pre: n > 1 and integer(a) and mod(pow(a,n),n) != mod(a,n)
  infer: not prime(n)
  note: Passing a Fermat congruence is not proof of primality.

5. ALGEBRAIC IDENTITIES
forall prime p, forall a in Z: a^p ≡ a (mod p)
forall prime p, forall a with p ∤ a: a^(p-1) ≡ 1 (mod p)
forall prime p, forall a with p ∤ a: a^(-1) ≡ a^(p-2) (mod p)
phi(p) = p-1 for prime p

6. PROOF FLOW
flow ProveFLT(a: Integer, p: Prime) -> Congruence:
  assert prime(p)
  if mod(a,p) == 0:
    return congruence(pow(a,p), a, p)
  else:
    residues := {1,2,...,p-1}
    multiplied := {mod(a*r,p) for r in residues}
    assert multiplied == residues  # permutation because gcd(a,p)=1
    infer pow(a,p-1) ≡ 1 (mod p) by cancellation
    return pow(a,p) ≡ a (mod p)

7. EXAMPLES
example 1: p=7, a=3; 3^6=729 ≡ 1 (mod 7)
example 2: p=5, a=10; 10^5 ≡ 10 ≡ 0 (mod 5)
example 3: n=341=11*31, a=2; 2^340 ≡ 1 (mod 341), but 341 is composite.

8. INFERENCE AND VALIDATION
validate prime(p) before applying FLT.
validate gcd(a,p)=1 before reducing exponent modulo p-1.
validate p>2 before interpreting a^(p-2) as a nonnegative modular power for inverse computation; p=2 is valid with exponent zero.
reject inference prime(n) solely from a^(n-1) ≡ 1 (mod n).
verify computed modular powers with exact integer modular arithmetic.

9. SEMANTIC_EQUIVALENCE
"Fermat's little theorem" <=> "FLT" (context: number theory)
"a^(p-1) ≡ 1 (mod p)" <=> "nonzero residue has order dividing p-1" (prime p)
"p ∤ a" <=> "gcd(a,p)=1" (prime p)

10. CONFIDENCE
mathematical_theorem: 1.00
inference_given_verified_premises: 1.00
unverified_primality_claim: 0.00
source_page_alignment: unverified

11. FLOW_HASH
algorithm: SHA-256
canonicalisation: UTF-8; LF newlines; hash canonical content excluding FLOW_HASH digest field
value: compute_at_ingestion

12. UPDATE_MODEL
version: 1.0
trigger: theorem_revision | ontology_alignment | example_correction
preserve: source_url, authorship, mathematical_provenance
revalidate: type_constraints, theorem_premises, examples, equivalences

13. AI_CONSUMPTION
input: {a: Integer, p: Integer, requested_operation: String}
steps: [check_modulus_primality, check_coprimality_if_required,
        select_valid_rule, derive_congruence, verify_modular_result,
        emit_proof_certificate]
output: {conclusion: Congruence, premises: List[Statement],
         proof: ProofCertificate, confidence: Number}
policy: Never conflate a necessary Fermat primality condition with a sufficient one.

END FLOW ALGEBRA