Number-Theoretic Properties & Tests

← Back to Domain-Specific Families

Abstractions about divisibility, primality, and related arithmetic properties of numbers and polynomials, covering primality testing (AKS test, trial division, Fermat's little theorem, probable primes), factorization-related properties (square-free integers, greatest common divisor, least common multiple), growth and density measures (average order, large sets), and related combinatorial constructs.

20 abstractions in this family — domain-specific abstractions that sit near one another in structural-signature space (k-means over structural-signature embeddings). Each is shown with its short description.

• AKS primality test — The AKS primality test (also known as the Agrawal–Kayal–Saxena primality test and the cyclotomic AKS test) is a deterministic primality-proving algorithm created and published by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, computer scientists at the Indian Institute of Technology Kanpur, on August 6, 2002, in an article titled "PRIMES is in P".
• Aliquot sum — In number theory, the aliquot sum of a positive integer is the sum of all proper divisors of , that is, all divisors of other than itself.
• Aperiodic Semigroup — A semigroup in which each element's positive powers eventually stop changing under one more multiplication by that element.
• Arithmetic–Geometric Mean — The arithmetic–geometric mean is the common limit of coupled arithmetic-mean and geometric-mean iterations on two positive numbers.
• Average Order of an Arithmetic Function — Describe an arithmetic function's aggregate growth with a simpler function whose initial-interval sums are asymptotically equivalent.
• Conference graph — In the mathematical area of graph theory, a conference graph is a strongly regular graph with parameters v, and It is the graph associated with a symmetric conference matrix, and consequently its order v must be 1 (modulo 4) and a sum of two squares.
• Congruence coefficient — In multivariate statistics, the congruence coefficient is an index of the similarity between factors that have been derived in a factor analysis.
• Coprime integers — In number theory, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1.
• Element distinctness problem — In computational complexity theory, the element distinctness problem or element uniqueness problem is the problem of determining whether all the elements of a list are distinct.
• Fermat's Little Theorem — For prime p, every integer a satisfies a^p ≡ a modulo p; nonzero residues satisfy a^(p−1) ≡ 1.
• Greatest Common Divisor — In mathematics, the greatest common divisor (GCD), also known as greatest common factor (GCF), of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers.
• Large Set (Combinatorics) — A large set of positive integers has a divergent sum of reciprocals, a criterion finer than merely being infinite or having positive density.
• Large Sieve — Bound the collective size of finite exponential sums at separated arithmetic frequencies, then use that mean-square control to limit modularly sifted sets.
• Least Common Multiple — Select the unique positive common multiple that divides every other common multiple of given positive integers.
• Prime k-tuple — A fixed finite offset set considered through common integer translates whose entries are all prime at an occurrence.
• Probable prime — Probable prime denotes number that satisfies a given necessary condition for primality within computational number theory.
• Scale factor (computer science) — In computer science, a scale factor is a number used as a multiplier to represent a number on a different scale, functioning similarly to an exponent in mathematics.
• Square-Free Integer — An integer not divisible by any perfect square greater than one, equivalently one whose prime factorization contains no repeated prime factor.
• Square-free polynomial — In mathematics, a square-free polynomial is a univariate polynomial (over a field or an integral domain) that has no multiple root in an algebraically closed field containing its coefficients.
• Trial Division — Test a complete, carrier-bounded cover of candidate divisors by exact division to find a factor or rule out reducibility.