With our order of presentation, fundamental concepts aren't used before
they're introduced. The edifice rests on
greatest common divisors,
Euclid's algorithm and Bézout's lemma.
The basic structure of the prime numbers can then be freely examined
in the second part.
(2016-11-07) Divisors
(or Factors ) and divisibility relation :
Divisors are well-defined within any additivesemigroup.
In an additive semigroup
(or, more generally, a magma merely endowed with a
power-associative addition)
an element x is said to be a divisor
(or factor ) of another element y
(we also say that "x divides y") when the latter is the
sum of one or more terms equal to the former:
x + x + ... + x = y
The divisibilityrelation "x divides y" is a preorder relation, since:
It's reflexive
(any element, including zero, divides itself ).
It's transitive (i.e., if x divides y and y divides z, then x divides z)
because addition is associative.
(Power-associativity is enough.)
As usual, the qualifier
proper can be used to disallow reflexivity.
Thus, x is never a proper divisor of itself.
It's paramount to define a concept as general as this one
in the poorest of cases (to avoid inferior definitions in richer contexts).
Here for example, we must disallow empty sums at the outset because
such things are only defined when there's a neutral element for addition.
Thus, when an additive element (zero) does exist,
the existence of proper divisors of zero
isn't trivial (it's an important consideration with
the generalized notion of divisor used in Ring Theory).
For the monoid of nonnegative integers, a third property is true,
which makes divisibility a full-fledged partial ordering relation :
It's antisymmetric (i.e., if x divides y and y divides x, then x = y).
Proof : We first remark that, among nonnegative integers,
a number is always greater than or equal to any of its divisors.
Then, the antisymmetry of divisibility is obtained from the antisymmetry of the usual ordering.
Note that zero (the neutral element for addition) divides only itself.
Although zero is a multiple of any other integer,
none is a divisor of zero.
(2015-01-25) Relatively prime
(or coprime ) integers.
Two integers are coprime when their greatest common divisor is 1.
The greatest common divisor (GCD) of two
integers is defined as the largest positive integer that divides
them both. The GCD
is efficiently computed using Euclid's algorithm
(or, far less efficiently, with the subtractive version
which can be more convenient for theoretical proofs).
Likewise, several integers are coprime when their only common positive divisor is 1
(French: nombres premiers entre eux,
nombres étrangers ).
Such numbers need not be pairwise coprime (e.g., 6, 10 and 15).
Theorem :
Arguably, the most important fact about coprime integers is:
If the number d divides m n and is coprime with n,
then d divides m.
Proof :
Using Bézout's lemma,
(itself a consequence of Euclid's algorithm,
quoted in the above definition of coprime numbers)
we know that there exists two integers u and v such that:
u d + v n = 1
Since d divides m n it also divides the following quantity:
u d m + v m n =
m ( u d + v n ) = m
Note that this result is crucial in the
proof of the fundamental theorem of arithmetic given below.
(In other words, the above establishes the unicity of prime factorizations;
it's not the other way around.)
Corollary :
If k is coprime with n, then
k Ù m n = k Ù m
Proof :
The main theorem says that any divisor d of m n divides m.
So d = k Ù m n
divides m and k. Therefore, this d
divides their GCD
(k Ù m).
The converse is trivially true, so the two are equal.
A positive integer p is said to be prime
when it has just two distinct divisors
among positive integers (1 and p).
Besides the number 1 (one) itself, which is not considered prime,
any positive integer is thus either a prime or a composite
number (namely, the product of two lesser factors).
Two distinct prime numbers p and q are clearly
coprime
(HINT: the set of their common divisors is the
intersection of {1,p} and {1,q}).
That fact, known as the coprimality of primes,
implies that a prime which divides a product of distinct primes must be equal
to one of them (HINT: Prove this by
induction on the number of factors).
That's needed to prove the fundamental theorem of arithmetic.
We proceed by induction, using the fact that any
integer greater than 1 is either prime or composite.
If such an integer is prime, we're done
(the prime divisor we're after is the number itself).
Otherwise, it has a lesser divisor greater than 1. Using the induction
hypothesis, that divisor has at least one prime factor.
By transitivity, that prime factor also divides the original number.
(2006-11-25) Fundamental Theorem of Arithmetic
Every positive integer has a unique factorization into primes.
For example:
168 = 2 3 3 7
Such a factorization can be specified by the
sequence of the exponents to which the successive primes should be
raised. In the example of 168, this is:
( 3, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, ... )
We say that "2 has multiplicity 3
in 168". The multiplicities of 3 and 7
in 168 are equal to 1.
Any other prime has multiplicity 0.
When discussing the prime divisors of a certain integer, it's
sometimes more elegant to consider the multiplicity of a prime
without assuming it's nonzero.
(On 2015-12-31, I found it convenient
to formulate this way a conjecture about the prime divisors of the form
6n+1 of the Wendt determinant
of odd order n).
Conversely, any sequence
of nonnegative integers with finitely many nonzero elements is associated with
a unique positive integer.
In the factorization of the integer 1, all exponents are zero:
( 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ... )
The sequence of exponents associated with the product of two positive integers is the
direct sum of the sequences associated with those factors.
Such sequences can be represented by lists ending at the
last nonzero term.
That would be the list (3,1,0,1) for 168
and the empty list ( ) for 1.
Proof of the Fundamental Theorem of Arithmetic :
Using the above lemma, we first prove (by induction)
that any positive integer n has a prime factorization
(i.e., it's a product of prime numbers). Gauss
(1798)
didn't think such a proof was needed. I beg to differ:
If n = 1, the factorization we seek is simply empty.
Otherwise, the lemma says that n has a prime divisor p.
The induction hypothesis tells us that the positive integer n/p has a
prime factorization.
Combining p with that factorization, we obtain a prime factorization of n.
To establish that the prime factorization of an integer is unique, we remark that
dividing repeatedly two such factorizations by any prime they have in common, must yield
an empty product.
Otherwise, we'd have a prime dividing a product of primes without being equal to any of them
(which contradicts the coprimality of distinct primes).
(2006-05-25) Euclid's Theorem (c. 300 BC)
There are infinitely many prime numbers.
All we have to prove is the existence of a prime above any given prime P.
This can be established in just two lines (one of the greatest proofs ever):
If Q is the product of all primes less than or equal to P, then any prime
factor of Q+1 can't divide Q and must, therefore,
be a prime greater than P.
Euclid's original proof isn't as simple but it's arguably more elementary because it doesn't
involve the product of an unbounded number of factors, which ancient Greeks may have found repugnant. It appears as
proposition 20
in Book IX of The Elements.
This great proof is often needlessly presented as a
proof by contradiction
(as Euclid himself did).
It's also often obscured by preliminary discussions about such things as
the nature of infinity, which aren't needed either.
Finally, the need for a not-so-obvious lemma (duly noted by Euclid)
is rarely stated, if ever.
The Set of Prime Numbers
(2007-04-30) Dirichlet's theorem on primes in arithmetic progressions:
If a and N are coprime, infinitely many primes are of the form kN+a.
This statement was conjectured by Gauss
(Euler had previously stated the special case a = 1).
It was proved by Dirichlet in 1837, using the
Dirichlet characters
and related L-series which he introduced
for that very purpose.
In 1975, Endre Szemerédi
(Abel prize 2012) proved that any set of integers of positive upper density
contains arbitrarily long
arithmetic progressions
(Szemerédi's theorem).
This had been conjectured by
Erdös (1913-1996) and
Turán (1910-1976) in 1936.
That result doesn't apply to the set of primes (which has zero upper density)
but Erdös strengthened the Erdös-Turán conjecture
in 1973 to state that arbitrarily long arithmetic progressions exist
in any set of positive integers when the series of its reciprocals diverges.
That's a very strong statement which would imply the Green-Tao theorem of 2004.
In 2006
(pdf),
Tao and Tamar Ziegler
generalized that, by showing that there are
arbitrarily long polynomial progressions of primes.
More precisely:
For any sequence of k integer-valued polynomials
(Q1, Q2 ... Qk )
and any positive e,
there are infinitely many choices of integers
x and
m < x e
which make all expressions x+mQi(m) prime.
The original Green-Tao theorem corresponds to the
special case Qi(m) = i.
The existence of infinitely many arithmetic progressions of length 3
among primes was established in 1939, by the Dutch mathematician
Johannes van der Corput
(1890-1971). Originally, Green and Tao wanted to prove that there are
infinitely many equally spaced sequences of 4 primes, but they saw that their
methods proved the existence of such sequences of any length...
Smallest Prime Arithmetic Progressions (PAP) of Given Length
If an arithmetic progression (AP) of k primes
starts above k,
then its common difference (N) must be a multiple
of all the primes less than or equal to k (or else, one such prime would
be a proper factor of a term in the progression).
This is made explicit in the above, using the
(fairly standard) notation
p# to denote the primorial of p, namely the
product of all primes between 2 and p
(A002110).
Recent Results and New Records :
Since the record breakers
are rarely found in strict order of size, we can't
reliably extend the above table. Instead, we'll just mention some newer results,
starting with the first known example of 22 primes in arithmetic progression,
discovered by Andrew Moran, Paul A. Pritchard and Anthony Thyssen on
1993-03-17:
11410337850553 + 4609098694200 k (k = 0 to 21).
On 2004-07-24,
Markus Frind, Paul Jobling and Paul Underwood found
an arithmetic progression of 23 primes
(ending with 449924511422857) :
56211383760397 + 44546738095860 k
(k = 0 to 22).
A smaller instance
(ending with 1036239621869317) was later found by Frind
(2006-04-01)
featuring a common difference
N = 9523 . 23#.
403185216600637 + 2124513401010 k
(k = 0 to 22).
The first arithmetic progression of 24 primes was discovered by
Jaroslaw "Jarek"
Wróblewski on
2007-01-18:
468395662504823 + k . 205619 . 23# (k = 0 to 23).
Wróblewski and Raanan Chermoni found a PAP of length 25 on 2008-05-17:
6171054912832631 + k . 366384 . 23# (k = 0 to 24).
In a distributed PrimeGrid project using software written
by Jaroslaw Wroblewski and Geoff Reynolds, the
Playstation 3 of Benoît Périchon found
26 primes in arithmetic progression on 2010-04-12:
43142746595714191 + k . 23681770 . 23# (k = 0 to 25).
A204189
The second example, discovered on 2012-03-16 by James Fry, is smaller:
3486107472997423 + k . 1666981 . 23# (k = 0 to 25).
The first example of 27 primes in arithmetic progression was discovered by Rob Gahan
with PrimeGrid, on 2019-09-23:
224584605939537911 + k . 81292139 . 23# (k = 0 to 26).
Consecutive Primes in Arithmetic Progression :
It's much more difficult to find consecutive primes
in arithmetic progression.
A sequence of length 10 was first found on
1998-03-02.
Namely,
P + 210 k (for k = 0 to 9)
with the following 93-digit value for P.
It's highly unlikely that a longer sequence (length 11) will be found any time soon,
although it's conjectured that there are infinitely many
instances of k consecutive primes in arithmetic progression,
for any k...
(2009-06-26) The von Mangoldt function
L(n)
L(n) = Log p if n
is a power of the prime p. Otherwise, L(n) = 0
The fundamental theorem of arithmetic is essentially equivalent
to the following relation, which states that the logarithm of an
integer is equal to the sum of the values of the
von Mangoldt function over all its divisors:
The function L is named after
Hans von
Mangoldt (1854-1925) who got his doctorate at
Berlin under
Weierstrass and
Kummer.
He paved the way for the two proofs of the Prime number theorem (1896)
by providing rigorous proofs for two statements which had only partial proofs
in Riemann's 1859 seminal paper on the Zeta function.
In 1895, von Mangoldt proved a
conjecture stated by
Bernhard Riemann (1826-1866)
in
1859.
The number of roots of the zeta function with a positive imaginary part less than
2kp is indeed:
(2006-11-25) PNT: The Prime Number Theorem (1896)
A random integer N is prime with a probability roughly equal to 1/ln(N).
In 1792, at age 15,
Gauss
made the above statement as a private conjecture in
his notebook.
This is usually recast in terms of various (equivalent)
approximations to the prime-counting function
which lets p(x)
denote the number of primes below x :
There's no controversy about the value of p(x)
between prime values of x.
At those points of discontinuity however,
the modern convention is used (consistent with the results of
Fourier analysis) which makes the value
at a jump discontinuity equal to the half-sum of the left and right limits.
Bizarre as it may look at first,
this normalization is also adopted for other counting functions,
including the prime-power counting function (J)
discussed below.
This flavor of the prime counting function is what
Riemann described when he
introduced the concept in 1859 (in his paper, he used the symbol F for this).
That's sometimes called the normalized
prime counting function, using a nought subscript to single it out.
However, since there's no agreement on what the unnormalized
version should be, I recommend dropping both the qualifier and the subscript !
In 1808, Legendre
proposed the following approximation, involving
a parameter B (about -1.08366) sometimes known as Legendre's constant.
(For extremely large values of N, the best value of B would be 1.)
p(x) ~ x / (B + ln x)
The aforementioned conjectural remark of the young Gauss is equivalent to equating
p(x) and
either flavor of the
logarithmic integral li(x) or Li(x).
Gauss put it in this form in 1849 (although his remark
appeared in print only posthumously, in 1863).
The resulting statement became known as the prime number theorem (PNT).
p(x)
~
li(x) ~ Li(x)
~
x / ln(x)
+ x / (ln x)2
+ 2x / (ln x)3
+ ... + k! x / (ln x)k+1
+ ...
Although it would be better to retain the first 3 terms in the above
asymptotic expansion
of the logarithm integral,
the PNT is usually stated by retaining only the leading term x/ln(x). Namely:
Prime-Number Theorem (PNT)
lim x® ¥
p(x)
= 1
x / Log x
In 1848, well before this relation was unconditionally proved,
Chebyshev showed that
if the limit exists, then it must be 1.
(video
by Ram Murty).
Two independent proofs of this famous theorem were given in 1896,
by Hadamard and
Vallée-Poussin.
In 1951, Wiener made clear that both of those
proofs rely on the established fact that the Riemann Zeta Function
z
does not have any zeroes of the form 1+it.
A similar remark holds for a third PNT proof given in 1903 by
Edmund Landau (1877-1938) as
a prelude to his proof of the prime ideal theorem
for algebraic number fields.
In 1949, a beautiful elementary proof of the PNT was
again found by two mathematicians simultaneously:
Paul Erdös and
Atle Selberg.
The celebrated Riemann Hypothesis
(which states that the nontrivial zeroes of
z are all of the form
½+it )
is equivalent to the following statement:
p(x)
=
Li(x) + O(Öx ln x)
=
li(x) + O(Öx ln x)
Against all numerical evidence, which never shows
p(x) above li(x),
John E. Littlewood (1885-1977)
proved, in 1914, that the sign of
p(x)-li(x) changes infinitely many times.
It's now known that the first such reversal of sign
must happen for some number x with 370 digits or fewer.
(2014-07-24) Riemann's weighted prime-power counting function J
Giving partial credit to the powers of primes.
It turns out that Euler's Zeta function,
the undisputed Queen of analytic number theory, is directly tied with a special
counting function closely related to the prime-counting function:
Instead of just counting the primes below x, like the function p does,
the function J also gives a fractional score of 1/n
to the n-th power of a prime.
Since there are clearly p ( x1/n )
such numbers below x, we have:
J ( x ) =
p ( x )
+
p ( x1/2 ) / 2
+
p ( x1/3 ) / 3
+
p ( x1/4 ) / 4
+ ...
J has jump discontinuities at prime-powers,
where its value is defined as the half-sum of its
lower and upper limits (to be consistent with
Fourier analysis).
The above formula can be inverted using the Möbius
function m :
p ( x ) = J ( x )
- J( x1/2 ) / 2
- J( x1/3 ) / 3
+ ... +
m(n) J( x1/n ) / n
+ ...
Proof :
To check this, use the above definition of J
to expand the RHS and then,
for every integer k, regroup all terms where
x is raised to 1/k :
å m
å n
m(n)
p( x1/mn ) / mn
=
å k
[ å n|k m(n) ]
p( x1/k ) / k
The bracketed sum is a known function of k which
vanishes unless k=1.
J is sometimes termed Riemann's Jump Function.
Bernhard Riemann introduced it
(using the symbol f at the time) in his famous 1859 paper
on the Zeta function, as part of the following construction...
The paper entitled
"Über die Anzahl der Primzahlen unter
einer gegebenen Grösse" (Nov. 1859)
is the only one Riemann ever wrote on the subject of the
Zeta function (z) and/or Number Theory.
In it, he formulates the wonderful conjecture
now known as the Riemann hypothesis (RH)
but the rest of the paper doesn't depend on that. Riemann's own words were:
"It's very probable that all roots are real.
One would surely wish for a rigorous proof here. I have
temporarily put aside the search for one, after some futile attempts,
because it's not necessary for the immediate goal of my study."
When Re(z) > 1, the series are absolutely convergent and we may write:
Riemann then substitutes every occurrence of p-kz
with a definite integral:
p-kz = z
ò
¥
x-z-1 dx
pk
This turns the whole sum into an integral involving the above function J :
Log z(z) = z
ò
¥
J(x) x-z-1 dx
0
Riemann's Explicit Formula (1859) :
Now comes the great part:
The above integral transformation would later be called a
Mellin transform
(Hjalmar Mellin was only 5 years old at the time).
Riemann realized that it could be inverted to retrieve J from z.
As we already know how the prime-counting function is derived from J, this will give us an explicit
way to obtain it from z...
The sum is understood to be performed over all the zeroes of the Zeta function, taken
in increasing order of magnitude
(the value of the sum depends on this order
because the series isn't absolutely convergent).
(2009-06-26) Number of divisors of an integer N
A large number N is expected to have about Log N divisors.
In 1838, Dirichlet
evaluated the average number of divisors of
all positive numbers not exceeding N.
This involves the Euler-Mascheroni constant
g :
Log N + 2 g - 1
»
Log N + 0.15443...
(2009-06-26) On the number w(N)
of prime factors of an integer N
A large number N has about
Log Log N prime factors (1917)
The number of distinct prime factors of n is traditionally
denoted w(n).
The function w
(see A001221)
is an additive function. That's to say:
w( ab ) =
w( a )
+ w( b )
whenever a and b
are coprime.
In 1917, G.H. Hardy
and S. Ramanujan proved
w(n) to be
asymptotically equal
to Log Log n .
In 1933,
Paul Turán
(1910-1976) gave an innovative one-page proof of that fact,
also featured in his doctoral dissertation (1934).
(2022-09-17) The Erdös-Kac Theorem (1940)
Fundamental law of probabilistic number theory.
(2006-05-24) The Largest Known Prime
Until a fast formula is found, the record will be broken again and again.
The largest known prime has very often been of the
form 2n-1. Such numbers are called Mersenne numbers
and their prime values are known as Mersenne primes
(we discuss elsewhere their history,
the special form of their factors
and the connection with
perfect numbers).
It's easy to see that a Mersenne number can't be prime unless the
exponent (n) is itself prime. (This happens to be also a consequence of
a nice general property of integer sequences which start with 0 and 1 and obey
a second-order recurrence,
as we demonstrate elsewhere.)
The primality of the exponent is not sufficient. For example,
the 11th Mersenne number 2047 is the product of 23 and 89, whereas the
23rd is divisible by 47...
Nevertheless, the primality of Mersenne primes is (currently)
significantly easier to establish
than that of all other integers of similar magnitudes.
The gap between the Mersenne primes 2127-1
and 2521-1 was sufficiently large to allow other approaches
to break the record, as documented in the table below.
This happened again between the discovery of the
primality of 2216091-1 (Slowinski, 1985)
and that of 2756839-1 (Slowinski, Gage et al., 1992)
when an "Amdahl 1200" computer
was used to prove the primality of the following number
(J. Brown, C. Noll, B. Parady, G. Smith, J. Smith and S. Zarantonello, 1989).
391581 ´ 2 216193 - 1
Since 1996, the scene has been dominated by the "Great Internet Mersenne Prime Search"
(GIMPS) which has harnessed thousands of microcomputers and found
allthe latest record primes
(see GIMPS for an update).
The
"Largest Known Prime", by Date
(until the dawn of the Computer Era)
Le Lasseur's Number :
The 17-digit number 13373763765986881 divides the 360th
Fibonacci number.
It was the second-largest known prime when it was discovered in 1879 by the noted French amateur
Henri Le Lasseur
(Henri Le Lasseur
de Ranzay, 1821-1894; also spelled "de Ranzey").
It has been argued that this number was (briefly) the largest
"known" prime, as the prime status of M127 (39 digits)
was supposedly not firmly established at the time. This ain't so, unfortunately.
The heroic proof of
the primality of a "general" number as large as Le Lasseur's number
would have deserved a bright spot in the record books,
instead of a mere footnote...
Le Lasseur's number was then the largest prime whose primality had been established by
general-purpose methods.
It's more than 4000 times larger than the runner-up
3203431780337 (Landry's number, 1867).
By contrast, the Frenchman Aimé Ferrier
officially reported his 44-digit record-breaking prime on
Bastille day, July 14, 1951. He had been working on this since May
and Jeff Miller may have been aware of Ferrier's ongoing work.
According to the 1997 recollections
of family member David Miller
as reported by Chris Caldwell :
"Jeff Miller went to some length to make sure
Ferrier's result was not overlooked ".
Miller may well have changed his original strategy (leading to his 79-digit record)
specifically to beat Ferrier's upcoming result
which would have overshadowed Miller's other results (the first of which
broke the 75-year old record of Lucas).
However, Miller deliberately reported both
his own 79-digit number and
Ferrier's 44-digit prime as having been discovered "in early July". This may have been a
professional courtesy to Ferrier,
although a deeper inquiry (which probably never took place) may or may not have revealed
that Ferrier's results came a few hours too late to enter the record book.
Giving priority to Ferrier puts both numbers in the record book and still gives
credit to Miller and Wheeler for having broken the long-standing
record of Lucas with the earliest of their 41-digit numbers.
Ferrier's number itself stands out as the largest prime ever discovered
without the help of an electronic computer.
This healthy ambiguity ought to be strictly respected now.
This is just what D.H. Lehmer did when
he summarized the "Recent Discoveries of Large Primes"
very shortly after those events [MTAC, 5, 36, Oct. 1951].
A machine printed the primality of 24253-1
before that of 24423-1.
However, a human being (Alexander Hurwitz)
read about the latter before anybody
knew about the former, which was thus never largest anong "known primes"
(for more details, see our presentation of Mersenne primes and
perfect numbers).
(2007-05-08) The Lucas-Lehmer Test (1930)
A fast way to check the primality of the pth Mersenne number 2p-1.
The Lucas-Lehmer test is a special case of the modern way to check the primality
of n when all the prime factors of n+1 are known.
It boils down to a procedure devised in 1878 by
Edouard Lucas (1842-1991) and streamlined by
D.H. Lehmer (1905-1991) in 1930:
Consider the following recursively-defined
sequence, modulo
2p-1
L0 = 4
Ln+1 =
Ln2 - 2 [mod 2p-1]
For an odd prime p,
2p-1 is prime if and only if
Lp-2 is zero. That's all!
So, the primality of
2p-1 can be determined with just p-2 multiplications.
(2017-11-13) Proth Numbers & Proth Primes (Proth's theorem, 1878)
Proth numbers are integers of the form k 2n + 1 with k < 2n
Proth's theorem (1878):
A Proth number N = k 2n + 1 [ with k < 2n ]
is prime if and only if a(N-1)/2 is congruent to -1 modulo N,
for some a.
Proof :
The condition is clearly necessary because it's satisfied for any odd prime N,
by Euler's criterion,
for exactly 50% of the possible positive choices for a (namely, the so-called
quadratic nonresidues). It's more delicate to establish that the stated condition
is sufficient.
Thus, the primality of a Proth number N can be easily checked by exponentiation modulo a
suitable base a.
The test itself does tell if the base is suitable and 50% of the random choices are.
(2017-11-13) Sierpinski Numbers [of the second kind]
Odd numbers k for which k 2n + 1 is never prime.
A Sierpinski number is an odd modulus k for which the
Proth number k 2n + 1
is never prime, for any integer n.
There are infinitely many Sierpinski numbers.
At this writing, the smallest known one is 78557.
It is due to John Selfridge (1927-2010) who showed, in 1962, that:
78557 . 2n + 1 is divisible by 3, 5, 7, 13, 19, 37 or 73
In 1967, Selfridge and Sierpinski conjectured that 78557
was the smallest Sierpinski number. In 2002, only 17
lesser possibilities remained open and the Seventeen
or Bust online collaboration was formed to tackle them all. Between March 2002 and April 2016, they managed
to eliminate eleven of those candidates, before merging with the
PrimeGrid project, which
soon eliminated one more (10223) by using Proth's theorem
to prove the primality of the following 9383761-digit number:
Only 5 remaining numbers could falsify the Selfridge-Sierpinski conjecture:
21181, 22699, 24737, 55459, 67607
Waclaw Sierpinski (1882-1969)
|
John Selfridge (1927-2010)
"Sierpinski numbers of the first kind" nn+1
(A014566)
are unrelated to the above Sierpinski numbers.
(2017-08-03) Pratt's theorem & Pratt primality certificates (1975)
Keys to a quick proof that a given number is prime.
The converse of Fermat's little theorem
can be used to design a nondeterministic algorithm
which can prove the primality of a prime in polynomial time.
This establishes that PRIMES (the set of all primes numbers, expressed as strings of digits)
is in NP (Pratt's theorem, 1975).
The lucky guesses in that nondeterministic algorithm can be
construed as a standardized proof that a given number is prime; they form what is known
as a Pratt primality certificate.
The validity of such a certificate can be checked deterministically rather quickly
(in polynomial time).
A Pratt certificate for a prime p is recursively defined as consisting of:
A generator (witness) for the multiplicative group
(/p)*
The prime factorization of p-1.
A Pratt certificate for each prime in that factorization.
Pratt certificates are typically recorded in databases of very large primes, including
The Prime Pages of
Chris Caldwell.
(2017-08-03) From Pratt's theorem (1975) to the AKS test (2002) :
Telling whether any number is prime or composite, in polynomial time.
The AKS algorithm was a great theoretical breakthrough which proved unconditionally
that the primality of an integer can be checked deterministically in polynomial time.
However, for all practical purposes, the randomized
Rabin-Miller test remains unsurpassed.
PRIMES is in P
by Manindra Agrawal, Neeraj Kayal & Nitin Saxena (2002).
(2006-05-24) Is there a formula which gives only primes?
What's a "formula" anyway?
As of this writing, checking the primality
of 2p-1 for increasingly large values of the exponent p
is the most efficient way to name large primes
(see GIMPS).
Anything faster than that would be major news. Something vastly
faster could essentially end the above record-breaking game
by making it easy to "name" explicitly primes with so many digits
that they could not possibly be written down.
This would not necessarily end the search for primes of
a specific type (like "Mersenne primes") but it would make the title of
"largest known prime" as meaningless as that of "largest known integer"
(whatever integer is named, something like
"two to the power of that" will name something vastly larger).
It's not enough to have a "formula" for larger primes.
It must be an effective formula...
The formula discussed next isn't an effective one!
Mills' Formula :
There are uncountably many values of x
for which x3n
will always round down to a prime integer.
This was shown in 1947 by a student of
Emil Artin at Princeton:
William H. Mills
(1921-2007?).
Mills used deep results about prime gaps which had been obtained by
Guido Hoheisel
(1894-1968) in 1930 and by
Albert Ingham
(1900-1967) in 1937.
Assuming the
Riemann Hypothesis to be true,
the lowest such x
may be explicitly computed, by bracketing its powers:
x1, rounded down, is the lowest prime, namely 2
x3, rounded down, is the lowest prime between
23 and 33, namely 11
x9, rounded down, is the lowest prime between
113 and 123, i.e., 1361
x27, rounded down, is the lowest prime between
13613 and 13623, etc.
Thus, raising x = 2.229494772491595235722852237656- to the power
of 3n (and rounding down) only yields prime numbers, namely:
2, 11, 1361, 2521008887, 16022236204009818131831320183,
etc.
One fallacy with that "etc." is that we had to prove the primality
of the last value to obtain x with this much precision
(conversely, the precision given is barely enough to obtain this
last prime number correctly).
The whole thing is
merely a way to encode
an infinite sequence of prime values into the infinitely
many decimals of a real number. It doesn't help in
constructing such a sequence.
The other fallacy is that the iteration of the process depends on the "obvious fact"
that there's always a prime between consecutive cubes.
Although the
Hoheisel-Ingham theorem does guarantees that for
sufficiently large cubes,
it doesn't say exactly how large is large.
Therefore, we cannot proceed "by inspection" for the above sequence
until a putative lower bound is reached.
Currently,
our only option is to assume the validity of Riemann's hypothesis
and conclude on that conditional basis
(otherwise no satisfactory value of x can be established).
The above sequence is usually expressed as A3, A9...
A3n... where n is a nonzero
integer and A (the cube root of the above x) is now known as
Mills' constant
(cf. A051021).
Thanks to T.D. Noe
for clarifying this, on 2008-09-23
(reminding me that we attended graduate school together).
A = x1/3 =
1.306377883863080690468614492602605712916784585156713644368...
Using squares instead of cubes in the above would be fine if we knew
that there's always a prime between consecutive squares. If that's true,
then the lowest number that truncates down to a prime when
raised to the power of a 2-power is 2.3247099696648664983923017-
The first primes so obtained are
2, 5, 29, 853, 727613, 529420677791 and 280286254072681840639693.
See A059784.
(2009-01-23) Ulam's Lucky Numbers and Ludic Numbers
Prime-likes sequences obtained by modifying the
Sieve of Erathostenes.
The prime numbers not exceeding some integer n can be obtained
by crossing out some of the positive integers not exceeding n,
according to the following sieving procedure, known as the
Sieve of Eratosthenes
which was devised by Eratosthenes of Cyrene (276-194 BC).
In the above, we could instead cross out every pth number
among the subsequent numbers not yet crossed out. In this case, we do not obtain
the sequence of primes, but the so-called ludic numbers
If we start with the odd numbers and repeatedly remove every pth
number (counting from the very beginning of the surviving sequence) we obtain the
[odd] lucky numbers (French: nombres fastes ):