Prime number ($p$)

A prime number is a positive integer $p>1$ whose only positive divisors are $1$ and $p$. The first ten prime numbers are $2,3,5,7,11,13,17,19,23,29$. In contrast, $12=3\cdot 4$ is a composite number because it has a positive divisor strictly between one and itself. The integer one is neither a prime number nor a composite number: the lower bound $p>1$ is part of the definition. Equivalently, the divisor function satisfies $\tau (p)=2$ for a prime number, whereas $\tau (1)=1$ and $\tau (n)\ge 3$ for every composite number $n$.

Prime numbers are the building blocks of positive integers under multiplication. The fundamental theorem of arithmetic says that every integer greater than one is a product of prime numbers, with a unique collection of factors when their order is ignored. For example, $12=2\cdot 2\cdot 3$ and $18=2\cdot 3\cdot 3$. Their common factors reveal the greatest common divisor $6$, and the combined maximum powers reveal the least common multiple $36$. A complicated divisibility question becomes a comparison of prime exponents.

There is also a useful finite test. If a composite number $n$ equals $ab$ with $1<a\le b$, then $a^2\le n$. Therefore some prime factor is at most $\sqrt{n}$, and trial division only needs to check prime numbers up to that square root. For $97$, checking $2,3,5,7$ suffices; none divides $97$, so it is a prime number. For $91$, the same test finds $7$, giving $91=7\cdot 13$. To find many prime numbers together, the sieve of Eratosthenes reuses the work by marking multiples.

The division with remainder calculations for $97$ make the test explicit:Since $9^2<97<10^2$, these are all the prime numbers at most its square root, and every remainder is nonzero. Thus the calculation certifies a prime number, without testing the integers $8,9,10,\dots ,96$ individually. In contrast, $91=7\cdot 13+0$ gives a prime factor and proves that $91$ is a composite number.

The definition has a long history. Book VII of Euclid's Elements distinguishes prime numbers from composite numbers through their possible measures; Book IX, Proposition 20 establishes that no finite list exhausts the prime numbers. The modern argument under Euclid's theorem needs only divisibility, so it proves an infinite conclusion without estimating how frequently prime numbers occur. ^{[ref] [ref]}.

A prime quadruplet is a set of four primes $p,p+2,p+6,p+8$. For example, $5,7,11,13$ form a prime quadruplet. Testing candidates uses integer congruences to discard starting values for which one of the four entries has a small prime factor.

Two primes whose difference is $6$, for example $5$ and $11$. The name refers to the Latin word for six. The primes need not be consecutive.

A prime number expressible as $(x^3-y^3)/(x-y)=x^2+xy+y^2$ for specified consecutive or nearly consecutive positive integers. The first kind has $x=y+1$ and therefore the form $3y^2+3y+1$; the second kind has $x=y+2$ and therefore the form $3y^2+6y+4$. The first kind arises when a difference of two cubes is itself prime: the factorization $x^3-y^3=(x-y)(x^2+xy+y^2)$ forces $x-y=1$ for $x>y>0$.

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, $3797$ is truncatable from both ends: $3797,797,97,7$ and $3797,379,37,3$ consist entirely of prime numbers.

A prime number for which every cyclic rotation of its numerical digits is also a prime number. In decimal representation, $197$ is an example because $197,971,719$ are all prime numbers. A multi-digit circular prime can contain only $1,3,7,9$: any other digit can be rotated into the units position and force divisibility by $2$ or $5$.

Primality is the property of a positive integer being a prime number. Primality testing determines this property; integer factorization asks for factors and is a different computational task.

Trial division searches for divisors of an integer by testing candidate divisions. For primality testing of an integer $n>1$, testing the prime numbers up to $\sqrt{n}$ 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.

The sieve of Eratosthenes finds all prime numbers at most an integer $N\ge 2$. Start with the integers $2,\dots ,N$ marked as candidates. For each surviving candidate $p$ in increasing order, mark the multiples $p^2,p^2+p,\dots$ up to $N$ as composite numbers. Stop processing candidates once $p^2>N$: the surviving candidates are exactly the prime numbers. Starting at $p^2$ saves work because any smaller proper multiple of $p$ already has a smaller prime factor. ^[ref].

For a complete run with $N=60$, the only prime numbers at most $\sqrt{60}$ are $2,3,5,7$, since $7^2\le 60<8^2$. Exclude one before starting; it is not a prime number. The four marking passes are:

There are $59-29-9-3-1=17$ surviving prime numbers:The next surviving candidate is $11$, and $11^2>60$, so no further marking pass is necessary. A prime number used for marking remains a candidate: starting at $p^2$ never marks $p$ itself.

The saving from starting at $p^2$ is justified by the smaller multiplier: if $pk<p^2$ with $2\le k<p$, then $k$ has a prime factor $q<p$, so $q$ has already marked $pk$. For $p=7$, the earlier multiples $14,21,28,35,42$ have already been marked using $2,3$ or $5$. The first new possibility is $49$.

For $N=100$, only the prime numbers $2,3,5,7$ 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.

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 $N$ has a prime factor at most $\sqrt{N}$, 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 $p^2$ starting rule are the formulation explained here, rather than instructions quoted from Euclid's Elements. ^[ref]

