Euler Totient Ontology

FLOW ALGEBRA
TITLE: Euler Totient Ontology
DOMAIN: Discrete Mathematics / Number Theory
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/number-theory/euler-totient-ontology.html
VERSION: 1.0
AUTHORSHIP: Mark Higgins — Sky (Recursive AI)
SITE: https://kirethresearch.org
STATUS: Mathematical synthesis; live page not independently verified

1. ONTOLOGY
ontology EulerTotientOntology {
  entity Integer : Z
  entity PositiveInteger : Z_{>0}
  entity Prime : PositiveInteger
  entity PrimeFactorisation : Sequence<(Prime, PositiveInteger)>
  entity ResidueClass : Z/nZ
  entity UnitGroup : (Z/nZ)^×
  entity TotientValue : Z_{>0}
  relation divides(a:Integer,b:Integer) : Boolean
  relation coprime(a:Integer,b:Integer) : Boolean := gcd(a,b)=1
  function phi(n:PositiveInteger) : TotientValue
}

2. CORE DEFINITION
forall n >= 1:
  phi(n) = |{ k in Z : 1 <= k <= n and gcd(k,n)=1 }|
  phi(1) = 1
  phi(n) = |(Z/nZ)^×|

3. FACTORISATION AND COMPUTATION
if n = product_{i=1..r} p_i^{a_i} with distinct primes p_i and a_i >= 1:
  phi(n) = product_{i=1..r} p_i^{a_i-1}(p_i-1)
         = n * product_{p|n}(1 - 1/p)
for prime p: phi(p)=p-1
for prime p and a>=1: phi(p^a)=p^{a-1}(p-1)
for n>2: phi(n) is even

4. ALGEBRAIC LAWS
forall positive m,n:
  gcd(m,n)=1 => phi(m*n)=phi(m)*phi(n)
  phi(m*n)=phi(m)*phi(n)*gcd(m,n)/phi(gcd(m,n))
  sum_{d|n} phi(d)=n
  phi(n) <= n
  phi(n)=n-1 iff n is prime, for n>=2

5. MODULAR ARITHMETIC AND THEOREMS
Euler theorem:
  n>=1 and gcd(a,n)=1 => a^phi(n) congruent 1 (mod n)
Fermat special case:
  p prime and p does not divide a => a^(p-1) congruent 1 (mod p)
Euler theorem does not assert the same conclusion for non-coprime a.

6. SEMANTIC RELATIONSHIPS
EulerTotient --IS_A--> ArithmeticFunction
EulerTotient --COUNTS--> CoprimeResidueClasses
EulerTotient --EQUALS_CARDINALITY_OF--> UnitGroup
EulerTotient --DEPENDS_ON--> PrimeFactorisation
EulerTotient --RELATES_TO--> GreatestCommonDivisor
EulerTotient --SUPPORTS--> ModularArithmetic
EulerTotient --USED_IN--> EulerTheorem
EulerTotient --RELATED_TO--> ChineseRemainderTheorem

7. INFERENCE RULES
R1: PRIME(p) => PHI(p,p-1)
R2: PRIME(p) AND a>=1 => PHI(p^a,p^(a-1)*(p-1))
R3: COPRIME(m,n) AND PHI(m,x) AND PHI(n,y) => PHI(m*n,x*y)
R4: PHI(n,t) AND COPRIME(a,n) => MODPOW(a,t,n)=1 mod n
R5: FACTORISATION(n,[(p_i,a_i)]) => PHI(n,product(p_i^(a_i-1)*(p_i-1)))
All rule inputs must satisfy the stated integer, positivity, and primality constraints.

8. VALIDATION EXAMPLES
phi(1)=1
phi(2)=1
phi(9)=6
phi(12)=4 (coprime representatives 1,5,7,11)
phi(30)=8
sum_{d|12} phi(d)=phi(1)+phi(2)+phi(3)+phi(4)+phi(6)+phi(12)=12
For n=10,a=3: gcd(3,10)=1, phi(10)=4, 3^4 mod 10=1

9. VALIDATION MODEL
assert n >= 1
assert all prime factors are distinct primes with positive exponents
assert reconstructed_n == n
assert 1 <= phi(n) <= n
assert phi(n) == count(k for k in 1..n if gcd(k,n)==1) for bounded test n
assert phi(m*n)==phi(m)*phi(n) only under gcd(m,n)==1
assert modular exponent theorem only under gcd(a,n)==1

10. SEMANTIC_EQUIVALENCE
Euler totient function == Euler phi function == Euler's totient function
phi(n) == number of invertible residue classes modulo n
phi(n) == order of multiplicative unit group modulo n
NOT_EQUIVALENT: phi(n) != count of all residues modulo n in general

11. CONFIDENCE
mathematical_definitions: 1.00
standard_theorems: 1.00
page_specific_alignment: unverified
inference_policy: deductive; no probabilistic claims from formal laws

12. FLOW_HASH
algorithm: SHA-256
canonicalisation: UTF-8, LF line endings, normalised ontology fields
value: COMPUTE_ON_INGEST (not a fabricated digest)

13. UPDATE_MODEL
version: 1.0
change_policy: retain mathematical invariants; version changed definitions or rule sets
validation_required: true
provenance_required: true

14. AI_CONSUMPTION
input: positive integer n, optional integer a, optional prime factorisation
output: phi(n), proof or calculation trace, coprime residue interpretation
pipeline: TYPE_CHECK -> FACTORISE_OR_ENUMERATE -> APPLY_TOTIENT_RULES -> VALIDATE -> EXPLAIN
safety: do not assume factorisation or primality without evidence
explainability: preserve intermediate prime powers and products

END FLOW ALGEBRA