Arithmetic derivative Created 2026-10-20 Updated 2026-11-05
The arithmetic derivative on positive integers is specified by for each prime number and the product rule . These conditions force . For a prime factorization they give
Repeated use of the product rule proves necessity. Conversely, the fundamental theorem of arithmetic makes this formula well-defined, and the addition of prime exponents under multiplication verifies the product rule. Thus it proves existence as well as uniqueness.[ref]
For example, . Despite its name, the arithmetic derivative does not preserve addition: , whereas . Its analogy with an ordinary derivative preserves the product rule while sacrificing the usual sum rule.
Dirichlet L-function Created 2026-09-24 Updated 2026-11-05
For a Dirichlet character modulo , its Dirichlet L-function is initially defined on the half-plane by
Since , this series converges absolutely by comparison with .
A Dirichlet character is a completely multiplicative function. The fundamental theorem of arithmetic therefore reorganizes the absolutely convergent series into an Euler product:
Expanding each factor as a geometric series assigns exactly one term to every positive integer. For the principal Dirichlet character , the factors at primes dividing disappear, giving , where is the Riemann zeta function.
Euclid's lemma 2026-10-13
If a prime number divides a product of integers , then divides or (possibly both):
For example, and . The hypothesis that is a prime number matters: , although six divides neither factor. When does not divide , the greatest common divisor of and is one; multiply Bézout's identity by to see that . Repeated application makes this the uniqueness step in the fundamental theorem of arithmetic. [ref].
For a completely computed example, because , while shows that seven does not divide twenty. Bézout's identity becomes, after multiplication by ,
The two terms on the right are divisible by seven, which explicitly recovers the forced divisibility of the second factor. Both alternatives can hold: , and seven divides both and .
In fact the property characterizes prime numbers among the integers greater than one. If is a composite number, choose with ; then , but divides neither nor . For several factors, repeated application of Euclid's lemma says that a prime number dividing their product divides at least one factor. In a product of prime numbers, that factor must equal it, because a prime number has no other prime factor. This is what prevents a different collection of prime factors from representing the same positive integer in the fundamental theorem of arithmetic.
Book VII, Proposition 30 of Euclid's Elements states the result in terms of a prime number measuring a product; its proof uses coprimality and ratios. The calculation using Bézout's identity above is a modern way to explain the same divisibility statement. [ref]
Euclid's theorem Created 2026-10-05 Updated 2026-10-14
There are infinitely many prime numbers. Indeed, for any finite list of prime numbers , the integer has a prime factor, by the fundamental theorem of arithmetic. None of the listed prime numbers divides , since each divides and a common divisor would divide . Thus no finite list contains all prime numbers. The constructed need not itself be a prime number.
For example, the first six prime numbers give
Both prime factors lie outside the original list, although is a composite number. The construction defeats a proposed complete list; it is not a formula guaranteed to produce a prime number. Book IX, Proposition 20 of Euclid's Elements explicitly considers both possibilities, prime and composite. [ref].
Factorization tree Created 2026-10-14 Updated 2026-10-20
A factorization tree is a rooted tree whose root is an integer . Each nonleaf label is a composite number split into two factors greater than one whose product equals that label; the leaves are prime numbers. Multiplying the leaves recovers . Many factorization trees can have the same root, but the fundamental theorem of arithmetic gives them the same leaf multiset.
Fundamental theorem of arithmetic Created 2026-09-24 Updated 2026-10-20
Every integer is a product of prime numbers, uniquely up to reordering the factors. More precisely, there are unique distinct prime numbers and unique positive integer exponents such that
In the header's displayed form, is the prime valuation, the exponent of in this prime factorization; it is zero when does not divide . Reordering or regrouping the prime factors does not give a different prime factorization.
For , repeated division gives , , , then , , and . Thus
Its nonzero prime valuations are , and . Recording only the distinct prime factors would lose the difference between and .
This turns divisibility into coordinatewise comparison of nonnegative exponents. A positive divisor of chooses an exponent from for , from for , and from for , giving positive divisors. The greatest common divisor takes the smaller exponent at each prime number; the least common multiple takes the larger. The theorem is a structural description, not an assertion that finding the factors of every large integer is computationally easy.
In general, for positive integers , the exact divisibility criterion is
For example, divides , with quotient , whereas does not: it requires four factors of two, but supplies only three. Both use only prime factors of , so membership in that list alone does not establish divisibility. Every positive divisor of is uniquely with , , . Sorted, all 24 positive divisors are
Thus the divisor function gives . These include divisors that are composite numbers, as well as the prime factors and one.
For another positive integer , the prime valuations give exact formulas for the greatest common divisor and least common multiple:
With and , their prime valuations at are and . The smaller exponents give , and the larger give , hence
Indeed, , , and . The same rules also explain : the smaller and larger exponents sum to the two original exponents. Here .
Figure 1. . The upper table compares exponents at the prime numbers for and , then takes their columnwise minimum and maximum. The lower tables enumerate for and ; each cell gives one positive divisor. Details.
The useful change of viewpoint is that multiplication becomes addition of prime valuations, , and divisibility becomes comparison. Many different-looking calculations therefore share one representation. The prime valuations are coordinates for multiplication, rather than digits in positional notation: they do not turn ordinary addition of integers into coordinatewise addition.
Different intermediate splits lead to the same prime ingredients. Starting with gives and ; starting with gives and . Continuing to split the composite numbers produces the same multiset of prime factors: three twos, two threes, and one five. The factorization tree records choices in the calculation, while the prime factorization records the invariant result.
Figure 2.
Two factorization trees for give the same prime factorization
. Details.
The proof outline explains the uniqueness. Existence follows by splitting a composite number into smaller factors until only prime numbers remain. For uniqueness, Euclid's lemma says that a prime factor of one product must divide one factor of any other prime product equal to it. That factor must be the same prime number; cancel it and repeat. The crucial divisibility step appears in Book VII, Proposition 30 of Euclid's Elements. [ref]
The ancient text supplies specific precursors to the modern statement: Book VII, Proposition 31 establishes that every composite number has a prime factor, and Book IX, Proposition 14 excludes any new prime factor from the least common multiple of given prime numbers. These are the propositions being cited, rather than the complete modern exponent formulation of the fundamental theorem of arithmetic. [ref] [ref]
Excluding one from the prime numbers keeps uniqueness meaningful: otherwise would give different collections of supposed prime factors. For , the natural convention is the empty product, equal to one, with no prime factors and all prime valuations zero.
Jacobi symbol Created 2026-09-24 Updated 2026-11-05
For an odd positive integer , the Jacobi symbol is the product of Legendre symbols
The fundamental theorem of arithmetic makes this definition unambiguous. Its value is zero exactly when and have a common prime factor; otherwise it is or . For , the empty product convention gives .
If is a quadratic residue modulo and is coprime to , its Jacobi symbol is one. The converse can fail for a composite number: , but two is not a square modulo fifteen because it is not a square modulo three.
Computing the Jacobi symbol does not require first finding the prime factorization. Repeatedly remove factors of two, swap odd numerator and denominator using Jacobi reciprocity, and reduce the numerator modulo the denominator, as in the Euclidean algorithm. This makes it useful in the Solovay-Strassen primality test.
If the prime does not divide , then . The Bezout identity gives integers with . Multiplying by gives . If , both terms on the left are divisible by , so . Thus Euclid lemma holds:
For completeness, existence in the fundamental theorem of arithmetic follows by strong induction on a positive integer . If is prime there is nothing to prove; otherwise with , and the inductive prime factorizations of give one for . The integer has the empty factorization.
For uniqueness, suppose are two prime factorizations. Repeated application of Euclid lemma shows that divides some . Both are primes, so they are equal. Reorder the second list, cancel this equal factor, and repeat. All factors must be matched, including their multiplicities. Thus prime factorization exists and is unique up to the order of its factors. For nonzero negative integers one also records the sign.
Suppose is a prime number, and . Since the only positive divisors of are one and , the greatest common divisor of and is one. By Bézout's identity, integers exist with . Multiplying by gives . Both terms on the left are divisible by , so . Thus Euclid lemma gives
The fundamental theorem of arithmetic says that every positive integer greater than one is a product of prime numbers, uniquely up to their order. Existence follows by strong mathematical induction: if is prime it already has a factorization; otherwise with , and the factorizations of combine to factor .
For uniqueness, suppose are two prime factorizations. Repeated application of Euclid lemma makes divide one of the , so primality forces . Reorder that factor to the front, cancel it and repeat. Neither side can retain extra primes when the other has become one, since every prime exceeds one. The two multisets are therefore identical. For a negative integer there is additionally the uniquely determined sign; one has the empty positive factorization, and zero is excluded. The prime-product divisibility lemma is the step which makes factorization unique.
Put . Comparing the harmonic number with an integral gives . By the fundamental theorem of arithmetic, the finite Euler product expands as the sum of over positive integers whose prime factors are at most . It therefore includes every term of , and
The first strict inequality is the geometric-series bound for the logarithmic remainder; the last uses the telescoping series . Thus the prime reciprocal lower bound is
Absolute convergence and the fundamental theorem of arithmetic give the Euler product
For a finite set of primes, expand the geometric factors: their product sums over integers whose prime factors lie in that set. Let the finite sets increase through all primes. Absolute convergence permits passage to the limit and recovers the full Dirichlet series. Moreover , so the logarithm converges and the product has no zeros there.
The same absolutely convergent logarithm, and , give
This is the product version of the three-four-one zero-free-region argument. It also proves there are no zeros on : if for , its factor has order at least four as , while the real pole contributes only order minus three and the factor remains bounded. The displayed left side would tend to zero, a contradiction. At there is a pole, not a zero.
For large , put . The Hardy-Littlewood approximation to the Riemann zeta function at gives for ; its finite sum is bounded by and the integral term is bounded. The Cauchy estimate for derivatives on circles of radius comparable to consequently gives for .
Take with a small fixed . The product inequality, , and imply
If , integration of the derivative along the horizontal segment changes this value by at most . Choose sufficiently small that , then sufficiently small. The lower bound remains a positive multiple of . For , the same product inequality, , and the near-one upper bound give that lower bound directly. For , the reciprocal Euler product gives .
Finally the no-zero result on , compactness at bounded heights and the regular reciprocal at the pole allow a further fixed reduction of to include bounded . We have proved the weak logarithmic zero-free region for the Riemann zeta function
The reciprocal at is its holomorphic extension, equal to zero.
An additive arithmetic function satisfies for coprime integers ; a completely additive arithmetic function satisfies this for all positive . In either case . The fundamental theorem of arithmetic gives , where means that the prime valuation of at is exactly .
Under the discrete uniform distribution on , the expectation of the indicator function of is
The formula remains valid when . Applying linearity of expectation to the finite prime power decomposition proves the required mean formula:
For the last assertion, write the excess prime-factor multiplicity directly as a sum of nonnegative indicator functions:
Here is the prime omega function and is the total number of prime factors. The expectation is bounded independently of , since
Thus Markov inequality gives vanishing probability on every diverging scale:
By the fundamental theorem of arithmetic, every integer greater than one has a prime factorization, and that factorization is unique up to reordering the factors. Equivalently, it has a unique finite prime-exponent representation , with nonnegative integer exponents. The unit integer has the empty product.
If the complete list of prime numbers were , then would have a prime divisor by the fundamental theorem of arithmetic. No divides it, since . This contradicts completeness of the list. Hence there are infinitely many prime numbers.
The fundamental theorem of arithmetic says that every integer is a product of prime numbers, uniquely up to reordering. Equivalently, for a unique family of nonnegative integer exponents, only finitely many of which are nonzero.
If the complete list of prime numbers were , then would have a prime divisor by the fundamental theorem of arithmetic. No divides it, since . This contradicts completeness of the list. Hence there are infinitely many prime numbers.
The fundamental theorem of arithmetic says that every integer is a product of prime numbers, uniquely up to reordering. Equivalently, for a unique family of nonnegative integer exponents, only finitely many of which are nonzero.
Use strong induction on the positive integer . The case is represented by the empty product. For , if is prime it is already a product of one prime. Otherwise with ; the induction hypothesis gives prime factorizations for both and , and concatenating them gives one for . This proves existence in the fundamental theorem of arithmetic without presupposing uniqueness.
The allowed primes are exactly . Define
The fundamental theorem of arithmetic makes this definition unambiguous and proves injectivity. For every , the positive integer belongs to and maps to that tuple, proving surjectivity. The inverse function is explicitly . In particular, maps to . This is the prime-exponent parametrization of smooth numbers.
For distinct primes , let consist of the positive integers having no other prime factors, including . The map from a number to its exponent tuple is a bijection from to when . The fundamental theorem of arithmetic proves that the tuple is uniquely defined and that equality of tuples implies equality of numbers. Every nonnegative tuple gives the allowed number , proving surjectivity. Multiplication of numbers corresponds to coordinatewise addition of tuples, with corresponding to the zero tuple.