 # Prime numbers

## Prime numbers Topics

Sort by:

### Prime formulas

There exist a variety of formulas for either producing the th prime as a function of or taking on only prime values. However, all such formulas require either extremely accurate knowledge of some unknown constant, or effectively require knowledge of the primes ahead of time in order to use the formula (Dudley 1969; Ribenboim 1996, p. 186). There also exist simple prime-generating polynomials that generate only primes for the first (possibly large) number of integer values.There are also many beautiful formulas involving prime sums and prime products that can be done in closed form.Considering examples of formulas that produce only prime numbers (although not necessarily the complete set of prime numbers ), there exists a constant (OEIS A051021) known as Mills' constant such that(1)where is the floor function, is prime for all (Ribenboim 1996, p. 186). The first few values of are 2, 11, 1361, 2521008887, ... (OEIS A051254). It..

### Prime distance

The prime distance of a nonnegative integer is the absolute difference between and the nearest prime. It is therefore true that for primes . The first few values for , 1, 2, ... are therefore 2, 1, 0, 0, 1, 0, 1, 0, 1, 2, ... (OEIS A051699). The values of having prime distances of 0, 1, 2, 3, ... are 2, 1, 0, 26, 93, 118, 119, 120, 531, 532, 897, ... (OEIS A077019).

### Zsigmondy theorem

If and (i.e., and are relatively prime), then has at least one primitive prime factor with the following two possible exceptions: 1. . 2. and is a power of 2. Similarly, if , then has at least one primitive prime factor with the exception .A specific case of the theorem considers the th Mersenne number , then each of , , , ... has a prime factor that does not occur as a factor of an earlier member of the sequence, except for . For example, , , , ... have the factors 3, 7, 5, 31, (1), 127, 17, 73, 11, , ... (OEIS A064078) that do not occur in earlier . These factors are sometimes called the Zsigmondy numbers .Zsigmondy's theorem is often useful, especially in group theory, where it is used to prove that various groups have distinct orders except when they are known to be the same (Montgomery 2001)...

### Pollard rho factorization method

A prime factorization algorithm also known as Pollard Monte Carlo factorization method. There are two aspects to the Pollard factorization method. The first is the idea of iterating a formula until it falls into a cycle. Let , where is the number to be factored and and are its unknown prime factors. Iterating the formula(1)or almost any polynomial formula (an exception being ) for any initial value will produce a sequence of number that eventually fall into a cycle. The expected time until the s become cyclic and the expected length of the cycle are both proportional to .However, since with and relatively prime, the Chinese remainder theorem guarantees that each value of (mod ) corresponds uniquely to the pair of values (), ). Furthermore, the sequence of s follows exactly the same formula modulo and , i.e.,(2)(3)Therefore, the sequence (mod ) will fall into a much shorter cycle of length on the order of . It can be directly verified that two values and..

### Williams p+1 factorization method

A variant of the Pollard p-1 method which uses Lucas sequences to achieve rapid factorization if some factor of has a decomposition of in small prime factors.

### Prime difference function

(1)The first few values are 1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, ... (OEISA001223). Rankin has shown that(2)for infinitely many and for some constant (Guy 1994). At a March 2003 meeting on elementary and analytic number in Oberwolfach, Germany, Goldston and Yildirim presented an attempted proof that(3)(Montgomery 2003). Unfortunately, this proof turned out to be flawed.An integer is called a jumping champion if is the most frequently occurring difference between consecutive primes for some (Odlyzko et al.).

### Exponent vector

Let denote the th prime, and writeThen the exponent vector is .

### Excludent factorization method

Also known as the difference of squares method. It was first used by Fermat and improved by Gauss. Gauss looked for integers and satisfyingfor various moduli . This allowed the exclusion of many potential factors. This method works best when factors are of approximately the same size, so it is sometimes better to attempt for some suitably chosen value of .

### Ordered factorization

An ordered factorization is a factorization (not necessarily into prime factors) in which is considered distinct from . The following table lists the ordered factorizations for the integers 1 through 10.ordered factorizations11121231342, 451563, , 671784, , , 892, 9103, , 10The numbers of ordered factorizations of , 2, ... are given by 1, 1, 1, 2, 1, 3, 1, 4, 2, 3, ... (OEIS A074206). This sequence has the Dirichlet generating function(1)where is the Riemann zeta function.A recurrence equation for is given by(2)where the sum is over the divisors of and (Hille 1936, Knopfmacher and Mays 2006). Another recurrence also due to Hille (1936) for is given by(3)where and(4)is the prime factorization of (Knopfmacher and Mays 1996).MacMahon (1893) derived the beautiful double sum formula(5)where(6)(Knopfmacher and Mays 1996). In the case that is a product of two prime powers,(7)Chor et al. (2000) showed that(8)(9)where is a hypergeometric function.The..

### Euler's factorization method

A factorization algorithm which works by expressing as a quadratic form in two different ways. Then(1)so(2)(3)Let be the greatest common divisor of and so(4)(5)(6)(where denotes the greatest common divisor of and ), and(7)But since , and(8)which gives(9)so we have(10)(11)(12)(13)(14)(15)

### Unordered factorization

An unordered factorization is a factorization of a number into a product of factors where order is ignored. The following table lists the unordered factorizations of the first few positive integers.unordered factorizations1122334, 4556, 6778, , 89, 910, 10A recurrence product for the number of unordered factorizations is given by Harris and Subbarao (1991).The numbers of unordered factorizations for , 2, ... are therefore 1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 4, 1, 2, 2, 5, ... (OEIS A001055). The maximum numbers of parts in the unordered (or ordered) factorizations of for , 2, ... are 1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 3, 1, 2, 2, 4, ... (OEIS A086436).The following gives a table of unordered factorizations with distinct parts for between 1 and 10.distinct unordered factorizations11223344556, 6778, 89910, 10The numbers of unordered factorizations with distinct parts for , 2, ... are given by 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 2, 2, 1, 3, ... (OEIS A045778). The..

### Euclid's theorems

A theorem sometimes called "Euclid's first theorem" or Euclid's principle states that if is a prime and , then or (where means divides). A corollary is that (Conway and Guy 1996). The fundamental theorem of arithmetic is another corollary (Hardy and Wright 1979).Euclid's second theorem states that the number of primes is infinite. This theorem, also called the infinitude of primes theorem, was proved by Euclid in Proposition IX.20 of the Elements (Tietze 1965, pp. 7-9). Ribenboim (1989) gives nine (and a half) proofs of this theorem. Euclid's elegant proof proceeds as follows. Given a finite sequence of consecutive primes 2, 3, 5, ..., , the number(1)known as the th Euclid number when is the th prime, is either a new prime or the product of primes. If is a prime, then it must be greater than the previous primes, since one plus the product of primes must be greater than each prime composing the product. Now, if is a product of primes,..

### Dixon's factorization method