Assume that $x^2\equiv -3(\mathrm{mod}p)$ with $p>3$ implies $p\equiv 1(\mathrm{mod}6)$. For a finite list of primes in that residue class, let $P$ be their product. Every prime divisor of $4P^2+3$ is greater than three and satisfies that quadratic modular congruence, hence has residue one modulo six. None is listed because $4P^2+3\equiv 3$ modulo a listed prime.

// Target: combinatorics.bigb

For any finite list of such prime numbers, let $P$ be their product. The integer $6P-1$ has no listed prime divisor, nor the divisors $2,3$. Its remaining prime factors have residues $1,-1$ modulo six, and at least one has residue $-1$ because their product has that residue. Thus no finite list is exhaustive.

// Target: number-theory.bigb

For every integer $n>1$, there is a prime number strictly between $n$ and $2n$. This supplies cyclic prime moduli comparable to an integer interval's length in additive combinatorics.

Two primes differing by two form a twin-prime pair, for example $3,5$ or $11,13$. The twin-prime upper bound using Bombieri–Vinogradov limits their number without proving there are infinitely many.

The conjecture asserts that infinitely many prime numbers $p$ have $p+2$ 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.

The local-density prediction for twin primes is the displayed asymptotic, with the twin-prime constant $C_2$. It is stronger than infinitude alone. The Selberg sieve proves the correct order of magnitude as an upper bound, but the parity problem in sieve theory prevents its elementary majorant from proving this conjectured asymptotic.

// Target: analytic-number-theory.bigb

This positive convergent product corrects for the dependence of primality of $n$ and $n+2$ at each odd prime. The associated singular series is $2C_2$: the factor at two is two, and at an odd prime the local correction is $(1-2/p)/(1-1/p{)}^2$. It appears in the Hardy–Littlewood twin-prime asymptotic conjecture and in upper bounds from the Selberg sieve.

// Target: analytic-number-theory.bigb

The sum of reciprocals of twin primes converges, whether or not there are infinitely many twin primes. The twin-prime upper bound from a quadratic sieve and reciprocal-sum convergence from a counting bound prove it. This contrasts with the Euler proof that the sum of reciprocals of primes diverges.

Apply the Selberg upper-bound sieve to the numbers $p+2$ with $p\le x$ prime. For odd squarefree integers $d$, the local count is $\pi (x;d,-2)$ and the density is $1/\varphi (d)$. With sieve level $D=x^{1/3}$, the normalizing sum is $\gg \log x$ by the truncated Euler-product lower bound. The Selberg least-common-multiple weights have absolute values at most $3^{\omega (d)}$. The weighted arithmetic-progression error bound and Bombieri–Vinogradov theorem make their total error $O(x/{\log }^{3}x)$. Consequently the number of twin prime pairs with smaller member at most $x$ is $O(x/{\log }^{2}x)$.

There are infinitely many prime numbers. Indeed, for any finite list of prime numbers $p_1,\dots ,p_k$, the integer $N=p_1\cdots p_k+1>1$ has a prime factor, by the fundamental theorem of arithmetic. None of the listed prime numbers divides $N$, since each divides $N-1$ and a common divisor would divide $1$. Thus no finite list contains all prime numbers. The constructed $N$ need not itself be a prime number.

For example, the first six prime numbers giveBoth prime factors lie outside the original list, although $30031$ 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].

There are infinitely many primes in each of the classes one and three modulo four. For the first, a hypothetical finite list $p_1,\dots ,p_r$ is contradicted by any prime divisor $q$ of $(2p_1\cdots p_r{)}^2+1$: it is odd, not on the list, and admits a square root of minus one, so $q\equiv 1(\mathrm{mod}4)$. For the second, $4p_1\cdots p_r-1$ is three modulo four; its prime factorization must include a prime that is three modulo four, and none of the listed primes divides it. These special congruence classes therefore admit elementary product-plus-or-minus-one arguments without the general theorem on primes in arithmetic progressions.

An odd prime is a prime number that is an odd integer. The only even number that is a prime number is $2$, since every other positive even number has $2$ as a proper divisor. Thus every prime number greater than $2$ is an odd prime. There are infinitely many odd primes, by Euclid's theorem.

A Fermat prime is a Fermat number that is also a prime number:The defining form alone does not imply primality. For example, $65537$ is a Fermat prime, while $4294967297$ is a Fermat number with proper divisors. For $k\ge 1$, every Fermat prime is one modulo four and two modulo three. Pépin's test gives an exact primality testing criterion for these candidates, rather than relying on their form.

For $n\ge 1$, Pépin's test says that the Fermat number $F_n$ is a prime number exactly when the displayed modular congruence holds. Modular exponentiation evaluates it by exponentiation by squaring without constructing the enormous ordinary power. The index restriction excludes $F_0=3$, where the base itself is divisible by the candidate.^[ref]

