Prime sieve 2026-10-20
A number-theoretic sieve used to enumerate prime numbers by excluding composite numbers. The sieve of Eratosthenes marks multiples of each discovered prime, beginning at its square.
Resilience of a denominator Created 2026-10-20 Updated 2026-11-05
For an integer , the resilience of a denominator is the fraction of its proper fractions already in lowest terms. The fraction is a reduced fraction exactly when and are coprime, so
where is Euler's totient function.
For , the allowed numerators are , giving . A prime denominator has resilience one. Conversely, a composite number has a proper prime divisor , and is among the listed fractions but is not reduced; thus its resilience is strictly less than one.
The prime factorization formula gives
The correction comes from sampling the positive proper numerators, rather than all residue classes. The related coresilience uses .
Semiprime 2026-10-06
A semiprime is a composite number that is a product of exactly two prime numbers, counted with multiplicity. For example, and are semiprimes. Distinct factors give for the Euler totient function, whereas equal factors give . This distinction matters when constructing a uniform coprime state for a semiprime.
Sieve of Eratosthenes 2026-10-14
The sieve of Eratosthenes finds all prime numbers at most an integer . Start with the integers marked as candidates. For each surviving candidate in increasing order, mark the multiples up to as composite numbers. Stop processing candidates once : the surviving candidates are exactly the prime numbers. Starting at saves work because any smaller proper multiple of already has a smaller prime factor. [ref].
For a complete run with , the only prime numbers at most are , since . Exclude one before starting; it is not a prime number. The four marking passes are:
  • : mark , removing 29 candidates.
  • : mark . The nine newly removed candidates are ; the even integers were already marked.
  • : mark . Only are newly removed.
  • : mark . Only is newly removed.
