Module number_theory 

Number theory & combinatorics (Gap analysis §3.2-NT).

Primality, factorization, modular arithmetic, the classic arithmetic functions (Euler totient, Möbius, divisor sums) and combinatorics (factorials, binomials, partitions, Stirling, Catalan). Underpins the CAS, crypto, and constructibility (the regular-polygon decision needs Fermat-prime factorization and φ(n)), and is one of the bounded, high-demand gaps the computational-engine gap analysis surfaced.

Exact integer arithmetic over u64/i64 (with u128 intermediates to avoid overflow in modular multiply); fail-closed via Option/NumberTheoryError on degenerate input. Kernel-class Divergent (branch-heavy) with a pure CPU path.

Layers (§11): modular, primes, arithmetic_functions, combinatorics.

Re-exports

pub use arithmetic_functions::divisor_count;

pub use arithmetic_functions::divisor_sum;

pub use arithmetic_functions::euler_totient;

pub use arithmetic_functions::mobius;

pub use combinatorics::binomial;

pub use combinatorics::catalan;

pub use combinatorics::factorial;

pub use combinatorics::partitions;

pub use combinatorics::stirling_first;

pub use combinatorics::stirling_second;

pub use modular::extended_gcd;

pub use modular::gcd;

pub use modular::lcm;

pub use modular::mod_inverse;

pub use modular::mod_pow;

pub use primes::divisors;

pub use primes::is_prime;

pub use primes::next_prime;

pub use primes::prime_factors;

Modules

arithmetic_functions

The classical multiplicative arithmetic functions, computed from the prime factorization: Euler’s totient φ, the Möbius function μ, divisor count d(n) and divisor sum σ(n).

combinatorics

Combinatorial functions: factorials, binomial coefficients, integer partitions, Stirling numbers (both kinds) and Catalan numbers. Exact integer results; the overflow-prone ones return Option<u128> (None past the u128 ceiling) rather than wrapping silently — fail closed.

modular

Modular arithmetic and the Euclidean algorithms — the backbone the rest of the library (primality, totient, CRT) is built on. Overflow-safe via u128/i128 intermediates.

primes

Primality and factorization. is_prime is a deterministic Miller–Rabin (the witness set {2,3,5,…,37} is proven correct for all of u64), and prime_factors uses trial division for small factors then Pollard’s rho (Brent’s variant) for the rest, so factorization is correct across the full u64 range — not just up to √n.

Enums

NumberTheoryError

Fail-closed errors for number-theoretic operations.