# Number-Theory Lab

> Primality, factorisation, gcd, modular arithmetic, CRT, φ, π(n), Collatz, continued fractions. Big-integer number theory with the working shown: Miller–Rabin primality (deterministic up to 3.3·10^24, otherwise with a stated number of rounds), factorisation by trial division and Pollard rho, gcd/lcm with the extended Euclidean table, modular inverse and exponentiation, the Chinese remainder theorem, Euler φ and divisors, prime counting up to 10 million, Collatz sequences and continued fractions.

Part of usefulweb.site (https://usefulweb.site/). Results are deterministic calculations from the inputs and the listed assumptions; the API returns exactly what the web page shows.

## Use it
- Human interface: https://numbertheorylab.usefulweb.site/ (interactive tool at https://numbertheorylab.usefulweb.site/tool)
- JSON API: POST https://numbertheorylab.usefulweb.site/api/v1/calculate with a JSON object of inputs (schema: https://numbertheorylab.usefulweb.site/api/v1/tool)
- OpenAPI: https://numbertheorylab.usefulweb.site/openapi.json
- MCP (Streamable HTTP): https://numbertheorylab.usefulweb.site/mcp - tool `number_theory_lab`

## Inputs
- operation (select): Operation
- a (text): n or a - Integer: decimal, 0x hex, 0b binary, or a power such as 2^127-1.
- b (text): b (second number / exponent / denominator)
- m (text): Modulus m
- congruences (textarea): Congruences (one per line: remainder modulus) - For the CRT: each line "a m" means x ≡ a (mod m). Moduli need not be coprime.
- rounds (integer): Miller–Rabin rounds above 3.3·10^24 - Error probability at most 4^−rounds for numbers beyond the deterministic range.

## Method
- Primality: trial division by primes below 100, then Miller–Rabin. Below 3,317,044,064,679,887,385,961,981 the first 13 primes as bases form a proof (Sorenson & Webster 2015), which covers every 64-bit number. Above it, the stated number of rounds uses bases derived from SHA-256 of n (reproducible); a composite passes each round with probability at most 1/4.
- Factorisation: trial division up to 10,000, then Pollard–Brent rho with a fixed iteration budget; factors are checked with Miller–Rabin. If the budget runs out the remaining cofactor is reported as unfactored, never guessed.
- φ(n) = ∏ p^(e−1)(p − 1), σ(n) = ∏ (p^(e+1) − 1)/(p − 1), d(n) = ∏ (e + 1). Carmichael numbers are detected with Korselt's criterion (square-free, composite, p − 1 | n − 1 for every prime factor).
- gcd via the Euclidean algorithm with Bézout coefficients; inverse exists iff gcd(a, m) = 1. CRT merges congruences pairwise and also handles non-coprime moduli (or reports that none exists). π(n) uses an odd-only sieve of Eratosthenes.