There are surviving prime numbers:
The next surviving candidate is , and , so no further marking pass is necessary. A prime number used for marking remains a candidate: starting at never marks itself.
Figure 1.
Four passes of the sieve of Eratosthenes through 60 leave seventeen prime numbers
. Blue cells are newly marked composite numbers; gray cells were removed earlier. White cells are candidates in the first three panels, and green cells are the final prime numbers. The outlined cell identifies the prime number used for that pass. One is excluded throughout. Details.
The saving from starting at is justified by the smaller multiplier: if with , then has a prime factor , so has already marked . For , the earlier multiples have already been marked using or . The first new possibility is .
For , only the prime numbers need marking passes. They remove all the composite numbers, leaving 25 prime numbers. The diagram colors each composite number by its smallest prime factor, so it shows which marking pass removes it first. The excluded integer one is shown separately.
Figure 2.
The sieve of Eratosthenes leaves 25 prime numbers among the integers from one to 100
. Each colored composite number is assigned to its smallest prime factor, one of . The green survivors are prime numbers; one is neither a prime number nor a composite number. Details.
Why does the algorithm work? A surviving candidate cannot be a composite number, since its smaller prime factor would already have removed it. Conversely, marking proper multiples never removes a prime number. Every composite number at most has a prime factor at most , so no later pass is needed. The sieve of Eratosthenes is useful when an entire bounded list is wanted; primality testing of one large integer is a different computational task.
The historical name is supported by a surviving primary account: Nicomachus, in Book I, chapter 13 of Introduction to Arithmetic, names Eratosthenes and describes separating prime numbers from composite numbers by marking multiples among the odd integers beginning with three. That passage documents the sieve tradition; the bounded algorithm above and its starting rule are the formulation explained here, rather than instructions quoted from Euclid's Elements. [ref]
Square-free integer Created 2026-09-24 Updated 2026-11-05
A positive integer is square-free when no square number greater than one is a divisor of . It suffices to exclude squares of prime numbers; equivalently, every prime valuation is zero or one:
Thus the prime factorization of a square-free integer is a product of distinct prime factors, with no repetitions. One is included: its prime factorization is an empty product and all its prime valuations are zero. These equivalent tests are stated in Grinberg's notes. [ref]
For signed integers, extend the definition by requiring to be a square-free integer, where denotes absolute value. Hence and both qualify. Zero does not: every prime number has its square as a divisor of zero. The Möbius function and radical of an integer below use their existing positive integer domains, so apply them to when handling a negative integer.
For example, is a square-free integer, whereas is not, because and . Being a composite number causes no problem: are all square-free integers. A square-free integer need not be coprime to another integer: and are both square-free integers but have greatest common divisor two. In fact the only signed integers coprime to every integer are , since .
Figure 1.
Exact square-free integer classification of the integers from one to sixty
. Green cells are square-free integers; each red cell displays a prime number square that divides its label, choosing the smallest such prime number. Only need testing in this range. There are green cells. This original finite arithmetic diagram is an exact enumeration, not a measurement or an assertion about a limiting frequency. Details.
For positive integers , the useful product criterion is
The proof outline is just addition of prime valuations: can stay at most one only if neither input repeats a prime factor and no prime factor occurs in both. Thus is a square-free integer, but is not. An equivalent characterization is that every factorization into positive integers has coprime factors. If , the factorization supplies two factors sharing ; conversely, a shared prime factor forces its square to divide . For , the unordered factor pairs all have greatest common divisor one; for , the pair fails.
Two existing arithmetic functions turn the definition into practical tests:
The radical of an integer keeps one copy of each prime factor, so it changes precisely the integers with a repeated prime factor. Its definition is given in Evertse's exercise sheet. [ref] The Möbius function assigns to a square-free integer with distinct prime factors and zero otherwise; squaring forgets the sign. Consequently counts exactly the green cells. This connects a restriction on repeated prime factors with weighted counting and inclusion-exclusion. [ref]
Strong induction Created 2026-09-24 Updated 2026-10-18
Strong induction establishes a proposition for all integers . Prove ; then, for each , assume every with and prove . The induction hypothesis includes all earlier cases, so the inductive step can use whichever smaller indices it needs. It cannot use itself.[ref]
This is useful when a construction breaks into smaller pieces of varying sizes. A prime factorization splits a composite number into smaller integer divisors, which need not be one less than the original integer. A recursive procedure can likewise call itself on several smaller inputs. The available cases should match those dependencies. Strong induction lets the mathematical proof follow the construction rather than forcing every step through the immediately preceding size.
Every integer has a prime factorization. The induction base case is prime. For a larger integer, either it is prime or it is , with . The induction hypothesis supplies prime factorizations of both smaller integer divisors; multiplying them gives one for . This proves existence, while uniqueness requires the additional argument under the fundamental theorem of arithmetic.[ref]
For the chosen number , one possible recursive decomposition is
The step at needs results for and , rather than a result for . Each composite number in this factorization tree splits into strictly smaller positive integers, so recursive descent terminates at prime numbers. The tree describes one construction; another choice of integer divisors can give a differently shaped factorization tree.
Figure 1.
The step for 84 can use 6 and 14: the induction hypothesis covers both
. Original factorization tree , followed by and . Arrows show recursive dependencies toward smaller integers, rather than the order of increasing induction. The strip at the bottom marks the earlier cases available at the step for , with the required and highlighted. No use of the unproved case is permitted in the hypothesis. Details.
The same pattern explains the usefulness of strong induction for algorithm correctness. When a recursive procedure returns answers for smaller inputs, the induction hypothesis can justify those answers; the remaining task is to justify how the current call combines them. Strictly decreasing a nonnegative integer size measure establishes termination. Correctness also requires each call's conditions and its combination rule; termination alone does not make an algorithm correct.
Strong pseudoprime Created 2026-09-24 Updated 2026-11-05
Let be an odd integer that is a composite number and write with odd. For a base coprime to , it is a strong pseudoprime when
These are exactly the passing outcomes of the Miller-Rabin primality test for that base. The test computes by modular exponentiation and repeatedly squares it, looking for the permitted value before reaching exponent .
Every strong pseudoprime to a base is a Fermat pseudoprime to that base, by squaring a permitted congruence sufficiently many times. The converse fails. For , one has and , . Neither tested residue is , and the first is not , so base two detects compositeness even though .
Trial division 2026-10-14
Trial division searches for divisors of an integer by testing candidate divisions. For primality testing of an integer , testing the prime numbers up to suffices: any composite number has a prime factor in that range. After finding a prime factor, repeated division removes its prime power, and testing the remaining quotient gives an elementary integer factorization method. This is useful for small inputs, but the number of candidates can grow rapidly with the input's digit count.
Von Mangoldt function Created 2026-09-24 Updated 2026-11-05
The Von Mangoldt function assigns a natural logarithm weight to each positive power of a prime number. For a positive integer ,
Here and throughout the Chebyshev functions, means the natural logarithm. In particular, : the exponent must be positive, even though the convention in prime power allows exponent zero. The support of a function of therefore consists precisely of the prime powers greater than one. [ref]
For example, and , whereas . A composite number can have a nonzero weight: has just one distinct prime factor. But has two distinct prime factors, so its weight is zero. At the weight is , not . This choice lets successive powers record successive copies of the same prime factor in the Von Mangoldt divisor identity.
The Von Mangoldt function is useful because it connects two views of the prime numbers: the prime factorization of an individual integer, through a divisor sum, and the accumulated weights below a cutoff, through the second Chebyshev function. The latter turns questions about the distribution of prime numbers into questions about a partial sum of an arithmetic function.
Wilson's theorem 2026-10-14
For an integer , Wilson's theorem characterizes prime numbers by a factorial:
The right side is an integer congruence, so the least nonnegative remainder is . For example, certifies that five is a prime number, whereas rules out six. [ref]
Figure 1.
Factorial residues distinguish primes from composites, with inverse pairs explaining the prime case
. Details.
For an odd prime number , each nonzero congruence class has a unique modular multiplicative inverse. Pair each class with its inverse: each distinct pair contributes one. A class is its own inverse exactly when ; since , Euclid's lemma leaves only . Their product is . The prime number two needs a separate check: . Conversely, a proper divisor divides both and , so the displayed integer congruence would force , a contradiction. [ref]
The composite numbers have an even sharper pattern: for every composite number , but . To check the zero claim, write with . If , both occur as different factors in the factorial. If , the different factors and both occur since , and their product is divisible by . The only excluded case is . Thus four is an exception to the zero pattern, but still fails Wilson's theorem: its required remainder would be three.
This is an exact primality testing criterion, but direct evaluation is expensive: even reducing modulo after every multiplication still takes a number of multiplications proportional to , which grows exponentially with the number of binary digits of . The problem is not merely storing a huge factorial. The more useful role of Wilson's theorem is simplifying factorial expressions in modular arithmetic. For instance, if is a prime number, then gives by a modular multiplicative inverse.