abc conjecture Created 2026-10-14 Updated 2026-11-05
For every , the abc conjecture asserts that there is a constant such that all coprime positive integers satisfyThe radical of an integer is the product of its distinct prime factors. The condition makes the three entries pairwise coprime. Repeated prime powers enlarge a number without enlarging its radical in the same way, so the conjecture constrains how often addition can relate unusually concentrated prime factorizations.
The example has and is an abc-hit. Such examples are compatible with the conjecture: its bound includes both the constant and the exponent . Conditional applications include the primitive Fermat bound from abc and the Catalan power bound from abc.
More generally, fix positive integers , a nonzero integer , and positive integers satisfying . Put , which divides . Applying the conjecture to the normalized positive triple formed from , and gives, for ,Indeed, the largest normalized entry is at least a fixed multiple of , while the radical is at most . Taking makes the exponent at least for , bounding uniformly; if , it also bounds . The separate case can satisfy the equation for every when .
Carmichael function Created 2026-09-24 Updated 2026-10-20
For an integer , the Carmichael function is the exponent of a finite group for the unit group : the least positive integer for whichHere the greatest common divisor condition selects the units. Euler's totient function counts them; the Carmichael function gives their least common return exponent.[ref]
Modulo eight, the units are , and their squares are all congruent to one. Their multiplicative orders are , so although . Modulo fifteen, the units have multiplicative orders . For example, the powers of two return through . Thus although ; the multiplicative order of four is only two.
The three quantities are related byA common return exponent must be a multiple of every multiplicative order, hence of their least common multiple. Conversely, that least common multiple makes every unit return to one. Lagrange's theorem makes each multiplicative order divide the group order , proving the final divisibility. The Carmichael function applies to all units at once, while the multiplicative order concerns a chosen unit.
For the prime factorization with distinct prime numbers and , the formulas areThese are least common multiples, rather than products: . The convention handles the trivial case separately.[ref]
The Chinese remainder theorem for unit groups explains the least common multiple: a power returns to one in every prime power component exactly when it is a multiple of each component's exponent of a finite group. For an odd prime power, the unit group is a cyclic group of group order . For , the unit group modulo is a direct product of groups , generated by the classes of and five, so its exponent of a finite group is .[ref]
A Computational Introduction to Number Theory and Algebra by Victor Shoup. Section 7.5, pp. 203–205, Theorem 7.28 and its proof
This gives a uniform reduction for modular exponentiation: for a unit and a nonnegative integer , reduce modulo . For example, because . The unit hypothesis matters: , but . Computing the formula assumes the prime factorization is available. The same common-exponent viewpoint explains Carmichael numbers: a composite number passes the Fermat primality test for every unit base exactly when . For example, .
Chebyshev function Created 2026-09-28 Updated 2026-11-05
The two Chebyshev functions measure the total natural logarithm weight of prime numbers or of prime powers greater than one below a real cutoff :Here ranges over prime numbers, over positive integers, and over positive integers. The Chebyshev theta function , also written , weights each prime number once. The second Chebyshev function weights every positive power of each prime number separately. Both vanish for ; the inclusive cutoff makes them right-continuous functions and nondecreasing functions, constant between their jumps. [ref]
At , the prime numbers are , while the extra prime powers greater than one are . Exactly,At each prime number , both Chebyshev functions jump by . At a prime power with , only the second Chebyshev function jumps, by . At and neither jumps. Notice that the gap is already positive at and : a shared jump does not remove the earlier contribution from .
Grouping the prime powers by their exponent gives, for ,The floor function cutoff is exact: forces whenever . For each exponent, is equivalent to . An upper cutoff smaller than the lower one means an empty sum. [ref]
Let be distinct prime numbers and positive integers. There are infinitely many positive integers with for every . Indeed the moduli are pairwise coprime, so the Chinese remainder theorem solves simultaneously. Adding multiples of their product gives arbitrarily large positive solutions. This allows long runs in which every integer has a large prescribed prime power divisor, even though neighboring integers are coprime.
Coprime-factorization lower bound for a quadratic-form class number Created 2026-09-24 Updated 2026-11-05
Let be a positive odd integer with distinct prime factors. Thenwhere is the class number of a negative discriminant.
Assign each complete prime power in the prime factorization of to one of two factors . There are ordered integer factorizations with coprime factors. Interchanging and pairs them without a fixed pair, because and coprime equal factors would both be one. Thus there are unordered pairs.
Each pair gives the primitive binary quadratic form of discriminant of a binary quadratic form . It is a reduced positive definite binary quadratic form, so distinct pairs give distinct equivalence classes under proper equivalence by uniqueness of the reduced positive definite binary quadratic form. This proves the lower bound. For the excluded case , the separate value also satisfies the weaker numerical inequality .
Coresilience Created 2026-10-20 Updated 2026-11-05
For an integer , the coresilience iswhere is Euler's totient function.[ref] It is related to the resilience of a denominator , but is not its complement:For a prime number , but , rather than zero. For the composite number fifteen, and .
As , the value is a unit fraction precisely when divides . A composite prime power with cannot qualify: its value is , already a reduced fraction with numerator greater than one. This excludes an entire family of composite numbers before a search.
Divisor-square summatory bound Created 2026-10-06 Updated 2026-11-05
For , the divisor function obeysOne proof compares it with the generalized divisor function , the number of ordered factorizations into four positive integers. At a prime power , the two counts are and . The inequality holds for every nonnegative integer , and multiplicativity gives . Hence, with the harmonic number,Applying partial summation to this upper bound also yields
Divisor sum Created 2026-09-24 Updated 2026-11-05
The divisor sum of an arithmetic function assigns to each positive integer the sumOnly positive integer divisors are included, so . The weights can count the integer divisors, measure their sizes, or record other arithmetic information: the constant-one arithmetic function gives the divisor function, whereas the identity arithmetic function gives the sum-of-divisors function.
Equivalently, , where is Dirichlet convolution and is the constant-one arithmetic function. If is a multiplicative function, then is a multiplicative function by Multiplicativity of Dirichlet convolution. [ref]
Floor and arithmetic functions by Darij Grinberg. Darij Grinberg, MIT 18.781 notes on floor and arithmetic functions, Proposition 2.4.2 and Theorem 2.6.1
Here is the mechanism. For positive coprime integers , every positive integer divisor of has a unique form with and ; moreover, are coprime integers. Thus a multiplicative function satisfiesAt a prime power, the divisor sum becomes . This turns a calculation over many integer divisors into short local calculations at prime powers.
Elementary lower bound for the Chebyshev theta function Created 2026-09-24 Updated 2026-11-05
The Chebyshev theta function satisfies for every sufficiently large real number . This follows without the Prime number theorem.
Write for the second Chebyshev function. The largest binomial coefficient in row is the central one, and that row sums to , soBy the Legendre formula, the prime valuation of this central binomial coefficient is a sum of terms , each zero or one. Hence the coefficient divides , whose natural logarithm is . Taking logarithms gives , the central-coefficient argument of Chebyshev estimate from central binomial coefficients.
For real , take . Monotonicity gives . Higher prime powers contribute at most to , as proved for the second Chebyshev function. ThereforeAfter division by , the right side tends to , proving the stated lower bound.
Euler totient function Created 2026-09-24 Updated 2026-11-05
Euler's totient function is the arithmetic functionIt counts the congruence classes modulo represented by integers coprime to . In particular, , since . For , the coprime integers among are , so ; they form a reduced residue system. [ref]
Floor and arithmetic functions by Darij Grinberg. Darij Grinberg, MIT 18.781 lecture notes, Definition 2.1.2
Counting these congruence classes is useful because they are exactly the classes with modular multiplicative inverses. Their number supplies the exponent in Euler theorem. Möbius inversion gives the product formulawhere runs over distinct prime factors of . Thus for prime powers with , and . The product for is an empty product, so it gives the same convention .
Finite field Created 2026-09-24 Updated 2026-10-13
A finite field is a field with finitely many elements: addition, subtraction, multiplication, and division by a nonzero element all stay inside a finite collection. Write , or , for a finite field with elements. The subscript counts elements; it does not prescribe modular arithmetic modulo . The field with four elements is the smallest example where that distinction matters.
Every finite field has size , where is a prime number and is a positive integer. To see the counting mechanism, use its prime field : the finite field is a finite-dimensional vector space over . For a basis , every element has exactly one expressionEach coefficient has choices, so there are expressions. Here is the characteristic of a field and is the dimension of a vector space. Thus sizes are possible, whereas are not prime powers and cannot be finite field sizes.
Conversely, every prime power occurs, and any two finite fields of the same size admit a field isomorphism. These are classification statements, beyond the counting argument. See Conrad's Theorems 1.5, 2.2, and 2.7.[ref]
https://kconrad.math.uconn.edu/blurbs/galoistheory/finitefields.pdf. Keith Conrad, Finite Fields, sections 1–2
Uniqueness means the arithmetic agrees after relabeling; it does not choose a basis, an irreducible polynomial for a quotient ring representation, or a particular field isomorphism. Even for the field with four elements, exchanging and preserves the arithmetic.The appeal for coding theory is exact, finite arithmetic with reliable division: polynomial interpolation and linear algebra work over a finite alphabet. A Reed-Solomon code represents messages by polynomials and adds redundancy by evaluating them at several distinct finite field elements. Forney's MIT notes develop this arithmetic as preparation for such error-correcting codes.[ref]
https://ocw.mit.edu/courses/6-451-principles-of-digital-communication-ii-spring-2005/8921c013c1d7802bb197572c52442b97_chap7.pdf. G. David Forney Jr., Introduction to finite fields, 2005
In cryptography, finite fields likewise supply exact arithmetic on finitely many symbols, with operations that can be implemented using bits.Historically, Évariste Galois published work on finite fields beyond prime fields in 1830, constructing them by adjoining elements satisfying irreducible polynomials over prime fields. Conrad's historical account also records E. H. Moore's 1893 terminology, from which the name Galois field and notation descend.[ref]
Gaussian binomial coefficient Created 2026-10-13 Updated 2026-10-20
A Gaussian binomial coefficient refines an ordinary binomial coefficient into a polynomial that remembers a size statistic. For nonnegative integers and , writeThe product represents a polynomial; it is not an instruction to divide by zero when or a denominator vanishes. The Gaussian binomial coefficient recurrence gives a way to compute it with only addition and multiplication. The empty product for is one, and as well. Setting after obtaining the polynomial recovers .
For example,At this gives six objects, but its coefficients reveal how those six objects are distributed across sizes : there are two of size two and one of each other size. The lattice-path interpretation of Gaussian binomial coefficients makes that information visible. Take unit steps north or east from to . A north step at horizontal coordinate contributes shaded cells to its left. The six step words have total shaded areas .
This is useful because an aggregate count can hide the feature one actually wants. A generating function retains the distribution of a statistic, so coefficient extraction answers questions such as “how many allowed diagrams contain exactly two cells?” The partition interpretation of Gaussian binomial coefficients makes every coefficient a nonnegative integer without relying on cancellation in the product formula.
An unexpected second use comes from linear algebra. If is a prime power, the value counts the -dimensional vector subspaces of . Thus the same expression that counts six paths at counts 35 two-dimensional subspaces of at . The Gaussian binomial coefficient counts finite-field subspaces article explains why selecting a vector subspace differs from selecting a subset of coordinates. [ref]
This relationship illustrates a q-analogue: the parameter can encode a statistic in one interpretation and the size of a finite field in another. Here denotes the formal variable, while denotes a finite field's cardinality when we evaluate the polynomial. The interpretation using a finite field requires to be a prime power; evaluating the polynomial at an arbitrary number does not construct a field of that size.
For a prime power and , count ordered lists of linearly independent vectors in . The first has choices. After independent choices, their linear span contains vectors, so the next has choices. Every -dimensional vector subspace has exactly ordered bases. Dividing the list count by this common multiplicity givesThe notation refers to the Grassmannian, here considered simply as the finite collection of these vector subspaces.[ref]
For , there are ordered independent pairs. Each two-dimensional vector subspace has ordered bases, leaving vector subspaces. There are only coordinate-selected vector subspaces; most of the 35 also contain vectors combining coordinates.
A unique reduced row echelon form gives another count. Its six possible pivot-column patterns have freely chosen entries. Each free entry lies in , giving vector subspaces, respectively. The diagram fixes the zero entries required to make each pivot the first nonzero entry in its row and the only nonzero entry in its column. Different choices describe different row spaces.
Gaussian multinomial coefficient Created 2026-10-20 Updated 2026-11-05
For nonnegative with sum , the Gaussian multinomial coefficient isIt is a polynomial in and at gives the ordinary multinomial coefficient. For a prime power , it counts flags in whose successive dimension increments are : choose each new subspace in the quotient by the previous one, using Gaussian binomial coefficients. For , the value is , giving 21 complete flags over .
Greatest common unitary divisor Created 2026-10-20 Updated 2026-11-05
A unitary divisor of a positive integer satisfies . The greatest common unitary divisor of is the largest integer that is a unitary divisor of both. In their prime factorizations, it includes precisely those whole prime powers whose positive exponents agree in and .
For and , it is , although the ordinary greatest common divisor is . For and , it is . Requiring unitary divisibility on both inputs is essential: merely being a unitary divisor of their ordinary greatest common divisor is a weaker condition.
Hensel lifting Created 2026-10-20 Updated 2026-11-05
Hensel lifting improves a solution of a polynomial congruence modulo a prime power to one modulo a higher power. For , suppose and . A lift satisfiesThe invertible derivative therefore determines a unique modulo .
For , the root modulo seven lifts to modulo , since and . Repetition gives a root in the p-adic integers. The simple-root hypothesis ensures uniqueness; when the derivative vanishes modulo , there may be multiple lifts or none.
Idempotent residue Created 2026-10-20 Updated 2026-11-05
An idempotent residue modulo a positive integer is a class satisfying , equivalently . Since consecutive integers are coprime, an idempotent modulo a prime power must be either zero or one.
If has distinct prime factors, the Chinese remainder theorem therefore gives idempotent residues: independently choose zero or one at each prime-power factor. Modulo six the four possibilities are . They expose the decomposition of the quotient ring into its prime-power components.
Inverse totient problem Created 2026-10-20 Updated 2026-11-05
Given a positive integer , find all positive integers satisfying . For every prime divisor of a solution, divides , so the possible primes lie in the finite set . Search can then combine the prime powers whose totient contributions multiply to .
Lifting a primitive root to odd prime powers Created 2026-09-24 Updated 2026-11-05
Let be an odd prime and a primitive root modulo . Then is a primitive root modulo every prime power if and only if it is a primitive root modulo . In that caseThe condition at says with . The odd-prime case of the lifting-the-exponent lemma, obtained here by repeated use of the binomial theorem and then raising to an exponent not divisible by , givesHere is the prime valuation. To see the induction step, the first term in has prime valuation , while every later term has strictly greater prime valuation when is odd and .
Min_25 sieve Created 2026-10-20 Updated 2026-11-05
The Min_25 sieve computes summatory multiplicative functions by isolating weighted prime sums and then restoring composite contributions. A useful basic form applies when for primes , the degree is small, and values on prime powers can be computed efficiently. The formulas below explain the two stages; optimized implementations differ in scheduling and cost.[ref]
Min_25 sieve explanation in the ABC370 editorial. general multiplicative-function framework, Lucy DP and Min_25 sieve sections
Use quotient arguments . There are distinct values: indices at most contribute that many, and larger indices yield values below . The floor function identity keeps later quotients in this table.
For each exponent , initialize . Process primes in increasing order, and eligible in decreasing order, applyingThis removes composites whose smallest prime factor is . The subtraction inside parentheses excludes earlier primes from the possible cofactors. Decreasing ensures each smaller argument still has its pre- value. After sieving, is the desired sum of over primes up to .
To restore composites, let be the th prime and let sum over with every prime factor greater than . Set for . Otherwise its prime contribution is , and addUnique decomposition by smallest prime factor and its full exponent proves this recurrence: mixed numbers use the first term, pure powers use the second. With , and , the answer is . No complete-multiplicativity assumption is needed.
For the Euler totient function up to six, the prime contribution is . The composites add , and gives total twelve. This independently chosen small example checks that prime powers and mixed products are both counted once.



