Tate module Created 2026-10-14 Updated 2026-11-05
For an abelian variety and a prime number different from the characteristic, the inverse limit of its geometric -torsion, with transition multiplication by , is its Tate module. For an elliptic curve, it is free of rank two over the p-adic integers and satisfies . The absolute Galois group acts continuously and commutes with all base-defined endomorphisms.
Let satisfy Eisenstein's criterion at a prime number , and let be a root. Then
Indeed, is an algebraic integer, whereas for and the field norm of has -adic valuation , so that element is not integral. If is integral, multiply it by . Every term except is integral; thus . Subtract , multiply the remainder by , and continue to obtain for every . Hence there is no element of order in the finite group , proving the claim. The result concerns the Eisenstein prime only: other primes may still divide the index.
Tonelli-Shanks algorithm Created 2026-10-20 Updated 2026-11-05
The Tonelli-Shanks algorithm finds a square root of a quadratic residue modulo an odd prime number . Handle separately and use the Legendre symbol to reject a quadratic nonresidue. Write with odd, choose a quadratic nonresidue , and initialize
modulo . Maintain , with of multiplicative order and of multiplicative order dividing .
If , find the least with . Set and update
The multiplicative order of decreases because its last nontrivial power and that of are both minus one. Thus strictly decreases. At , the invariant gives .
For , initialization gives . One update gives , so the roots are and modulo thirteen.[ref]
Total number of prime factors Created 2026-10-06 Updated 2026-11-05
The total number of prime factors counts every occurrence of a prime factor in the prime factorization of a positive integer . Equivalently, it adds the prime valuations:
One may also write over all prime numbers, since only finitely many prime valuations are nonzero. The empty sum gives . By contrast, the prime omega function has and counts distinct prime factors. [ref]
Expanding into shows , whereas and . The same calculation for the comparison examples gives
The total number of prime factors agrees for and , although their prime supports of an integer differ. Meanwhile and have the same radical of an integer and prime omega function, but different values of the total number of prime factors. These examples show exactly which information each arithmetic function forgets.
Figure 1.
One box per prime factor occurrence: the total number of prime factors counts boxes, the prime omega function counts groups, and the radical of an integer multiplies one prime number from each group
. Details.
The total number of prime factors is a completely additive arithmetic function:
The proof is that multiplication adds each prime valuation, , and summing preserves that equality. No coprimality condition is needed. For example, and both have total number of prime factors three; their product has six. By comparison, the prime omega function is only an additive arithmetic function: here .
There is a useful way to see the total number of prime factors as a count of elementary building blocks: any expression of as a product of prime numbers has exactly factors, by the fundamental theorem of arithmetic. Equivalently, every factorization tree for has leaves. Repeated prime factors increase this count without introducing new kinds of prime number. The difference is the existing excess prime-factor multiplicity:
Every summand is nonnegative, so if and only if is a squarefree integer, including . In particular, a prime power with has , and .
Historically, Hardy and Ramanujan's 1917 paper explicitly separated the prime omega function from the total number of prime factors, writing them as and , respectively. Their example has counts three and six. That distinction let them compare two measures of how an integer is built from prime factors. [ref]
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.
Truncatable prime 2026-10-20
A prime number that remains prime after successively deleting digits from a specified end of its positional notation. Left truncation, right truncation, and requiring both are distinct conditions. For example, is truncatable from both ends: and consist entirely of prime numbers.
Twin prime conjecture Created 2026-10-14 Updated 2026-11-05
The conjecture asserts that infinitely many prime numbers have prime. The Hardy–Littlewood twin-prime asymptotic conjecture predicts their quantitative frequency and is stronger. The Selberg sieve supplies an upper bound of the predicted order but does not prove infinitude.
Unbounded element orders in imaginary quadratic ideal class groups Created 2026-10-25 Updated 2026-10-31
For every positive integer , some imaginary quadratic field has an ideal class of order of a group element greater than . Specifically, take a prime number with . In , the Dedekind factorization theorem gives , with distinct prime ideals and of ideal norm five. If for , the field norm equation forces . Then is even and , contradicting unique factorization of ideals in a number field. Thus has order of a group element greater than . The existence of suitable follows from Dirichlet's theorem on arithmetic progressions.
A finite abelian group is a cyclic group if and only if it has at most one subgroup of each order dividing its order. A cyclic group has exactly one subgroup of order for each , generated by the th power of a generator.
Conversely, the structure theorem for finitely generated modules over a principal ideal domain expresses as with . If , choose a prime number . The first and second summands then provide distinct subgroups of order , contradicting the hypothesis. Hence , so is cyclic, including the trivial group when . This criterion combines with the root bound for a polynomial to prove that a finite subgroup of a field multiplicative group is cyclic.
Unit modulo n Created 2026-09-29 Updated 2026-10-14
For a positive integer modulus , a residue class is a unit when it has a modular multiplicative inverse: some integer satisfies . Modulo twelve, the units are exactly
In particular, five is its own modular inverse, since . Multiplying all twelve residue classes by five gives a permutation; multiplying the outputs by five recovers the inputs. By contrast, multiplying by six gives only zero and six, with six inputs for each output. It cannot be reversed.
Figure 1.
Multiplication by five permutes all twelve residue classes, whereas multiplication by six merges distinct inputs
. Details.
In general, the exact criterion is
For the forward direction, implies every common divisor of divides one. Conversely, if their greatest common divisor is one, Bézout's identity supplies , so is a modular inverse. The extended Euclidean algorithm computes these coefficients. The units form the unit group under multiplication. [ref]
Multiplicative cancellation while keeping the same integer modulus is valid for a unit modulo n: from , multiply by a modular inverse of to get . A nonunit cannot be cancelled as a general rule. For example, , yet . Thus division by six cannot undo this multiplication; solving a linear congruence instead keeps track of all possible classes.
This distinction marks the boundary between commutative rings and fields. Modulo a prime number , every nonzero residue class is a unit, so is a finite field. Modulo twelve it is a commutative ring with zero divisors, and is not a field. For , the sole class satisfies and is a unit; this one-element zero ring is not a field. [ref]
Upper asymptotic density Created 2026-10-06 Updated 2026-10-14
For a subset of the positive integers, its upper asymptotic density is
The limit superior keeps the largest limiting proportion even when the running proportions oscillate. Because they lie in , this limit superior always exists in . If natural density exists, upper asymptotic density equals it.
The convention here uses , while natural density above uses . Replacing one interval by the other changes a count by at most one, so the proportions differ by at most and have the same limit superior. For the set without natural density above, the count in is six rather than five, because is included and zero is absent. Nevertheless its upper asymptotic density is exactly . The even positive integers have upper asymptotic density and the prime numbers have upper asymptotic density zero.
The useful feature is that a large proportion along arbitrarily large initial integer intervals already supplies structure. The Szemerédi theorem says that positive upper asymptotic density forces arithmetic progressions of every finite length, with positive common difference, even without an existing natural density. Szemerédi's 1975 paper resolved this general finite-length problem; it makes density a bridge from counting to additive structure. [ref]
Valuation Created 2026-09-29 Updated 2026-11-05
An additive valuation on a field is a map , where is a totally ordered group with commutative addition, satisfying
The order is compatible with addition, and exceeds every element of . One usually takes the value group to be the image of . The trivial valuation assigns zero to every nonzero element.
For a prime number , writing a nonzero rational number as with dividing neither nor gives the p-adic valuation . Thus . Products add exponents, whereas cancellation in a sum can only increase the minimum exponent. In fact, if then : applying the inequality to rules out a strict increase. The nonnegative elements form the valuation ring, whose positive-valued elements form its maximal ideal.
Victor Ufnarovski 2026-11-05
Victor Ufnarovski studied the arithmetic derivative with Bo Åhlander. Their definition assigns derivative one to every prime number and extends by the product rule. For , the resulting formula turns differentiation into an operation governed by integer factorization, rather than an ordinary derivative of a real-variable function.[ref]
Von Mangoldt divisor identity Created 2026-09-24 Updated 2026-10-14
For every positive integer , the divisor sum of its Von Mangoldt function weights recovers its natural logarithm:
The sum runs over the positive integer divisors of . For , its only term is . Equivalently, if and is the constant-one arithmetic function, then , where is Dirichlet convolution. [ref]
For , the positive integer divisors are . Only contribute:
Thus the vanishing of loses no information here: the divisor sum retrieves both copies of the prime factor from the integer divisors and .
Figure 1.
The Von Mangoldt divisor identity assembles from three nonzero divisor weights
. The six positive integer divisors of appear in increasing order. Blue bars contribute at and ; the orange bar contributes at . The remaining three weights are zero. The adjacent stacked bar shows the total . Details.
Proof outline: by the fundamental theorem of arithmetic, write with distinct prime numbers and positive exponents . Among the positive integer divisors, the ones with nonzero Von Mangoldt function weights are exactly . Consequently
The natural logarithm turns the prime factorization product into a sum, and the prime powers greater than one supply exactly the required multiplicities.
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.
Wheel modulus Created 2026-10-20 Updated 2026-11-05
The wheel modulus is the product of a chosen finite set of small distinct prime numbers in wheel factorization. Except for those primes themselves, every prime candidate must lie in a residue class coprime to . For , the allowed residues are , repeating every thirty integers. The proportion retained is . Passing the wheel only avoids these small divisors; it does not certify primality, since composite values such as still pass.
For an odd prime number , put . Both and are divisible by . By Wilson's theorem, they are also congruent modulo , because each is modulo . The coprime integers therefore both divide their difference, giving the displayed integer congruence. This combines the prime-modulus factorial identity with an elementary divisibility constraint.
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.
Wolstenholme's theorem Created 2026-10-20 Updated 2026-11-05
For every prime number , Wolstenholme's theorem gives
Its harmonic-sum form is . All denominators are coprime to , so fractions are interpreted using modular inverses.
Here is a proof of both assertions. Write . Multiplication by permutes the nonzero residue classes modulo , so . Since , this implies . Replacing by in gives
using . Thus , proving the harmonic-sum form.
Finally, expand the binomial coefficient as a product:
Terms containing three or more selected factors vanish in this integer congruence. The two harmonic-sum estimates make both remaining correction terms zero modulo . For , the result reads .