In order to find integers and such that(1)(a modified form of Fermat's factorization method), in which case there is a 50% chance that is a factor of , choose a random integer , compute(2)and try to factor . If is not easily factorable (up to some small trial divisor ), try another . In practice, the trial s are usually taken to be , with , 2, ..., which allows the quadratic sieve factorization method to be used. Continue finding and factoring s until are found, where is the prime counting function. Now for each , write(3)and form the exponent vector(4)Now, if are even for any , then is a square number and we have found a solution to (◇). If not, look for a linear combination such that the elements are all even, i.e.,(5)(6)Since this must be solved only mod 2, the problem can be simplified by replacing the s with(7)Gaussian elimination can then be used tosolve(8)for , where is a vector equal to (mod 2). Once is known, then we have(9)where the products are taken..

### Squarefree factorization

Squarefree factorization is a first step in many factoring algorithms. It factors nonsquarefree polynomials in terms of squarefree factors that are relatively prime. It can separate factors of different multiplicities, but not factors with the same multiplicity. One way to find a squarefree factorization is to compute polynomial greatest common denominators iteratively.The squarefree part (i.e., product of all distinct monic irreducible factors) of a monic nonconstant polynomial in a field of characteristic zero is , where is the derivative of .

### Least prime factor

Let be any integer and let (also denoted ) be the least integer greater than 1 that divides , i.e., the number in the factorizationwith for . The least prime factor is implemented in the Wolfram Language as FactorInteger[n][[1,1]].For , 3, ..., the first few are 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, ... (OEIS A020639).If is composite then (Séroul 2000, p. 7), with equality for the square of a prime.A plot of the least prime factor function resembles a jagged terrain of mountains, which leads to the appellation of "twin peaks" to a pair of integers such that 1. , 2. , 3. For all , implies . The least multiple prime factors for squarefulintegers are 2, 2, 3, 2, 2, 3, 2, 2, 5, 3, 2, 2, 2, ... (OEIS A046027).Erdős et al. (1993) consider the least prime factor of the binomial coefficients, and define what they term good binomial coefficients and exceptional binomial coefficients. They also conjecture that..

### Distinct prime factors

The distinct prime factors of a positive integer are defined as the numbers , ..., in the prime factorization(1)(Hardy and Wright 1979, p. 354).A list of distinct prime factors of a number can be computed in the Wolfram Language using FactorInteger[n][[All, 1]], and the number of distinct prime factors is implemented as PrimeNu[n].The first few values of for , 2, ... are 0, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 1, 2, 1, 2, ... (OEIS A001221; Abramowitz and Stegun 1972, Kac 1959). This sequence is given by the inverse Möbius transform of , where is the characteristic function of the prime numbers (Sloane and Plouffe 1995, p. 22). The prime factorizations and distinct prime factors of the first few positive integers are listed in the table below.prime factorizationdistinct prime factors (A027748)1--0--221233134125515622, 377178129131022, 511111111222, 313131131422, 71523, 51612The numbers consisting only of distinct..

### Sphenic number

A sphenic number is a positive integer which is the product of exactly three distinct primes. The first few sphenic numbers are 30, 42, 66, 70, 78, 102, 105, 110, 114, ... (OEIS A007304).In particular, if , , and are prime numbers, then every sphenic number has precisely eight positive divisors, namely , , , , , , , and itself.The Möbius function of a sphenic number is .

### Direct search factorization

Direct search factorization is the simplest (and most simple-minded) prime factorization algorithm. It consists of searching for factors of a number by systematically performing trial divisions, usually using a sequence of increasing numbers. Multiples of small primes are commonly excluded to reduce the number of trial divisors, but just including them is sometimes faster than the time required to exclude them. Direct search factorization is very inefficient, and can be used only with fairly small numbers.When using this method on a number , only divisors up to (where is the floor function) need to be tested. This is true since if all integers less than this had been tried, then(1)In other words, all possible factors have had their cofactors already tested. It is also true that, when the smallest prime factor of is , then its cofactor (such that ) must be prime. To prove this, suppose that the smallest is . If , then the smallest value and could assume..

### Rough number

Finch (2001, 2003) defines a -rough (or -jagged) number to be positive integer all of whose prime factors are greater than or equal to .Greene and Knuth define "unusual numbers" as numbers whose greatest prime factor is greater than or equal to , and these number are dubbed "-rough" or "-jagged" by Finch (2001, 2003). The first few unusual numbers are 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, ... (OEIS A063538), which turn out to not be so unusual after all (Greene and Knuth 1990, Finch 2001). The first few "usual" numbers are then 8, 12, 16, 18, 24, 27, 30, ... (OEIS A063539).The probability that the greatest prime factor of a random integer is greater than is (Schroeppel 1972).

### Greatest prime factor

For an integer , let denote the greatest prime factor of , i.e., the number in the factorizationwith for . For , 3, ..., the first few are 2, 3, 2, 5, 3, 7, 2, 3, 5, 11, 3, 13, 7, 5, ... (OEIS A006530). The greatest multiple prime factors for squareful integers are 2, 2, 3, 2, 2, 3, 2, 2, 5, 3, 2, 2, 3, ... (OEIS A046028).A number for which is called an unusual number by Greene and Knuth (1990) and a -rough numbers by Finch (2001). The first few -rough numbers are 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 20, 21, ... (OEIS A064052). The probability that a random positive integer is -rough is (Schroeppel 1972).A number that is not -rough is called, not surprisingly, a -smooth number (or sometimes, a "round number"). The first few are 1, 4, 8, 9, 12, 16, 18, 24, 25, 27, ... (OEIS A048098)...

### Continued fraction factorization algorithm

A prime factorization algorithm which uses residues produced in the continued fraction of for some suitably chosen to obtain a square number. The algorithm solvesby finding an for which (mod ) has the smallest upper bound. The method requires (by conjecture) about steps, and was the fastest prime factorization algorithm in use before the quadratic sieve, which eliminates the 2 under the square root (Pomerance 1996), was developed.

### Fundamental theorem of arithmetic

The fundamental theorem of arithmetic states that every positive integer (except the number 1) can be represented in exactly one way apart from rearrangement as a product of one or more primes (Hardy and Wright 1979, pp. 2-3).This theorem is also called the unique factorization theorem. The fundamental theorem of arithmetic is a corollary of the first of Euclid's theorems (Hardy and Wright 1979).For rings more general than the complex polynomials , there does not necessarily exist a unique factorization. However, a principal ideal domain is a structure for which the proof of the unique factorization property is sufficiently easy while being quite general and common.

### Composite number problem

The composite number problem asks if for a given positive integer there exist positive integers and such that .The complexity of the composite number problem was unknown for many years, although the problem was known to belong to (Pratt 1975, Garey and Johnson 1983). Agrawal et al. (2004) subsequently and unexpectedly discovered a polynomial-time algorithm now known as the AKS primality test.

### Primitive prime factor

Given an integer sequence , a prime number is said to be a primitive prime factor of the term if divides but does not divide any for . It is possible for a term to have zero, one, or many primitive prime factors.For example, the prime factors of the sequence are summarized in the following table (OEIS A005529).prime factorizationprime factorsprimitive prime factors12222255553102, 54171717175262, 13136373737377502, 58655, 139822, 414110101101101101

### Prime signature

The prime signature of a positive integer is a sorted list of nonzero exponents in the prime factorizationBy definition, the prime signature of 1 is . The prime numbers have prime signature and squares of prime numbers have prime signature .The following table gives the prime signatures of the first few positive integers(OEIS A118914). factorizationprime signaturefactorizationprime signature11111122123313134145515616771717818919191020

### Fermat's factorization method

Given a number , Fermat's factorization methods look for integers and such that . Then(1)and is factored. A modified form of this observation leads to Dixon's factorization method and the quadratic sieve.Every positive odd integer can be represented in the form by writing (with ) and noting that this gives(2)(3)Adding and subtracting,(4)(5)so solving for and gives(6)(7)Therefore,(8)As the first trial for , try , where is the ceiling function. Then check if(9)is a square number. There are only 22 combinations of the last two digits which a square number can assume, so most combinations can be eliminated. If is not a square number, then try(10)so(11)(12)(13)(14)Continue with(15)(16)(17)(18)(19)so subsequent differences are obtained simply by adding two.Maurice Kraitchik sped up the algorithm by looking for and satisfying(20)i.e., . This congruence has uninteresting solutions and interesting solutions . It turns out that if is odd..

### Brent's factorization method

The second part of Pollard rho factorization method concerns detection of the fact that a sequence has become periodic. Pollard's original suggestion was to use the idea attributed to Floyd of comparing to for all . Brent's improvement to Pollard's method concerns how to detect periodicity, and replaces Floyd's method with the following algorithm. Keep only one running copy of . If is a power of a base , let , and at each step, compare the current value with the saved value . In the factorization case, instead of comparing with , computeMore generally, Brent (1980) considered using any base for saving values instead of . However, he found to be very close to optimal.

### Prime factor

A prime factor is a factor that is prime, i.e., one that cannot itself be factored. In general, a prime factorization takes the form(1)where are prime factors and are their orders. Prime factorization can be performed in the Wolfram Language using the command FactorInteger[n], which returns a list of pairs.The following table gives the prime factorization for the positive integers .1111112131314141221222324233131323233343434142434445515253545616263646771717273737474781828384891919292939491020304050The number of not necessarily distinct prime factors of a number is denoted (Hardy and Wright 1979, p. 354) or . Conway et al. (2008) coined the term "multiprimality of " to describe , with semiprimes then being termed biprimes, numbers with three factors terms triprimes, etc. The number of prime factors is given in terms of the prime factorization above by(2)The first few values for , 2, ... are 0, 1, 1, 2, 1, 2,..

### Aurifeuillean factorization

A factorization of the form(1)The factorization for was discovered by Aurifeuille, and the general form was subsequently discovered by Lucas. The large factors are sometimes written as and as follows:(2)(3)which can be written(4)(5)(6)where and(7)(8)(9)

### Pratt certificate

The Pratt certificate is a primality certificate based on Fermat's little theorem converse. Prior to the work of Pratt (1975), the Lucas-Lehmer test had been regarded purely as a heuristic that worked a lot of the time (Knuth 1969). Pratt (1975) showed that Lehmer's primality heuristic could be made a nondeterministic procedure by applying it recursively to the factors of . As a consequence of this result, Pratt (1975) became the first to demonstrate that the resulting tree implies that prime factorization lies in the complexity class NP.To generate a Pratt certificate, assume that is a positive integer and is the set of prime factors of . Suppose there exists an integer (called a "witness") such that but (mod ) whenever is one of . Then Fermat's little theorem converse states that is prime (Wagon 1991, pp. 278-279).By applying Fermat's little theorem converse to and recursively to each purported factor of , a certificate for..

### Almost prime

A number with prime factorizationis called -almost prime if it has a sum of exponents , i.e., when the prime factor (multiprimality) function .The set of -almost primes is denoted .The primes correspond to the "1-almost prime" numbers and the 2-almost prime numbers correspond to semiprimes. Conway et al. (2008) propose calling these numbers primes, biprimes, triprimes, and so on.Formulas for the number of -almost primes less than or equal to are given byand so on, where is the prime counting function and is the th prime (R. G. Wilson V, pers. comm., Feb. 7, 2006; the first of which was discovered independently by E. Noel and G. Panos around Jan. 2005, pers. comm., Jun. 13, 2006).The following table summarizes the first few -almost primes for small .OEIS-almost primes1A0000402, 3, 5, 7, 11, 13, ...2A0013584, 6, 9, 10, 14, 15, 21, 22, ...3A0146128, 12, 18, 20, 27, 28, 30, 42, 44, 45, 50, 52,..

### Prime constellation

A prime constellation, also called a prime -tuple, prime -tuplet, or prime cluster, is a sequence of consecutive numbers such that the difference between the first and last is, in some sense, the least possible. More precisely, a prime -tuplet is a sequence of consecutive primes (, , ..., ) with , where is the smallest number for which there exist integers , and, for every prime , not all the residues modulo are represented by , , ..., (Forbes). For each , this definition excludes a finite number of clusters at the beginning of the prime number sequence. For example, (97, 101, 103, 107, 109) satisfies the conditions of the definition of a prime 5-tuplet, but (3, 5, 7, 11, 13) does not because all three residues modulo 3 are represented (Forbes).A prime double with is of the form (, ) and is called a pair of twin primes. Prime doubles of the form (, ) are called cousin primes, and prime doubles of the form (, ) are called sexy primes.A prime triplet has . The constellation..

### Dirichlet's theorem

Given an arithmetic progression of terms , for , 2, ..., the series contains an infinite number of primes if and are relatively prime, i.e., . This result had been conjectured by Gauss (Derbyshire 2004, p. 96), but was first proved by Dirichlet (1837).Dirichlet proved this theorem using Dirichlet L-series, but the proof is challenging enough that, in their classic text on number theory, the usually explicit Hardy and Wright (1979) report "this theorem is too difficult for insertion in this book."

### Lucky number of euler

A lucky number of Euler is a number such that the prime-generating polynomialis prime for , 2, ..., . Such numbers are related to the imaginary quadratic field in which the ring of integers is factorable. Specifically, the lucky numbers of Euler (excluding the trivial case ) are those numbers such that the imaginary quadratic field has class number 1 (Rabinowitz 1913, Le Lionnais 1983, Conway and Guy 1996, Ribenboim 2000).As proved by Heegner (1952)--although his proof was not accepted as complete at the time--and subsequently established by Stark (1967), there are only nine numbers such that (the Heegner numbers , , , , , , , and ), and of these, only 7, 11, 19, 43, 67, and 163 are of the required form. Therefore, the only lucky numbers of Euler are 2, 3, 5, 11, 17, and 41 (Le Lionnais 1983, OEIS A014556), and there does not exist a better prime-generating polynomial of Euler's form...

### Twin prime cluster

A twin prime cluster of order is a collection of consecutive prime numbers such that consecutive pairs form twin primes. Twin prime clusters were discussed by Mudge (around 1995), and N. D. Backhouse found such a cluster of order 7. The smallest twin prime clusters of order , 2, ... are 3, 5, 5, 9419, 909287, 325267931, 678771479, 1107819732821, 170669145704411, 3324648277099157, ... (OEIS A111950). The cluster of order 7 was found by P. Carmody on Jan. 7, 2001, the cluster of order 8 was found by DeVries (2001), the cluster of order 9 by DeVries (2002), and the cluster of order 10 by G. Levai (in Sept. 2004, pers. comm., Apr. 5, 2005).

### Cluster prime

An odd prime is called a cluster prime if every even positive integer less than can be written as a difference of two primes , where . The first 23 odd primes 3, 5, 7, ..., 89 are all cluster primes. The first few odd primes that are not cluster primes are 97, 127, 149, 191, 211, ... (OEIS A038133).The numbers of cluster primes less than , , ... are 23, 99, 420, 1807, ... (OEIS A039506), and the corresponding numbers of noncluster primes are 0, 1, 68, 808, 7784, ... (OEIS A039507). It is not known if there are infinitely many cluster primes, but Blecksmith et al. (1999) show that for every positive integer , there is a bound such that if , thenwhere is the number of cluster primes not exceeding . Blecksmith et al. (1999) also show that the sum of the reciprocals of the cluster primes is finite...

A prime constellation of four successive primes with minimal distance . The term was coined by Paul Stäckel (1892-1919; Tietze 1965, p. 19). The quadruplet (2, 3, 5, 7) has smaller minimal distance, but it is an exceptional special case. With the exception of (5, 7, 11, 13), a prime quadruple must be of the form (, , , ). The first few values of which give prime quadruples are , 3, 6, 27, 49, 62, 69, 108, 115, ... (OEIS A014561), and the first few values of are 5 (the exceptional case), 11, 101, 191, 821, 1481, 1871, 2081, 3251, 3461, ... (OEIS A007530). The number of prime quadruplets with largest member less than , , ..., are 1, 2, 5, 12, 38, 166, 899, 4768, ... (OEIS A050258; Nicely 1999).The asymptotic formula for the frequency of prime quadruplesis analogous to that for other prime constellations,(1)(2)where (OEIS A061642) is the Hardy-Littlewood constant for prime quadruplets.Roonguthai found the large prime quadruplets with(3)(4)(5)(6)(7)(8)(9)Forbes..

### Pocklington's criterion

Let be an odd prime, be an integer such that and , andThen the following are equivalent 1. is prime. 2. There exists an such that , where GCD is the greatest common divisor (i.e., and are relatively prime). This is a modified version of the original theorem due to Lehmer.

### Ward's primality test

Let be an odd integer, and assume there exists a Lucas sequence with associated Sylvester cyclotomic numbers such that there is an (with and relatively prime) for which divides . Then is a prime unless it has one of the following two forms: 1. , with prime and , or 2. , with and prime.

### P&eacute;pin's test

A test for the primality of Fermat numbers , with and . Then the two following conditions are equivalent: 1. is prime and , where is the Jacobi symbol, 2. . is usually taken as 3 as a first test.

### Compositeness certificate

A compositeness certificate is a piece of information which guarantees that a given number is composite. Possible certificates consist of a factor of a number (which, in general, is much quicker to check by direct division than to determine initially), or of the determination that either(i.e., violates Fermat's little theorem), orA quantity satisfying either property is said to be a witness to 's compositeness.

### Miller's primality test

If a number fails Miller's primality test for some base , it is not a prime. If the number passes, it may be a prime. A composite number passing Miller's test is called a strong pseudoprime to base . If a number does not pass the test, then it is called a witness for the compositeness. If is an odd, positive composite number, then passes Miller's test for at most bases with (Long 1995). There is no analog of Carmichael numbers for strong pseudoprimes.The smallest numbers that are strong pseudoprimes to base 2, 3, 5, and 7 (and would hence fail a test based on these bases) are 3215031751, 118670087467, 307768373641, 315962312077, ... (OEIS A074773; Jaeschke 1993).Miller showed that any composite has a witness less than if the Riemann hypothesis is true.

### Proth's theorem

For with odd and , if there exists an integer such thatthen is prime. A prime of this form is known as a Proth prime.

### Aks primality test

In August 2002, M. Agrawal and colleagues announced a deterministic algorithm for determining if a number is prime that runs in polynomial time (Agrawal et al. 2004). While this had long been believed possible (Wagon 1991), no one had previously been able to produce an explicit polynomial time deterministic algorithm (although probabilistic algorithms were known that seem to run in polynomial time). This test is now known as the Agrawal-Kayal-Saxena primality test, cyclotomic AKS test, or AKS primality test.Commenting on the impact of this discovery, P. Leyland noted, "One reason for the excitement within the mathematical community is not only does this algorithm settle a long-standing problem, it also does so in a brilliantly simple manner. Everyone is now wondering what else has been similarly overlooked" (quoted by Crandall and Papadopoulos 2003).The complexity of the original algorithm of Agrawal et al...

### Primality test

A primality test is a test to determine whether or not a given number is prime, as opposed to actually decomposing the number into its constituent prime factors (which is known as prime factorization).Primality tests come in two varieties: deterministic and probabilistic. Deterministic tests determine with absolute certainty whether a number is prime. Examples of deterministic tests include the Lucas-Lehmer test and elliptic curve primality proving. Probabilistic tests can potentially (although with very small probability) falsely identify a composite number as prime (although not vice versa). However, they are in general much faster than deterministic tests. Numbers that have passed a probabilistic prime test are therefore properly referred to as probable primes until their primality can be demonstrated deterministically.A number that passes a probabilistic test but is in fact composite is known as a pseudoprime. There are..

### Euler's criterion

For an odd prime and a positive integer which is not a multiple of ,where is the Legendre symbol.

### Pocklington's theorem

Let where is the factored part of a number(1)where , and .Pocklington's theorem, also known as the Pocklington-Lehmer test, then says that if there exists a for , ..., such that(2)and(3)then is prime.

### Supersingular prime

There are two definitions of the supersingular primes: one group-theoretic, and the other number-theoretic.Group-theoretically, let be the modular group Gamma0, and let be the compactification (by adding cusps) of , where is the upper half-plane. Also define to be the Fricke involution defined by the block matrix . For a prime, define . Then is a supersingular prime if the genus of .The number-theoretic definition involves supersingular elliptic curves defined over the algebraic closure of the finite field . They have their j-invariant in .Supersingular curves were mentioned by Charlie the math genius in the Season 2 episode "In Plain Sight" of the television crime drama NUMB3RS.There are exactly 15 supersingular primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 47, 59, and 71 (OEIS A002267). The supersingular primes are exactly the set of primes that divide the group order of the Monster group...

### Even prime

The unique even prime number 2. All other primes are odd primes. Humorously, that means 2 is the "oddest" prime of all.The sequence 2, 4, 6, 10, 14, 22, 26, 34, 38, ... (OEIS A001747) consisting of the number 2 together with the primes multiplied by 2 is sometimes also called the even primes, since these are the even numbers that are divisible by just 1, 2, , and .

### Circular prime

A prime number is called circular if it remains prime after any cyclic permutation of its digits. An example in base-10 is because , , and are all primes. The first few circular primes are 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 113, 131, 197, ... (OEIS A068652).Base-10 circular primes not contain any digit 0, 2, 4, 5, 6, or 8, since having such a digit in the units place yields a number which is necessarily divisible by either or (and therefore not prime).Every prime repunit is a circular prime.Circular primes are rare. Including only the smallest number corresponding to each cycle gives the sequence 2, 3, 5, 7, 11, 13, 17, 37, 79, 113, 197, 199, 337, 1193, 3779, 11939, 19937, 193939, 199933, ... (OEIS A016114; Darling 2004), together with repunits , , , , , , and (the last several of which are probable primes)...

### Riemann prime counting function

Riemann defined the function by(1)(2)(3)(Hardy 1999, p. 30; Borwein et al. 2000; Havil 2003, pp. 189-191 and 196-197; Derbyshire 2004, p. 299), sometimes denoted , (Edwards 2001, pp. 22 and 33; Derbyshire 2004, p. 298), or (Havil 2003, p. 189). Note that this is not an infinite series since the terms become zero starting at , and where is the floor function and is the base-2 logarithm. For , 2, ..., the first few values are 0, 1, 2, 5/2, 7/2, 7/2, 9/2, 29/6, 16/3, 16/3, ... (OEIS A096624 and A096625). As can be seen, when is a prime, jumps by 1; when it is the square of a prime, it jumps by 1/2; when it is a cube of a prime, it jumps by 1/3; and so on (Derbyshire 2004, pp. 300-301), as illustrated above.Amazingly, the prime counting function is related to by the Möbius transform(4)where is the Möbius function (Riesel 1994, p. 49; Havil 2003, p. 196; Derbyshire 2004, p. 302). More amazingly..

### Explicit formula

The so-called explicit formulagives an explicit relation between prime numbers and Riemann zeta function zeros for and not a prime or prime power. Here, is the summatory Mangoldt function (also known as the second Chebyshev function), and the second sum is over all nontrivial zeros of the Riemann zeta function , i.e., those in the critical strip so (Montgomery 2001).

### Sum of prime factors

Let be the sum of prime factors (with repetition) of a number . For example, , so . Then for , 2, ... is given by 0, 2, 3, 4, 5, 5, 7, 6, 6, 7, 11, 7, 13, 9, 8, ... (OEIS A001414). The sum of prime factors function is also known as the integer logarithm.The high-water marks are 0, 2, 3, 4, 5, 7, 11, 13, 17, ..., which occur at positions 1, 2, 3, 4, 5, 7, 11, 13, 17, ... (OEIS A046022), which, with the exception of the first term, correspond exactly to the actual values of the high-water marks.If is considered to be 0 for a prime, then the sequence of high-water marks is 0, 4, 5, 6, 7, 9, 10, 13, 15, 19, 21, 25, 31, 33, ... (OEIS A088685), which occur at positions 1, 4, 6, 8, 10, 14, 21, 22, 26, 34, 38, 46, 58, ... (OEIS A088686). Rather amazingly, if the first 7 terms are dropped, then the last digit of the high-water marks and the last digit of their positions fall into one of the four patterns , (3, 2), (5, 6), or (9, 4) (A. Jones, pers. comm., October 5, 2003).Now consider iterating..

### Prime representation

Let , , and denote positive integers satisfying(i.e., both pairs are relatively prime), and suppose every prime with is expressible if the form for some integers and . Then every prime such that and is expressible in the form for some integers and (Halter-Koch 1993, Williams 1991).prime formrepresentation

### Prime sums

Let(1)be the sum of the first primes (i.e., the sum analog of the primorial function). The first few terms are 2, 5, 10, 17, 28, 41, 58, 77, ... (OEIS A007504). Bach and Shallit (1996) show that(2)and provide a general technique for estimating such sums.The first few values of such that is prime are 1, 2, 4, 6, 12, 14, 60, 64, 96, 100, ... (OEIS A013916). The corresponding values of are 2, 5, 17, 41, 197, 281, 7699, 8893, 22039, 24133, ... (OEIS A013918).The first few values of such that are 1, 23, 53, 853, 11869, 117267, 339615, 3600489, 96643287, ... (OEIS A045345). The corresponding values of are 2, 874, 5830, 2615298, 712377380, 86810649294, 794712005370, 105784534314378, 92542301212047102, ... (OEIS A050247; Rivera), and the values of are 2, 38, 110, 3066, 60020, 740282, 2340038, 29380602, 957565746, ... (OEIS A050248; Rivera).In 1737, Euler showed that the harmonic seriesof primes, (i.e., sum of the reciprocals of the primes) diverges(3)(Nagell..

### Fermat's 4n+1 theorem

Fermat's theorem, sometimes called Fermat's two-square theorem or simply "Fermat's theorem," states that a prime number can be represented in an essentially unique manner (up to the order of addends) in the form for integer and iff or (which is a degenerate case with ). The theorem was stated by Fermat, but the first published proof was by Euler.The first few primes which are 1 or 2 (mod 4) are 2, 5, 13, 17, 29, 37, 41, 53, 61, ... (OEIS A002313) (with the only prime congruent to 2 mod 4 being 2). The numbers such that equal these primes are (1, 1), (1, 2), (2, 3), (1, 4), (2, 5), (1, 6), ... (OEIS A002331 and A002330).The theorem can be restated by lettingthen all relatively prime solutions to the problem of representing for any integer are achieved by means of successive applications of the genus theorem and composition theorem...

### Sierpi&324;ski's prime sequence theorem

For any , there exists a such that the sequencewhere , 2, ... contains at least primes.

### Euler's 6n+1 theorem

Euler's theorem states that every prime of the form , (i.e., 7, 13, 19, 31, 37, 43, 61, 67, ..., which are also the primes of the form ; OEIS A002476) can be written in the form with and positive integers.The first few positive integers that can be represented in this form (with ) are 4, 7, 12, 13, 16, 19, ... (OEIS A092572), summarized in the following table together with their representations.4(1, 1)7(2, 1)12(3, 1)13(1, 2)16(2, 2)19(4, 1)21(3, 2)28(1, 3), (4, 2), (5, 1)31(2, 3)Restricting solutions such that (i.e., and are relatively prime), the numbers that can be represented as are 4, 7, 12, 13, 19, 21, 28, 31, 37, 39, 43, ... (OEIS A092574), as summarized in the following table. with 4(1, 1)7(2, 1)12(3, 1)13(1, 2)19(4, 1)21(3, 2)28(1, 3), (5, 1)31(2, 3)37(5, 2)

### Schnirelmann's theorem

There exists a positive integer such that every sufficiently large integer is the sum of at most primes. It follows that there exists a positive integer such that every integer is a sum of at most primes. The smallest proven value of is known as the Schnirelmann constant.Schnirelmann's theorem can be proved using Mann's theorem,although Schnirelmann used the weaker inequalitywhere , , and is the Schnirelmann density. Let be the set of primes, together with 0 and 1, and let . Using a sophisticated version of the inclusion-exclusion principle, Schnirelmann showed that although , . By repeated applications of Mann's theorem, the sum of copies of satisfies . Thus, if , the sum of copies of has Schnirelmann density 1, and so contains all positive integers.

### Choquet theory

Erdős proved that there exist at least one prime of the form and at least one prime of the form between and for all .

### Chen's theorem

Every "large" even number may be written as where is a prime and is the set of primes and semiprimes .

### Chebyshev's theorem

There are at least two theorems known as Chebyshev's theorem.The first is Bertrand's postulate, proposed by Bertrand in 1845 and proved by Chebyshev using elementary methods in 1850 (Derbyshire 2004, p. 124).The second is a weak form of the prime number theorem stating that the order of magnitude of the prime counting function iswhere denotes "is asymptotic to" (Hardy and Wright 1979, p. 9). More precisely, Chebyshev showed in 1849 that iffor some constant , then (Derbyshire 2004, p. 123).

### Double wieferich prime pair

A pair of prime numbers such thatThe only known examples are (2, 1093), (3, 1006003), (5 , 1645333507), (83, 4871), (911, 318917), and (2903, 18787).If the equation of Catalan's Diophantineproblemhas a nontrivial solution in integers and primes greater than 3, then must be a double Wieferich pair, as proved in 2000 by Mihailescu (Steiner 1998, Peterson 2000).

### Mills' prime

Mills' constant can be defined as the least such thatis prime for all positive integers (Caldwell and Cheng 2005).The first few for , 2, ... are 2, 11, 1361, 2521008887, ... (OEIS A051254). They can be represented more compactly through as andCaldwell and Cheng (2005) calculated the first 10 Mills primes. 13 are known as of Jul. 2013, with the firth few for , 2, ... being 3, 30, 6, 80, 12, 450, 894, 3636, 70756, 97220, 66768, 300840, ... (OEIS A108739). is not known, but it is known that (E. Weisstein, Aug. 13, 2013).The integer lengths of the Mills' primes are 1, 2, 4, 10, 29, 85, 254, 762, 2285,6854, 20562, 61684, 185052, ... (OEIS A224845).

### Dihedral prime

A number such that the "LED representation" of (i.e., the arrangement of horizonal and vertical lines seen on a digital clock or pocket calculator), upside down, in a mirror, and upside-down-and-in-a-mirror are all primes. The digits of are therefore restricted to 0, 1, 2, 5, and 8. The first few dihedral primes are 2, 5, 11, 101, 181, 1181, 1811, 18181, 108881, 110881, 118081, 120121, ... (OEIS A134996).

### Interprime

An interprime is the average of consecutive (but not necessarily twin) odd primes. The first few terms are 4, 6, 9, 12, 15, 18, 21, 26, 30, 34, ... (OEIS A024675). The first few even interprimes are 4, 6, 12, 18, 26, 30, 34, 42, 50, 56, 60, ... (OEIS A072568), and the first few odd ones are 9, 15, 21, 39, 45, 69, 81, 93, 99, ... (OEIS A072569).Interprimes cannot themselves be prime (since otherwise there would exist a prime between consecutive primes, which is impossible by definition).The sumhas zeros at almost integer approximations of the interprimes, with the single additional point 5/2 (D. Tisdale, pers. comm., Sep. 8, 2008).

### Good prime

A prime is called "good" iffor all (there is a typo in Guy 1994 in which the s are replaced by 1s). There are infinitely many good primes, and the first few are 5, 11, 17, 29, 37, 41, 53, ... (OEIS A028388).

### Regular prime

A prime which does not divide the class number of the cyclotomic field obtained by adjoining a primitive pth root of unity to the field of rationals. A prime is regular iff does not divide the numerators of the Bernoulli numbers , , ..., . A prime which is not regular is said to be an irregular prime.In 1915, Jensen proved that there are infinitely many irregular primes. It has not yet been proven that there are an infinite number of regular primes (Guy 1994, p. 145). Of the primes , (or 60.59%) are regular (the conjectured fraction is ). The first few are 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 43, 47, ... (OEIS A007703).

### Proth prime

A Proth number that is prime, i.e., a number of the form for odd , a positive integer, and . Factors of Fermat numbers are of this form as long as they satisfy the condition odd and . For example, the factor of is not a Proth prime since . (Otherwise, every odd prime would be a Proth prime.)Proth primes satisfy Proth's theorem, i.e., a number of this form is prime iff there exists a number a such that is congruent to modulo . This provides an easy computational test for Proth primes. Yves Gallot has written a downloadable program for testing Proth primes and many of the largest currently known primes have been found with this program.A Sierpiński number of the second kind is a number satisfying Sierpiński's composite number theorem, i.e., a Proth number such that is composite for every .The first few Proth primes are 3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, ...(OEIS A080076).The following table gives the first few indices such that is prime for..

### Wilson quotient

The quotientwhich must be congruent to 0 (mod ) for to be a Wilson prime. The quotient is an integer only when (in which case ) or is a prime, and the values of corresponding to , 3, 5, 7, 11, ... are 1, 1, 5, 103, 329891, 36846277, 1230752346353, ... (OEIS A007619).

### Mann's theorem

Mann's theorem is a theorem widely circulated as the " conjecture" that was subsequently proven by Mann (1942). It states that if and are sets of integers each containing 0, thenHere, denotes the direct sum, i.e., , and is the Schnirelmann density.Mann's theorem is optimal in the sense that satisfies .Mann's theorem implies Schnirelmann's theorem as follows. Let , then Mann's theorem proves that , so as more and more copies of the primes are included, the Schnirelmann density increases at least linearly, and so reaches 1 with at most copies of the primes. Since the only sets with Schnirelmann density 1 are the sets containing all positive integers, Schnirelmann's theorem follows.

### Vandiver's criteria

Let be an irregular prime, and let be a prime with . Also let be an integer such that (mod ). For an irregular pair , form the product(1)where(2)(3)If (mod ) for all such irregular pairs, then Fermat's last theorem holds for exponent .

### Chebyshev bias

Chebyshev noticed that the remainder upon dividing the primes by 4 gives 3 more often than 1, as plotted above in the left figure. Similarly, dividing the primes by 3 gives 2 more often than 1 (right figure). This is called the Chebyshev bias, or sometimes the prime race (Wagon 1994).Consider the list of the first primes (mod 4). This list contains equal numbers of remainders 3 and 1 (mod 4) for , 3, 7, 13, 89, 2943, 2945, 2947, 2949, 2951, 2953, 50371, ... (OEIS A038691; Wagon 1994, pp. 2-3). The values of for which the list is biased towards 1 are 2946, 50378, 50380, 50382, 50383, 50384, 50385, ... (OEIS A096628).Definingthe values of for which are , 3, 7, 13, 89, 2943, 2945, 2947, ... (OEIS A038691).Similarly, consider the list of the first primes (mod 3), skipping and since . This list contains equal numbers of remainders 2 and 1 at the values , 6, 8, 12, 14, 22, 38, 48, 50, ... (OEIS A096629). The first value of for which the list is biased towards 1 is , as..

### Pierpont prime

A Pierpont prime is a prime number of the form . The first few Pierpont primes are 2, 3, 5, 7, 13, 17, 19, 37, 73, 97, 109, 163, 193, 257, 433, 487, 577, 769, ... (OEIS A005109).A regular polygon of sides can be constructed by ruler, compass and angle-trisector iffwhere , , ..., are distinct Pierpont primes and (Gleason 1998).The numbers of Pierpont primes less than , , ... are 4, 10, 18, 25, 32, 42, 50, 58, ... (OEIS A113420) and the number less than , , , , ... are 4, 10, 25, 58, 125, 250, 505, 1020, 2075, 4227, ... (OEIS A113412; Caldwell).As of Apr. 2010, the largest known Pierpont prime is , which has decimal digits (https://primes.utm.edu/primes/page.php?id=87449).

### Fortunate prime

Consider the Euclid numbers defined bywhere is the th prime and is the primorial. The first few values of are 3, 7, 31, 211, 2311, 30031, 510511, ... (OEIS A006862).Now let be the next prime (i.e., the smallest prime greater than ),where is the prime counting function. The first few values of are 5, 11, 37, 223, 2333, 30047, 510529, ... (OEIS A035345).Then R. F. Fortune conjectured that is prime for all . The first values of are 3, 5, 7, 13, 23, 17, 19, 23, ... (OEIS A005235), and values of up to are indeed prime (Guy 1994), a result extended to 1000 by E. W. Weisstein (Nov. 17, 2003). The indices of these primes are 2, 3, 4, 6, 9, 7, 8, 9, 12, 18, .... In numerical order with duplicates removed, the Fortunate primes are 3, 5, 7, 13, 17, 19, 23, 37, 47, 59, 61, 67, 71, 79, 89, ... (OEIS A046066)...

### Twin prime conjecture

There are two related conjectures, each called the twin prime conjecture. The first version states that there are an infinite number of pairs of twin primes (Guy 1994, p. 19). It is not known if there are an infinite number of such primes (Wells 1986, p. 41; Shanks 1993, p. 30), but it seems almost certain to be true. While Hardy and Wright (1979, p. 5) note that "the evidence, when examined in detail, appears to justify the conjecture," and Shanks (1993, p. 219) states even more strongly, "the evidence is overwhelming," Hardy and Wright also note that the proof or disproof of conjectures of this type "is at present beyond the resources of mathematics."Arenstorf (2004) published a purported proof of the conjecture (Weisstein 2004). Unfortunately, a serious error was found in the proof. As a result, the paper was retracted and the twin prime conjecture remains fully open.The conjecture..

### Eberhart's conjecture

If is the th prime such that is a Mersenne prime, thenIt was modified by Wagstaff (1983) to yield Wagstaff'sconjecture,where is the Euler-Mascheroni constant.

### Levy's conjecture

Levy (1963) noted that(1)(2)and from this observation, conjectured that all odd numbers are the sum of a prime plus twice a prime. This conjecture is a stronger version of the weak Goldbach conjecture and has been verified up to (Corbit 1999).The number of ways to express as for and primes and , 2, ... are 0, 0, 0, 1, 2, 2, 2, 2, 4, 2, 3, 3, 3, 4, 4, ... (OEIS A046927).

### Lehmer's totient problem

Lehmer's totient problem asks if there exist any composite numbers such that , where is the totient function? No such numbers are known. However, any such an would need to be a Carmichael number, since for every element in the integers (mod ), , so and is a Carmichael number.In 1932, Lehmer showed that such an must be odd and squarefree, and that the number of distinct prime factors must satisfy . This was subsequently extended to . The best current result is and , improving the lower bound of Cohen and Hagis (1980) since there are no Carmichael numbers less than having distinct prime factors; Pinch). However, even better results are known in the special cases , in which case (Wall 1980), and , in which case and (Lieuwens 1970).

### Cram&eacute;r conjecture

The Cramér conjecture is the unproven conjecturethatwhere is the th prime.

### Legendre's conjecture

Legendre's conjecture asserts that for every there exists a prime between and (Hardy and Wright 1979, p. 415; Ribenboim 1996, pp. 397-398). It is one of Landau's problems.Although it is not known if there always exists a prime between and , Chen (1975) has shown that a number which is either a prime or semiprime does always satisfy this inequality. Moreover, there is always a prime between and where (Iwaniec and Pintz 1984; Hardy and Wright 1979, p. 415).The smallest primes between and for , 2, ..., are 2, 5, 11, 17, 29, 37, 53, 67, 83, ... (OEIS A007491). The numbers of primes between and for , 2, ... are given by 2, 2, 2, 3, 2, 4, 3, 4, ... (OEIS A014085).

### Sierpi&324;ski's composite number theorem

As proved by Sierpiński (1960), there exist infinitely many positive odd numbers such that is composite for every . Numbers with this property are called Sierpiński numbers of the second kind, and analogous numbers with the plus sign replaced by a minus are called Riesel numbers. It is conjectured that the smallest value of for a Sierpiński number of the second kind is (although a handful of smaller candidates remain to be eliminated) and that the smallest Riesel number is .

### Brocard's conjecture

Brocard's conjecture states thatfor , where is the prime counting function and is the th prime. For , 2, ..., the first few values are 2, 5, 6, 15, 9, 22, 11, 27, 47, 16, ... (OEIS A050216).

### Shanks' conjecture

Let be the first prime which follows a prime gap of between consecutive primes. Shanks' conjecture holds thatWolf conjectures a slightly different formwhich agrees better with numerical evidence.

### Selfridge's conjecture

There exist infinitely many with for all , where is the th prime. Also, there exist infinitely many such that for all .

### Andrica's conjecture

Andrica's conjecture states that, for the th prime number, the inequalityholds, where the discrete function is plotted above. The high-water marks for occur for , 2, and 4, with , with no larger value among the first primes. Since the Andrica function falls asymptotically as increases, a prime gap of ever increasing size is needed to make the difference large as becomes large. It therefore seems highly likely the conjecture is true, although this has not yet been proven. bears a strong resemblance to the prime difference function, plotted above, the first few values of which are 1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6, ... (OEIS A001223).A generalization of Andrica's conjecture considers the equationand solves for . The smallest such is (OEIS A038458), known as the Smarandache constant, which occurs for and (Perez)...

### Abc conjecture

The abc conjecture is a conjecture due to Oesterlé and Masser in 1985. It states that, for any infinitesimal , there exists a constant such that for any three relatively prime integers , , satisfying(1)the inequality(2)holds, where indicates that the product is over primes which divide the product . If this conjecture were true, it would imply Fermat's last theorem for sufficiently large powers (Goldfeld 1996). This is related to the fact that the abc conjecture implies that there are at least non-Wieferich primes for some constant (Silverman 1988, Vardi 1991).The conjecture can also be stated by defining the height and radical of the sum as(3)(4)where runs over all prime divisors of , , and . Then the abc conjecture states that for all , there exists a constant such that for all ,(5)(van Frankenhuysen 2000). van Frankenhuysen (2000) has shown that there exists an infinite sequence of sums or rational integers with large height compared..

### Grimm's conjecture

Grimm conjectured that if , , ..., are all composite numbers, then there are distinct primes such that for .

### Giuga's conjecture

If andis necessarily a prime? In other words, definingdoes there exist a composite such that ? It is known that iff for each prime divisor of , and (Giuga 1950, Borwein et al. 1996); therefore, any counterexample must be squarefree. A composite integer satisfies iff it is both a Carmichael number and a Giuga number. Giuga showed that there are no exceptions to the conjecture up to . This was later improved to (Bedocchi 1985) and (Borwein et al. 1996).Kellner (2002) provided a short proof of the equivalence of Giuga's and Agoh'sconjectures. The combined conjecture can be described by a sum of fractions.

### Wagstaff's conjecture

A modification of the Eberhart's conjecture proposed by Wagstaff (1983) which proposes that if is the th prime such that is a Mersenne prime, thenwhere is the Euler-Mascheroni constant.

### Dickman function

The probability that a random integer between 1 and will have its greatest prime factor approaches a limiting value as , where for and is defined through the integral equation(1)for (Dickman 1930, Knuth 1998), which is almost (but not quite) a homogeneous Volterra integral equation of the second kind. The function can be given analytically for by(2)(3)(4)(Knuth 1998).Amazingly, the average value of such that is(5)(6)(7)(8)(9)which is precisely the Golomb-Dickman constant , which is defined in a completely different way!The Dickman function can be solved numerically by converting it to a delay differential equation. This can be done by noting that will become upon multiplicative inversion, so define to obtain(10)Now change variables under the integral sign by defining(11)(12)so(13)Plugging back in gives(14)To get rid of the s, define , so(15)But by the first fundamental theoremof calculus,(16)so differentiating both sides of equation..

### Riemann function

There are a number of functions in various branches of mathematics known as Riemann functions. Examples include the Riemann P-series, Riemann-Siegel functions, Riemann theta function, Riemann zeta function, xi-function, the function obtained by Riemann in studying Fourier series, the function appearing in the application of the Riemann method for solving the Goursat problem, the Riemann prime counting function , and the related the function obtained by replacing with in the Möbius inversion formula.The Riemann function for a Fourier series(1)is obtained by integrating twice term by term to obtain(2)where and are constants (Riemann 1957; Hazewinkel 1988, vol. 8, p. 118).The Riemann function arises in the solution of the linear case of the Goursat problem of solving the hyperbolic partial differential equation(3)with boundary conditions(4)(5)(6)Here, is defined as the solution of the equation(7)which satisfies..

Let denote the number of primes which are congruent to modulo (i.e., the modular prime counting function). Then one might expect that(Berndt 1994).Although this is true for small numbers, Hardy and Littlewood showed that changes sign infinitely often. The effect was first noted by Chebyshev in 1853, and is sometimes called the Chebyshev phenomenon. It was subsequently studied by Shanks (1959), Hudson (1980), and Bays and Hudson (1977, 1978, 1979). The effect was also noted by Ramanujan, who incorrectly claimed that (Berndt 1994).The bias of the sign of is known as the Chebyshev bias.

### Modular prime counting function

By way of analogy with the prime counting function , the notation denotes the number of primes of the form less than or equal to (Shanks 1993, pp. 21-22).Hardy and Littlewood proved that an switches leads infinitely often, a result known as the prime quadratic effect. The bias of the sign of is known as the Chebyshev bias.Groups of equinumerous values of include (, ), (, ), (, , , ), (, ), (, , , , , ), (, , , ), (, , , , , ), and so on. The values of for small are given in the following table for the first few powers of ten (Shanks 1993).SloaneA091115A091116A091098A09109912121113111380878087611617609619478448074783480839231392663917539322332194332384332180332398288051728809372880504288095025422713254248202542349125424042SloaneA091115A0911191111128086611616478448063923139265332194332383288051728809362542271325424819SloaneA091120A091121A091122A091123A091124A091125011010345354282730262927203203209202211200159315841613160116041596130631306513105130691310513090110653110771110815110776110787110776960023960114960213960085960379960640847422184747968475123847402184746308474742SloaneA091126A091127A091128A0911290111576637444343295311314308238424092399239919552196531962319669165976166161166204166237143997014405441440534144040612711220127123401271227112711702Note..

### Meissel's formula

A modification of Legendre's formula for the prime counting function . It starts with(1)where is the floor function, is the number of integers with , and is the number of integers with , and so on.Identities satisfied by the s include(2)for and(3)(4)Meissel's formula is(5)where(6)(7)Taking the derivation one step further yields Lehmer'sformula.

### Mapes' method

A method for computing the prime counting function.Define the function(1)where is the floor function and the are the binary digits (0 or 1) in(2)Legendre's formula can then be written(3)The first few values of are(4)(5)(6)(7)(8)(9)(10)(11)Mapes' method takes time , which is slightly faster than the Lehmer-Schur method.

### Lehmer's formula

Lehmer's formula is a formula for the primecounting function,(1)where is the floor function,(2)(3)(4)(5)and is the prime counting function. It is related to Meissel's formula.

### Legendre's formula

Legendre's formula counts the number of positive integers less than or equal to a number which are not divisible by any of the first primes,(1)where is the floor function. Taking , where is the prime counting function, gives(2)Legendre's formula holds since one more than the number of primes in a range equals the number of integers minus the number of composites in the interval.Legendre's formula satisfies the recurrence relation(3)Let , then(4)(5)(6)(7)(8)where is the totient function, and(9)where . If , then(10)Note that is not practical for computing for large arguments. A more efficient modification is Meissel's formula.

### Gram series

The Gram series is an approximation to the primecounting function given by(1)where is the Riemann zeta function (Hardy 1999, p. 24). This approximation is 10 times better than for but has been proven to be worse infinitely often by Littlewood (Ingham 1990).The Gram series is equivalent to the Riemannprime counting function (Hardy 1999, pp. 24-25)(2)where is the logarithmic integral and is the Möbius function (Hardy 1999, pp. 16 and 23; Borwein et al. 2000), but is much more tractable for numeric computations. For example, the plots above show the difference where is computed using the Wolfram Language's built-in NSum command (black) and approximated using the first (blue), (green), (yellow), (orange), and (red) points.A related series due to Ramanujan is(3)(4)(5)(6)(Berndt 1994, p. 124; Hardy 1999, p. 23), where is a Bernoulli number. The integral analog, also found by Ramanujan, is(7)(Berndt..

### Chebyshev functions

The two functions and defined below are known as the Chebyshev functions.The function is defined by(1)(2)(3)(Hardy and Wright 1979, p. 340), where is the th prime, is the prime counting function, and is the primorial. This function has the limit(4)and the asymptotic behavior(5)(Bach and Shallit 1996; Hardy 1999, p. 28; Havil 2003, p. 184). The notation is also commonly used for this function (Hardy 1999, p. 27).The related function is defined by(6)(7)where is the Mangoldt function (Hardy and Wright 1979, p. 340; Edwards 2001, p. 51). Here, the sum runs over all primes and positive integers such that , and therefore potentially includes some primes multiple times. A simple and beautiful formula for is given by(8)i.e., the logarithm of the least common multiple of the numbers from 1 to (correcting Havil 2003, p. 184). The values of for , 2, ... are 1, 2, 6, 12, 60, 60, 420, 840, 2520, 2520, ... (OEIS A003418;..

### Colbert number

A Colbert number is any prime number with more than decimal digits whose discovery contributes to the long-sought after proof that is the smallest Sierpiński number of the second kind. Colbert Numbers are named to honor Stephen T. Colbert.There are currently five known Colbert numbers, as summarized in the following table.Colbert numberdecimal digits15215613918990275967723572072116617The Seventeen or Bust distributed computing effort is conducting a search for the remaining six Colbert numbers (where indicates the exponent is unknown).unknown Colbert numberdecimal digits??????

### Rosser's theorem

The prime number theorem shows that the th prime number has the asymptotic value(1)as (Havil 2003, p. 182). Rosser's theorem makes this a rigorous lower bound by stating that(2)for (Rosser 1938). This result was subsequently improved to(3)where (Rosser and Schoenfeld 1975). The constant was subsequently reduced to (Robin 1983). Massias and Robin (1996) then showed that was admissible for and . Finally, Dusart (1999) showed that holds for all (Havil 2003, p. 183). The plots above show (black), (blue), and (red).The difference between and is plotted above. The slope of the difference taken out to is approximately .

### Mertens' second theorem

Mertens' second theorem states that the asymptotic form of the harmonic series for the sum of reciprocal primes is given bywhere is a prime, is a constant known as the Mertens constant, and is a Landau symbol.

### Legendre's constant

Legendre's constant is the number 1.08366 in Legendre's guess at the primenumber theoremwith . Legendre first published a guess the formin his Essai sur la Théorie des Nombres (Edwards 2001, p. 3; Havil 2003, p. 177), but in the third edition (renamed Théorie des nombres), modified it to the form above (Derbyshire 2004, pp. 55 and 369).This expression is correct to leading term only, since it is actually true that this limit approaches 1 (Rosser and Schoenfeld 1962, Panaitopol 1999).

### Unique prime

Following Yates (1980), a prime such that is a repeating decimal with decimal period shared with no other prime is called a unique prime. For example, 3, 11, 37, and 101 are unique primes, since they are the only primes with periods one (), two (), three (), and four () respectively. On the other hand, 41 and 271 both have period five, so neither is a unique prime.The unique primes are the primes such thatwhere is a cyclotomic polynomial, is the period of the unique prime, is the greatest common divisor, and is a positive integer.The first few unique primes are 3, 11, 37, 101, 9091, 9901, 333667, ... (OEIS A040017), which have periods 1, 2, 3, 4, 10, 12, 9, 14, 24, ... (OEIS A051627), respectively.

### Prime number theorem

The prime number theorem gives an asymptotic form for the prime counting function , which counts the number of primes less than some integer . Legendre (1808) suggested that for large ,(1)with (where is sometimes called Legendre's constant), a formula which is correct in the leading term only,(2)(Nagell 1951, p. 54; Wagon 1991, pp. 28-29; Havil 2003, p. 177).In 1792, when only 15 years old, Gauss proposed that(3)Gauss later refined his estimate to(4)where(5)is the logarithmic integral. Gauss did not publish this result, which he first mentioned in an 1849 letter to Encke. It was subsequently posthumously published in 1863 (Gauss 1863; Havil 2003, pp. 174-176).Note that has the asymptotic series about of(6)(7)and taking the first three terms has been shown to be a better estimate than alone (Derbyshire 2004, pp. 116-117).The statement (4) is often known as "the" prime number theorem and was proved..

### P&oacute;lya conjecture

Let be a positive integer and the number of (not necessarily distinct) prime factors of (with ). Let be the number of positive integers with an odd number of prime factors, and the number of positive integers with an even number of prime factors. Pólya (1919) conjectured thatis , where is the Liouville function.The conjecture was made in 1919, and disproven by Haselgrove (1958) using a method due to Ingham (1942). Lehman (1960) found the first explicit counterexample, , and the smallest counterexample was found by Tanaka (1980). The first for which are , 4, 6, 10, 16, 26, 40, 96, 586, 906150256, ... (Tanaka 1980, OEIS A028488). It is unknown if changes sign infinitely often (Tanaka 1980).

### Euler prime

Let a prime number generated by Euler's prime-generating polynomial be known as an Euler prime. Then the first few Euler primes occur for , 2, ..., 39, 42, 43, 45, ... (OEIS A056561), corresponding to the primes 43, 47, 53, 61, 71, 83, 97, 113, 131, 151, 173, ... (OEIS A005846).As of Feb. 2013, the largest known Euler prime is , which has 398204 decimal digits and was found by D. Broadhurst (https://primes.utm.edu/primes/page.php?id=111195).

### Wolstenholme prime

A prime is called a Wolstenholme prime if the central binomial coefficient(1)or equivalently if(2)where is the th Bernoulli number and the congruence is fractional.A prime is a Wolstenholme prime if and only if(3)where the congruence is again fractional.The only known Wolstenholme primes are 16843 and 2124679 (OEIS A088164). There are no others up to (McIntosh 2004).

### Wilson prime

A Wilson prime is a prime satisfyingwhere is the Wilson quotient, or equivalently,The first few Wilson primes are 5, 13, and 563 (OEIS A007540). Crandall et al. (1997) showed there are no others less than (McIntosh 2004), a limit that has subsequently been increased to (Costa et al. 2012).

### Wieferich prime

A Wieferich prime is a prime which is a solution to the congruence equation(1)Note the similarity of this expression to the special case of Fermat'slittle theorem(2)which holds for all odd primes. The first few Wieferich primes are 1093, 3511, ... (OEIS A001220), with none other less than (Lehmer 1981, Crandall 1986, Crandall et al. 1997), a limit since increased to (McIntosh 2004) and subsequently to by PrimeGrid as of November 2015.Interestingly, one less than these numbers have suggestive periodic binaryrepresentations(3)(4)(Johnson 1977).If the first case of Fermat's last theorem is false for exponent , then must be a Wieferich prime (Wieferich 1909). If with and relatively prime, then is a Wieferich prime iff also divides . The conjecture that there are no three consecutive powerful numbers implies that there are infinitely many non-Wieferich primes (Granville 1986; Ribenboim 1996, p. 341; Vardi 1991). In addition, the abc..

### Number field sieve

An extremely fast factorization method developed by Pollard which was used to factor the RSA-130 number. This method is the most powerful known for factoring general numbers, and has complexity(1)reducing the exponent over the continued fraction factorization algorithm and quadratic sieve. There are three values of relevant to different flavors of the method (Pomerance 1996). For the "special" case of the algorithm applied to numbers near a large power,(2)for the "general" case applicable to any odd positive number which is not a power,(3)and for a version using many polynomials (Coppersmith1993),(4)

### Elliptic curve primality proving

Elliptic curve primality proving, abbreviated ECPP, is class of algorithms that provide certificates of primality using sophisticated results from the theory of elliptic curves. A detailed description and list of references are given by Atkin and Morain (1990, 1993).Adleman and Huang (1987) designed an independent algorithm using hyperellipticcurves of genus two.ECPP is the fastest known general-purpose primality testing algorithm. ECPP has a running time of . As of 2004, the program PRIMO can certify a 4769-digit prime in approximately 2000 hours of computation (or nearly three months of uninterrupted computation) on a 1 GHz processor using this technique. As of 2009, the largest prime certified using this technique was the 11th Mills' prime (https://primes.utm.edu/primes/page.php?id=77907)which has decimal digits. The proof was performed using a distributed computation that started in September 2005 and ended in June 2006..

### Wagstaff prime

A Wagstaff prime is a prime number of the form for a prime number. The first few are given by , 5, 7, 11, 13, 17, 19, 23, 31, 43, 61, 79, 101, 127, 167, 191, 199, 313, 347, 701, 1709, 2617, 3539, 5807, 10501, 10691, 11279, 12391, 14479, 42737, 83339, 95369, 117239, 127031, 138937, 141079, 267017, 269987, 374321, 986191, and 4031399 (OEIS A000978), with and larger corresponding to probable primes. These values correspond to the primes with indices , 3, 4, 5, 6, 7, 8, 9, 11, 14, 18, 22, 26, ... (OEIS A123176).The Wagstaff primes are featured in the newMersenne prime conjecture.There is no simple primality test analogous to the Lucas-Lehmer test for Wagstaff primes, so all recent primality proofs of Wagstaff primes have used elliptic curve primality proving.A Wagstaff prime can also be interpreted as a repunit prime of base , asif is odd, as it must be for the above number to be prime.Some of the largest known Wagstaff probable primes are summarized in the following..

### Elliptic curve factorization method

The elliptic curve factorization method, abbreviated ECM and sometimes also called the Lenstra elliptic curve method, is a factorization algorithm that computes a large multiple of a point on a random elliptic curve modulo the number to be factored . It tends to be faster than the Pollard rho factorization and Pollard p-1 factorization methods.Zimmermann maintains a table of the largest factors found using the ECM. As of Jan. 2009, the largest prime factor found using the ECM had 67 decimal digits. This factor of was found by B. Dodson on Aug. 24, 2006 (Zimmermann).

### Twin primes

Twin primes are pairs of primes of the form (, ). The term "twin prime" was coined by Paul Stäckel (1862-1919; Tietze 1965, p. 19). The first few twin primes are for , 6, 12, 18, 30, 42, 60, 72, 102, 108, 138, 150, 180, 192, 198, 228, 240, 270, 282, ... (OEIS A014574). Explicitly, these are (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), ... (OEIS A001359 and A006512).All twin primes except (3, 5) are of the form .It is conjectured that there are an infinite number of twin primes (this is one form of the twin prime conjecture), but proving this remains one of the most elusive open problems in number theory. An important result for twin primes is Brun's theorem, which states that the number obtained by adding the reciprocals of the odd twin primes,(1)converges to a definite number ("Brun's constant"), which expresses the scarcity of twin primes, even if there are infinitely many of them (Ribenboim 1996, p. 201)...

### Titanic prime

In the 1980s, Samuel Yates defined a titanic prime to be a prime number of at least 1000 decimal digits. The smallest titanic prime is . As of 1990, more than 1400 were known (Ribenboim 1990). By 1995, more than were known, and many tens of thousands are known today. The largest prime number known as of December 2018 is the Mersenne prime , which has a whopping decimal digits.

### Cunningham chain

A sequence of primes is a Cunningham chain of the first kind (second kind) of length if () for , ..., . Cunningham primes of the first kind are Sophie Germain primes.It is conjectured there are arbitrarily long Cunningham chains. The longest known Cunningham chains are of length 17, with the first examples found corresponding to (first kind; J. Wroblewski, May 2008) and (second kind; J. Wroblewski, Jun. 2008).The smallest prime beginning a complete Cunningham chain of the first kind of lengths , 2, ... are 13, 3, 41, 509, 2, 89, 1122659, 19099919, 85864769, 26089808579, ... (OEIS A005602).The smallest prime beginning a complete Cunningham chain of the second kind of lengths , 2, ... are 11, 7, 2, 2131, 1531, 33301, 16651, 15514861, 857095381, 205528443121, ... (OEIS A005603)...

### Strong pseudoprime

A strong pseudoprime to a base is an odd composite number with (for odd) for which either(1)or(2)for some , 1, ..., (Riesel 1994, p. 91). Note that Guy (1994, p. 27) restricts the definition of strong pseudoprimes to only those satisfying (1).The definition is motivated by the fact that a Fermat pseudoprime to the base satisfies(3)But since is odd, it can be written , and(4)If is prime, it must divide at least one of the factors, but can't divide both because it would then divide their difference(5)Therefore,(6)so write to obtain(7)If divides exactly one of these factors but is composite, it is a strong pseudoprime. A composite number is a strong pseudoprime to at most 1/4 of all bases less than itself (Monier 1980, Rabin 1980). The strong pseudoprimes provide the basis for Miller's primality test and Rabin-Miller strong pseudoprime test.A strong pseudoprime to the base is also an Euler pseudoprime to the base (Pomerance et al. 1980)...

### Sophie germain prime

A prime is said to be a Sophie Germain prime if both and are prime. The first few Sophie Germain primes are 2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, ... (OEIS A005384). It is not known if there are an infinite number of Sophie Germain primes (Hoffman 1998, p. 190).The numbers of Sophie Germain primes less than for , 2, ... are 3, 10, 37, 190, 1171, 7746, 56032, ... (OEIS A092816).The largest known proven Sophie Germain prime pair as of Feb. 29, 2016 is given by where(Caldwell), each of which has decimal digits (PrimeGrid).The definition of Sophie Germain primes and the value of the largest then-known suchprime were mentioned by the characters Hal and Catherine in the 2005 film Proof.Sophie Germain primes of the form correspond to the indices of composite Mersenne numbers .Around 1825, Sophie Germain proved that the first case of Fermat's last theorem is true for such primes, i.e., if is a Sophie Germain prime, then there do not exist integers..

### Cousin primes

Pairs of primes of the form (, ) are called cousin primes. The first few are (3, 7), (7, 11), (13, 17), (19, 23), (37, 41), (43, 47), (67, 71), ... (OEIS A023200 and A046132).A large pair of cousin (proven) primes start with(1)where is a primorial. These primes have 10154 digits and were found by T. Alm, M. Fleuren, and J. K. Andersen (Andersen 2005).As of Jan. 2006, the largest known pair of cousin (probable) primes are(2)which have 11311 digits and were found by D. Johnson in May 2004.According to the first Hardy-Littlewood conjecture, the cousin primes have the same asymptotic density as the twin primes,(3)(4)where (OEIS A114907) is the twin primes constant.An analogy to Brun's constant, the constant(5)(omitting the initial term ) can be defined. Using cousin primes up to , the value of is estimated as(6)..

### Prime triplet

A prime triplet is a prime constellation of the form (, , ), (, , ), etc. Hardy and Wright (1979, p. 5) conjecture, and it seems almost certain to be true, that there are infinitely many prime triplets of the form (, , ) and (, , ).tripletSloanefirst member(, , )A0220045, 11, 17, 41, 101, 107, ...(, , )A0461343, 5, 11, 29, 59, 71, 101, ...(, , )A0461355, 11, 17, 29, 41, 59, 71, ...(, , )A0220057, 13, 37, 67, 97, 103, ...(, , )A0461363, 7, 13, 19, 37, 43, 79, ...(, , )A0461377, 19, 67, 97, 127, 229, ...(, , )A0461385, 11, 23, 53, 101, 131, ...(, , )A0461397, 13, 31, 37, 61, 73, 97, ...(, , )A0232415, 7, 11, 17, 31, 41, 47, ...(, , )A0461415, 11, 29, 59, 71, 89, 101, ...As of Apr. 2019, the largest known prime triplet of the form has smallest memberand each of its three members has decimal digits...

### Brun's constant

The number obtained by adding the reciprocals of the odd twinprimes,(1)By Brun's theorem, the series converges to a definite number, which expresses the scarcity of twin primes, even if there are infinitely many of them (Ribenboim 1989, p. 201). By contrast, the series of all prime reciprocals diverges to infinity, as follows from the Mertens second theorem by letting (which provides a stronger characterization of the divergence than Euler's proof that , obtained more than a century before Mertens' proof).Shanks and Wrench (1974) used all the twin primes among the first 2 million numbers. Brent (1976) calculated all twin primes up to 100 billion and obtained (Ribenboim 1989, p. 146)(2)assuming the truth of the first Hardy-Littlewood conjecture. Using twin primes up to , Nicely (1996) obtained(3)(Cipra 1995, 1996), in the process discovering a bug in Intel's® PentiumTM microprocessor. Using twin primes up to , Nicely..

### Prime gaps

A prime gap of length is a run of consecutive composite numbers between two successive primes. Therefore, the difference between two successive primes and bounding a prime gap of length is , where is the th prime number. Since the prime difference function(1)is always even (except for ), all primes gaps are also even. The notation is commonly used to denote the smallest prime corresponding to the start of a prime gap of length , i.e., such that is prime, , , ..., are all composite, and is prime (with the additional constraint that no smaller number satisfying these properties exists).The maximal prime gap is the length of the largest prime gap that begins with a prime less than some maximum value . For , 2, ..., is given by 4, 8, 20, 36, 72, 114, 154, 220, 282, 354, 464, 540, 674, 804, 906, 1132, ... (OEIS A053303).Arbitrarily large prime gaps exist. For example, for any , the numbers , , ..., are all composite (Havil 2003, p. 170). However, no general method..

### Prime factorization algorithms

Many algorithms have been devised for determining the prime factors of a given number (a process called prime factorization). They vary quite a bit in sophistication and complexity. It is very difficult to build a general-purpose algorithm for this computationally "hard" problem, so any additional information that is known about the number in question or its factors can often be used to save a large amount of time.The simplest method of finding factors is so-called "direct search factorization" (a.k.a. trial division). In this method, all possible factors are systematically tested using trial division to see if they actually divide the given number. It is practical only for very small numbers.The fastest-known fully proven deterministic algorithm is the Pollard-Strassen method(Pomerance 1982; Hardy et al. 1990)...

### Prime counting function

The prime counting function is the function giving the number of primes less than or equal to a given number (Shanks 1993, p. 15). For example, there are no primes , so . There is a single prime (2) , so . There are two primes (2 and 3) , so . And so on.The notation for the prime counting function is slightly unfortunate because it has nothing whatsoever to do with the constant . This notation was introduced by number theorist Edmund Landau in 1909 and has now become standard. In the words of Derbyshire (2004, p. 38), "I am sorry about this; it is not my fault. You'll just have to put up with it."Letting denote the th prime, is a right inverse of since(1)for all positive integers. Also,(2)iff is a prime number.The first few values of for , 2, ... are 0, 1, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6, ... (OEIS A000720). The Wolfram Language command giving the prime counting function for a number is PrimePi[x], which works up to a maximum value of .The notation..

### Goldbach conjecture

Goldbach's original conjecture (sometimes called the "ternary" Goldbach conjecture), written in a June 7, 1742 letter to Euler, states "at least it seems that every number that is greater than 2 is the sum of three primes" (Goldbach 1742; Dickson 2005, p. 421). Note that Goldbach considered the number 1 to be a prime, a convention that is no longer followed. As re-expressed by Euler, an equivalent form of this conjecture (called the "strong" or "binary" Goldbach conjecture) asserts that all positive even integers can be expressed as the sum of two primes. Two primes such that for a positive integer are sometimes called a Goldbach partition (Oliveira e Silva).According to Hardy (1999, p. 19), "It is comparatively easy to make clever guesses; indeed there are theorems, like 'Goldbach's Theorem,' which have never been proved and which any fool could have guessed." Faber and..

### Prime arithmetic progression

An arithmetic progression of primes is a set of primes of the form for fixed and and consecutive , i.e., . For example, 199, 409, 619, 829, 1039, 1249, 1459, 1669, 1879, 2089 is a 10-term arithmetic progression of primes with difference 210.It had long been conjectured that there exist arbitrarily long sequences of primes in arithmetic progression (Guy 1994). As early as 1770, Lagrange and Waring investigated how large the common difference of an arithmetic progression of primes must be. In 1923, Hardy and Littlewood (1923) made a very general conjecture known as the k-tuple conjecture about the distribution of prime constellations, which includes the hypothesis that there exist infinitely long prime arithmetic progressions as a special case. Important additional theoretical progress was subsequently made by van der Corput (1939), who proved than there are infinitely many triples of primes in arithmetic progression, and Heath-Brown (1981),..

### Gilbreath's conjecture

Let the difference of successive primes be defined by , and by(1)N. L. Gilbreath claimed that for all (Guy 1994). In 1959, the claim was verified for . In 1993, Odlyzko extended the claim to all primes up to .Gilbreath's conjecture is equivalent to the statement that, in the triangular array of the primes, iteratively taking the absolute difference of each pair of terms(2)(OEIS A036262), always gives leading term 1(after the first row).The number of terms before reaching the first greater than two in the second, third,etc., rows are given by 3, 8, 14, 14, 25, 23, 22, 25, ... (OEIS A000232).

### Fermat prime

A Fermat prime is a Fermat number that is prime. Fermat primes are therefore near-square primes.Fermat conjectured in 1650 that every Fermat number is prime and Eisenstein in 1844 proposed as a problem the proof that there are an infinite number of Fermat primes (Ribenboim 1996, p. 88). At present, however, the only Fermat numbers for for which primality or compositeness has been established are all composite.The only known Fermat primes are(1)(2)(3)(4)(5)(OEIS A019434), and it seems unlikely that any more will be found using current computational methods and hardware. It follows that is prime for the special case together with the Fermat prime indices, giving the sequence 2, 3, 5, 17, 257, and 65537 (OEIS A092506). is a Fermat prime if and only if the period length of is equal to . In other words, Fermat primes are full reptend primes...

### Bertrand's postulate

Bertrand's postulate, also called the Bertrand-Chebyshev theorem or Chebyshev's theorem, states that if , there is always at least one prime between and . Equivalently, if , then there is always at least one prime such that . The conjecture was first made by Bertrand in 1845 (Bertrand 1845; Nagell 1951, p. 67; Havil 2003, p. 25). It was proved in 1850 by Chebyshev (Chebyshev 1854; Havil 2003, p. 25; Derbyshire 2004, p. 124) using non-elementary methods, and is therefore sometimes known as Chebyshev's theorem. The first elementary proof was by Ramanujan, and later improved by a 19-year-old Erdős in 1932.A short verse about Bertrand's postulate states, "Chebyshev said it, but I'll say it again; There's always a prime between and ." While commonly attributed to Erdős or to some other Hungarian mathematician upon Erdős's youthful re-proof the theorem (Hoffman 1998), the quote is actually..

### Lucas's theorem

Lucas's theorem states that if be a squarefree integer and a cyclotomic polynomial, then(1)where and are integer polynomials of degree and , respectively. This identity can be expressed as(2)with and symmetric polynomials. The following table gives the first few and s (Riesel 1994, pp. 443-456).213156710

### Idoneal number

An idoneal number, also called a suitable number or convenient number, is a positive integer for which the fact that a number is a monomorph (i.e., is expressible in only one way as where is relatively prime to ) guarantees it to be a prime, prime power, or twice one of these. The numbers are also called Euler's idoneal numbers or suitable numbers.A positive integer is idoneal iff it cannot be written as for integer , , and with .The 65 idoneal numbers found by Gauss and Euler and conjectured to be the only such numbers (Shanks 1969) are 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 15, 16, 18, 21, 22, 24, 25, 28, 30, 33, 37, 40, 42, 45, 48, 57, 58, 60, 70, 72, 78, 85, 88, 93, 102, 105, 112, 120, 130, 133, 165, 168, 177, 190, 210, 232, 240, 253, 273, 280, 312, 330, 345, 357, 385, 408, 462, 520, 760, 840, 1320, 1365, and 1848 (OEIS A000926). It is known that if any other idoneal numbers exist, there can be only one more...

### Prime diophantine equations

is prime iff the 14 Diophantine equations in 26 variables(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12)(13)(14)have a solution in positive integers (Jones etal. 1976; Riesel 1994, p. 40).

### Wilson's theorem

Iff is a prime, then is a multiple of , that is(1)This theorem was proposed by John Wilson and published by Waring (1770), although it was previously known to Leibniz. It was proved by Lagrange in 1773. Unlike Fermat's little theorem, Wilson's theorem is both necessary and sufficient for primality. For a composite number, except when .A corollary to the theorem states that iff a prime is of the form , then(2)The first few primes of the form are , 13, 17, 29, 37, 41, ... (OEIS A002144), corresponding to , 3, 4, 7, 9, 10, 13, 15, 18, 22, 24, 25, 27, 28, 34, 37, ... (OEIS A005098).Gauss's generalization of Wilson's theorem considers the product of integers that are less than or equal to and relatively prime to an integer . For , 2, ..., the first few values are 1, 1, 2, 3, 24, 5, 720, 105, 2240, 189, ... (OEIS A001783). Then defining(3)gives the congruence(4)for an odd prime. When , this reduces to which is equivalent to . The first few values of are 0, , , , , , , 1, , , , .....

### Gauss's criterion

Let be an odd prime and a positive integer not divisible by . Then for each positive odd integer , let bewith , and let be the number of even s. Thenwhere is the Legendre symbol.

### Fermat quotient

The Fermat quotient for a number and a prime base is defined as(1)If , then(2)(3)(mod ), where the modulus is taken as a fractional congruence.The special case is given by(4)(5)(6)(7)(8)all again (mod ) where the modulus is taken as a fractional congruence, is the digamma function, and the last two equations hold for odd primes only. is an integer for a prime, with the values for , 3, 5, ... being 1, 3, 2, 5, 3, 13, 3, 17, 1, 6, ....The quantity is known to be congruent to zero (mod ) for only two primes: the so-called Wieferich primes 1093 and 3511 (Lehmer 1981, Crandall 1986).

### Prime cut

Find two numbers such that . If you know the greatest common divisor of and , there exists a high probability of determining a prime factor. Taking small numbers which additionally give small primes further increases the chances of finding a prime factor.

### Fermat's little theorem

If is a prime number and is a natural number, then(1)Furthermore, if ( does not divide ), then there exists some smallest exponent such that(2)and divides . Hence,(3)The theorem is sometimes also simply known as "Fermat'stheorem" (Hardy and Wright 1979, p. 63).This is a generalization of the Chinese hypothesis and a special case of Euler's totient theorem. It is sometimes called Fermat's primality test and is a necessary but not sufficient test for primality. Although it was presumably proved (but suppressed) by Fermat, the first proof was published by Euler in 1749. It is unclear when the term "Fermat's little theorem" was first used to describe the theorem, but it was used in a German textbook by Hensel (1913) and appears in Mac Lane (1940) and Kaplansky (1945).The theorem is easily proved using mathematical induction on . Suppose (i.e., divides ). Then examine(4)From the binomial theorem,(5)Rewriting,(6)But..

### Prime number

A prime number (or prime integer, often simply called a "prime" for short) is a positive integer that has no positive integer divisors other than 1 and itself. More concisely, a prime number is a positive integer having exactly one positive divisor other than 1, meaning it is a number that cannot be factored. For example, the only divisors of 13 are 1 and 13, making 13 a prime number, while the number 24 has divisors 1, 2, 3, 4, 6, 8, 12, and 24 (corresponding to the factorization ), making 24 not a prime number. Positive integers other than 1 which are not prime are called composite numbers.While the term "prime number" commonly refers to prime positive integers, other types of primes are also defined, such as the Gaussian primes.The number 1 is a special case which is considered neither prime nor composite (Wells 1986, p. 31). Although the number 1 used to be considered a prime (Goldbach 1742; Lehmer 1909, 1914; Hardy and Wright..

### Prime factorization

The factorization of a number into its constituent primes, also called prime decomposition. Given a positive integer , the prime factorization is writtenwhere the s are the prime factors, each of order . Each factor is called a primary. Prime factorization can be performed in the Wolfram Language using the command FactorInteger[n], which returns a list of pairs.Through his invention of the Pratt certificate, Pratt (1975) became the first to establish that prime factorization lies in the complexity class NP.The following Wolfram Language code can be used to give a nicely typeset form of a number : FactorForm[n_?NumberQ, fac_:Automatic] := Times @@ (HoldForm[Power[]]& @@@ FactorInteger[n, fac])The first few prime factorizations (the number 1, by definition, has a prime factorization of "1") are given in the following table.prime factorizationprime factorization11111122123313134145515616771717818919191020The..

### Prime array

Find the array of single digits which contains the maximum possible number of primes, where allowable primes may lie along any horizontal, vertical, or diagonal line.For the array, 11 primes are maximal and are contained in the two distinct arrays(1)giving the primes (3, 7, 13, 17, 31, 37, 41, 43,47, 71, 73) and (3, 7, 13, 17, 19, 31, 37, 71, 73, 79, 97), respectively.The best array is(2)which contains 30 primes: 3, 5, 7, 11, 13, 17, 31, 37, 41, 43, 47, 53, 59, 71, 73, 79, 97, 113, 157, 179, ... (OEIS A032529). This array was found by Rivera and Ayala and shown by Weisstein in May 1999 to be maximal and unique (modulo reflection and rotation).The best arrays known are(3)all of which contain 63 primes. The first was found by C. Rivera and J. Ayala in 1998, and the other three by James Bonfield on April 13, 1999. Mike Oakes proved by computation that the 63 primes is optimal for the array.The best prime arrays known are(4)each of which contains 116 primes...

### Landau's formula

Landau (1911) proved that for any fixed ,as , where the sum runs over the nontrivial Riemann zeta function zeros and is the Mangoldt function. Here, "fixed " means that the constant implicit in depends on and, in particular, as approaches a prime or a prime power, the constant becomes large.Landau's formula is roughly the derivative of the explicitformula.Landau's formula is quite extraordinary. If is not a prime or a prime power, then and the sum grows as a constant times . But if is a prime or a prime power, then and the sum grows much faster, like a constant times . This exhibits an amazing connection between the primes and the s; somehow the zeros "recognize" when is a prime and cause large contributions to the sum.

### Carmichael condition

A number satisfies the Carmichael condition iff for all prime divisors of . This is equivalent to the condition for all prime divisors of .

### Factor

A factor is a portion of a quantity, usually an integer or polynomial that, when multiplied by other factors, gives the entire quantity. The determination of factors is called factorization (or sometimes "factoring").In number theoretic usage, a factor of a number is equivalent to a divisor of (Ore 1988, p. 29; Burton 1989, p. 26). The divisors of a number are given in the Wolfram Language by the command Divisors[n]. In elementary education, the term "factor" is sometimes used to mean proper divisor, i.e., a factor of other than the number itself. However, as a result of the confusion this practice creates and its inconsistency with the mathematical literature, it should be discouraged.It is usually desired to break factors down into the smallest possible pieces so that no factor is itself factorable. For integers, the determination of such prime factors is called prime factorization. For large integers,..

### Prime products

The product of primes(1)with the th prime, is called the primorial function, by analogy with the factorial function. Its logarithm is closely related to the Chebyshev function .The zeta-regularized product over allprimes is given by(2)(3)(Muñoz Garcia and Pérez-Marco 2003, 2008), answering the question posed by Soulé et al. (1992, p. 101). A derivation proceeds by algebraic manipulation of the prime zeta function and gives the more general results(4)and(5)(Muñoz Garcia and Pérez-Marco 2003).Mertens theorem states that(6)where is the Euler-Mascheroni constant, and a closely related result is given by(7)There are amazing infinite product formulas forprimes given by(8)(Ramanujan 1913-1914; Le Lionnais 1983, p. 46) and(9)(OEIS A082020; Ramanujan 1913-1914).More general formulas are given by(10)where is the Riemann zeta function and by the Euler product(11)Named prime..

### Factorization

The determination of a set of factors (divisors) of a given integer ("prime factorization"), polynomial ("polynomial factorization"), etc., which, when multiplied together, give the original number, polynomial, etc In many cases of interest (particularly prime factorization, factorization is unique, and so gives the "simplest" representation of a given quantity in terms of smaller parts.The terms "factorization" and "factoring" are used synonymously.The term "factorization" is occasionally misused, including by no less "authority" than The New York Times, where Fox (2006) wrote, "He was 88, which can be factored as 1, 2, 4, 8, 11, 22, 44, and 88." This usage is incorrect since the given numbers are indeed factors, but the collection of factors does not comprise a factorization...