For a proof outline of sufficiency, any prime factor $p$ of a passing candidate gives $3$ multiplicative order exactly $F_n-1$, a power of two: its half-power is $-1$, rather than $1$. Fermat's little theorem forces $F_n-1\mid p-1$, so $p\ge F_n$, and hence $p=F_n$. Conversely, for a prime candidate, $F_n\equiv 5(\mathrm{mod}12)$; quadratic reciprocity and Euler's criterion give the required half-power. At $n=1$, the check is $3^2\equiv 4=-1(\mathrm{mod}5)$.

For a Fermat prime $p=2^{2^k}+1$, the multiplicative group modulo $p$ has order $2^{2^k}$. Its $\phi (p-1)=(p-1)/2$ primitive roots are all quadratic nonresidues; since there are also $(p-1)/2$ nonresidues, the two sets coincide.

Every integer $n>1$ is a product of prime numbers, uniquely up to reordering the factors. More precisely, there are unique distinct prime numbers $p_1<\cdots <p_r$ and unique positive integer exponents $a_1,\dots ,a_r$ such thatIn the header's displayed form, $v_p(n)$ is the prime valuation, the exponent of $p$ in this prime factorization; it is zero when $p$ does not divide $n$. Reordering or regrouping the prime factors does not give a different prime factorization.

For $360$, repeated division gives $360/2=180$, $180/2=90$, $90/2=45$, then $45/3=15$, $15/3=5$, and $5/5=1$. ThusIts nonzero prime valuations are $v_2(360)=3$, $v_3(360)=2$ and $v_5(360)=1$. Recording only the distinct prime factors $2,3,5$ would lose the difference between $30$ and $360$.

This turns divisibility into coordinatewise comparison of nonnegative exponents. A positive divisor of $360$ chooses an exponent from $0,1,2,3$ for $2$, from $0,1,2$ for $3$, and from $0,1$ for $5$, giving $4\cdot 3\cdot 2=24$ 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 $d,n$, the exact divisibility criterion isFor example, $72=2^3\cdot 3^2$ divides $360$, with quotient $5$, whereas $48=2^4\cdot 3$ does not: it requires four factors of two, but $360$ supplies only three. Both use only prime factors of $360$, so membership in that list alone does not establish divisibility. Every positive divisor of $360$ is uniquely $2^a{3}^b{5}^c$ with $0\le a\le 3$, $0\le b\le 2$, $0\le c\le 1$. Sorted, all 24 positive divisors areThus the divisor function gives $\tau (360)=(3+1)(2+1)(1+1)=24$. These include divisors that are composite numbers, as well as the prime factors and one.

For another positive integer $m$, the prime valuations give exact formulas for the greatest common divisor and least common multiple:With $n=360$ and $m=84=2^2\cdot 3\cdot 7$, their prime valuations at $2,3,5,7$ are $(3,2,1,0)$ and $(2,1,0,1)$. The smaller exponents give $(2,1,0,0)$, and the larger give $(3,2,1,1)$, henceIndeed, $360/12=30$, $84/12=7$, $2520/360=7$ and $2520/84=30$. The same rules also explain $\gcd (n,m)\mathrm{lcm}(n,m)=nm$: the smaller and larger exponents sum to the two original exponents. Here $12\cdot 2520=360\cdot 84=30240$.

The useful change of viewpoint is that multiplication becomes addition of prime valuations, $v_p(nm)=v_p(n)+v_p(m)$, 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 $360=36\cdot 10$ gives $36=6\cdot 6$ and $10=2\cdot 5$; starting with $360=8\cdot 45$ gives $8=2\cdot 4$ and $45=5\cdot 9$. 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.

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 $360=2^3\cdot 3^2\cdot 5=1\cdot 2^3\cdot 3^2\cdot 5=1\cdot 1\cdot 2^3\cdot 3^2\cdot 5$ would give different collections of supposed prime factors. For $n=1$, the natural convention is the empty product, equal to one, with no prime factors and all prime valuations zero.

For an integer $n>1$ with prime factorization $n={\prod }_{j=1}^r{p}_j^{e_j}$, this is the sum of its prime factors with each repeated $e_j$ times. For example, $s(18)=2+3+3=8$. It differs from the sum of distinct prime factors.

The prime signature of $n={\prod }_{i=1}^r{p}_i^{a_i}$ is the multiset of positive prime exponents $a_i$, conventionally sorted. For example, $12=2^2\cdot 3$ and $45=3^2\cdot 5$ both have signature $(2,1)$. Quantities such as the divisor function and the number of ordered factorizations depend on this signature rather than the particular primes.

A factorization tree is a rooted tree whose root is an integer $n>1$. 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 $n$. Many factorization trees can have the same root, but the fundamental theorem of arithmetic gives them the same leaf multiset.

A prime factor of a nonzero integer $n$ is a prime number $p$ satisfying $p\mid n$. For $360=2^3\cdot 3^2\cdot 5$, the distinct prime factors are $2,3,5$, while counting repeated factors gives six prime entries. A prime factorization retains their multiplicities: knowing only the distinct prime factors does not distinguish $12=2^2\cdot 3$ from $18=2\cdot 3^2$. A negative integer has the same prime factors as its absolute value.

A prime power is a positive integer of the form $p^d$, where $p$ is a prime number and $d$ is a nonnegative integer.