Number Theory

Overview

Number theory studies the arithmetic structure of integers, including divisibility, prime decomposition, and congruences. It underpins modern cryptography, coding theory, and algorithm design, and it is also central to practical tasks such as key generation, residue checks, and factor-based diagnostics in data workflows. In spreadsheet analytics, these tools make advanced integer methods accessible without custom scripting while preserving mathematically rigorous behavior. For a broad reference, see Number theory on Wikipedia.

The core ideas across this category are factorization, arithmetic functions, and modular structure. Divisor-based functions summarize integer composition, totient-style functions measure multiplicative structure, and modular operators determine orders, roots, and solvability of congruences. Many workflows combine these concepts, such as using prime factors to compute arithmetic invariants, then applying congruence tests to validate modular constraints. A recurring identity is Euler’s theorem, a^{\varphi(n)} \equiv 1 \pmod n for \gcd(a,n)=1, which links factorization and residue arithmetic.

Implementation is primarily powered by SymPy number theory, with selected helper functions from primePy and the Python standard library math module. SymPy provides robust symbolic and algorithmic routines for divisors, primality, factorization, and modular equations, while primePy contributes lightweight prime-listing and totient utilities. The result is a practical bridge between spreadsheet interfaces and production-grade Python math libraries.

The divisor and integer-arithmetic group supports structural analysis of single integers and sets of integers. GCD, LCM, and ISQRT handle foundational arithmetic operations used in normalization, period alignment, and bounds reasoning. DIVISORS, PROPDIVS, DIVCOUNT, and PROPDIVCNT enumerate or count divisor sets for classification and feature engineering. TOTIENT, PPY_PHI, and REDUCEDTOT measure multiplicative-group properties that are useful in cycle-length analysis, coprime counting, and modular-system design.

The modular arithmetic group focuses on congruence solvability and multiplicative behavior modulo n. DLOG solves discrete logarithms, while NORDER, ISPRIMROOT, and PRIMROOT characterize generators and cyclic structure of unit groups. Residue classification and symbol computations are handled by ISQUADRES, QUADRES, LEGENDRE, and JACOBI, supporting quadratic reciprocity workflows and fast solvability checks. Equation solvers SQRTMOD, NTHROOTMOD, and QUADCONG provide direct solutions to modular root and quadratic congruence problems used in cryptographic prototyping and residue-based constraint systems.

The prime-focused group provides primality testing, prime generation, and factor decomposition utilities for search, validation, and decomposition tasks. ISPRIME, PRIME, NEXTPRIME, and PREVPRIME support point queries and sequential prime navigation. Range and counting workflows are covered by PRIMERANGE, PPY_PRIMEUPTO, PPY_PRIMEBETWEEN, and PRIMEPI, while RANDPRIME provides randomized prime sampling in bounded intervals. For decomposition and derived structure, FACTORINT returns full prime powers and PRIMEFACTORS returns distinct prime factors, and PPY_PRIMECHECK provides an alternate primality check path.

Gcd Lcm Divisors

Tool	Description
DIVCOUNT	Count divisors of an integer with optional modulus filtering.
DIVISORS	List divisors of an integer with optional proper divisor mode.
GCD	Compute the greatest common divisor of one or more integers.
ISQRT	Compute the integer square root of a nonnegative integer.
LCM	Compute the least common multiple of one or more integers.
PPY_PHI	Compute Euler’s totient function using the primePy implementation.
PROPDIVCNT	Count proper divisors of an integer with optional modulus filtering.
PROPDIVS	List proper divisors of an integer.
REDUCEDTOT	Compute Carmichael’s reduced totient function for an integer.
TOTIENT	Compute Euler’s totient function for an integer.

Modular Arithmetic

Tool	Description
DLOG	Solve discrete logarithms in modular arithmetic.
ISPRIMROOT	Check whether a value is a primitive root modulo n.
ISQUADRES	Check whether a value is a quadratic residue modulo p.
JACOBI	Compute the Jacobi symbol for two integers.
LEGENDRE	Compute the Legendre symbol modulo an odd prime.
NORDER	Find the multiplicative order of an integer modulo n.
NTHROOTMOD	Solve nth-power congruences modulo an integer.
PRIMROOT	Find a primitive root modulo n when one exists.
QUADCONG	Solve quadratic congruences modulo n.
QUADRES	List all quadratic residues modulo p.
SQRTMOD	Solve quadratic congruences of the form x squared congruent to a.

Prime Numbers

Tool	Description
FACTORINT	Compute the prime factorization of an integer with multiplicities.
ISPRIME	Determine whether an integer is prime.
NEXTPRIME	Return the ith prime number greater than a given integer.
PPY_PRIMEBETWEEN	List prime numbers between two bounds using primePy.
PPY_PRIMECHECK	Check primality using the primePy implementation.
PPY_PRIMEUPTO	List all prime numbers up to a maximum value using primePy.
PREVPRIME	Return the largest prime smaller than a given integer.
PRIME	Return the nth prime number.
PRIMEFACTORS	Return distinct prime factors of an integer.
PRIMEPI	Count the number of primes less than or equal to an integer.
PRIMERANGE	Generate all prime numbers in a specified interval.
RANDPRIME	Sample a prime number from a half-open integer interval.