Prime number
A prime number is a natural number that is greater than 1 and only divisible by itself and by 1 . The word “prime number” is derived from the Latin numerus primus 'first number' , where primus specifically means 'beginning, the first (of things)', so that a 'starting number' is meant that is not constructed from any other (preceding) number can.
The set of prime numbers is usually denoted by the symbol . With linked is the result of the ordered by size primes that are also prime consequence calls. It is accordingly
With
The importance of the prime numbers for many areas of mathematics is based on three consequences from their definition:
- Existence and uniqueness of the prime factorization : Every natural number that is greater than 1 and is not itself a prime number can be written as the product of at least two prime numbers. This product representation is clear except for the order of the factors. That serves as proof
- Euclid's lemma : If a product of two natural numbers is divisible by a prime number, then at least one of the factors is divisible by them.
- Prime numbers cannot be represented as the product of two natural numbers that are both greater than 1.
These properties are used in algebra for generalizations of the concept of prime numbers .
A number that is the product of two or more prime factors is called composite . The number 1 is neither prime nor composite, which is related to its invertibility . All other natural numbers are one of the two, either prime (i.e. prime number) or composite.
Even in ancient Greece there was an interest in the prime numbers and some of their properties were discovered. Although primes have always been very appealing to people since then, many questions relating to prime numbers remain unanswered , including those that are more than a hundred years old and easy to understand. These include Goldbach's conjecture , according to which every even number except 2 can be represented as the sum of two prime numbers, and the conjecture that there are an infinite number of prime twins (these are pairs of prime numbers whose difference is 2).
Prime numbers and their properties play a major role in cryptography because prime factors cannot really be found efficiently, even with the advent of electronic calculating machines. On the other hand, these machines enable efficient encryption and, if you know the key, decryption of even long texts.
Prime factorization
The fundamental theorem of arithmetic applies : Every positive integer can be represented as a product of prime numbers, and this representation is unique except for the order of the prime numbers. These prime numbers are called the prime factors of the number. The one is shown as an empty product .
Because every natural number greater than zero can be clearly represented by multiplying prime numbers, the prime numbers occupy a special atomic position in mathematics, they “generate” all other natural numbers, so to speak. Alexander K. Dewdney described them as largely similar to the elements of chemistry .
This also makes it clear why it is inexpedient to define one as a prime number: It is the neutral element of multiplication and can therefore not generate any further numbers multiplicatively. It is not required for the representation of the numbers as the product of prime factors. If one were to count 1 among the prime numbers, the uniqueness of the prime factorization would also be lost, because any number of ones can be appended to each division without changing the value of the number.
A number of factorization methods have been developed to determine the prime factors of general numbers or those of special form as quickly as possible. So far, however, no method is known to efficiently factor any number, i.e. H. in a time that grows at most polynomially with the length of the given number. The factoring assumption states that such a method does not exist either.
Properties of prime numbers
The prime numbers are within the set of natural numbers, thereby characterized , that each of them natural exactly two numbers as a splitter has.
With the exception of the number 2, all prime numbers are odd, because all larger even numbers can be divided by 2 (at least) in addition to themselves and 1. So every prime number except 2 has the form with a natural number .
Each prime number can be assigned to one of the two classes “prime number of form ” or “prime number of form ”, where is a natural number. In addition, every prime number has the form or , where is a natural number. According to Dirichlet's prime number theorem, there are infinitely many prime numbers in each of these four classes.
Every natural number of the form with a nonnegative integer contains at least one prime factor of the form . A corresponding statement about numbers of the form or prime factors of the form is not possible.
A prime number can be written in the form with whole numbers if and only if the form has. In this case the representation is essentially clear; H. except for the order and sign of . This representation corresponds to the prime factorization
in the ring of whole Gaussian numbers .
The number −1 is a quadratic remainder modulo any prime number of the form and a quadratic non- remainder modulo any prime number of the form .
Fermat's Little Theorem
Let it be a prime number. For every whole number that is not divisible by , the following applies (for the notation see congruence ):
For numbers that are not divisible by numbers , the following formulation is equivalent:
There are numbers that are not prime, but still behave like prime numbers on a base ; h., it is . Such are called Fermat's pseudoprimes for the base . One that is Fermat's pseudoprime with respect to all bases coprime to it is called a Carmichael number .
In this context, the problem of Fermat's pseudoprimes becomes apparent: they are mistaken for prime numbers by a primality test that uses Fermat's small theorem ( Fermat's primality test ). However, if an encryption method such as RSA uses a composite number instead of a prime number, the encryption is no longer secure. Therefore, better primality tests must be used in such procedures.
Euler and the Legendre symbol
A simple consequence of Fermat's Little Theorem is the following statement: For every odd prime number and every integer that is not divisible by , either
or
One can show that the first case occurs if and only if there is a square number that is congruent to modulo , see Legendre symbol .
Binomial coefficient
For prime numbers and applies
together with the binomial sentence it follows
For whole numbers , this statement also follows directly from Fermat's Little Theorem, but it can also be used, for example, for polynomials with whole-number coefficients; in the general context it corresponds to the fact that the mapping in rings of the characteristic is a homomorphism, the so-called Frobenius homomorphism .
From Wilson's theorem ( is a prime number if and only if is) it follows that for every prime number and every natural number there is congruence
is satisfied.
Charles Babbage proved in 1819 that for every prime number this congruence holds:
The mathematician Joseph Wolstenholme (1829–1891) then proved in 1862 that the following congruence applies to every prime number :
Giuga
From Fermat's Little Theorem it follows that for a prime number :
Example :
Giuseppe Giuga hypothesized that the reverse direction also applies, i.e. that a number with this property is always prime. It is not clear whether this assumption is correct. It is known, however, that a counterexample would have to have more than 10,000 decimal places. In connection with Giuga's conjecture , the Giuga numbers are examined.
Linear recursions
The little Fermat's sentence can also be read in the following form: In the following , the -th term for a prime number is always divisible by. Other sequences of exponential character have similar properties, such as the Lucas sequence ( ) and the Perrin sequence ( ). Analog apply to other linear recursion, but more complex statements, such as the Fibonacci sequence : If a prime number, then by divisible; is there
the Legendre symbol .
Divergence of the sum of the reciprocal values
The series of reciprocal values of the prime numbers is divergent. Thus:
- .
This is equivalent to the statement that the sequence defined by does not have a finite limit value, which in turn means that any imaginable real number can be exceeded for a sufficiently large selected . This is initially astonishing, since the prime number gaps keep increasing on average. The set of Mertens makes a statement about the exact growth behavior of these divergent series.
Prime number tests
A prime number test can be used to find out whether any natural number is prime. There are several such methods that rely on special properties of prime numbers. In practice, the Miller-Rabin test is most often used, which has an extremely short duration, but has a low probability of delivering false-positive results. With the AKS primality test it is possible to decide on the primality without the risk of an error in polynomial running time. However, in practice it is significantly slower than the Miller-Rabin test.
Prime number certificate
Finding out whether a natural number is prime or not can be a hassle. For each prime number, however, a chain of assertions can be made, all of which are immediately understandable, together prove the primality and whose total length is at most proportional to the square of the length of the prime number. Such a document is Certificate (Engl. Primality certificate ) called.
In the case of the composite nature (non-primality) of a number, the difference between receipt and finding a receipt is even more obvious: Two factors are sufficient as evidence, the product of which results in the composite number; Finding a real divisor can take a lot of effort.
Largest known prime
In the fourth century BC, the Greek Euclid logically concluded that there are an infinite number of prime numbers; this statement is called Euclid's theorem. Euclid provided a contradictory proof for the correctness of this theorem ( Elements, Book IX, § 20): Based on the assumption that there are only finitely many prime numbers, another number can be constructed that has a previously unknown prime number as a divisor or itself is a prime number, which contradicts the assumption. Thus a finite set can never contain all prime numbers, so there are infinitely many. Today we know a whole series of proofs for Euclid's theorem.
Euclid's theorem states that there is no greatest prime. However, there is no known method that efficiently generates arbitrarily large prime numbers - that is why there has always been one largest known prime number since people started dealing with prime numbers. Currently (as of December 2018) it is a number with 24,862,048 (decimal) digits, which was calculated on December 7, 2018. The discoverer Patrick Laroche received $ 3,000 from the Great Internet Mersenne Prime Search project , which searches for Mersenne prime numbers using distributed computing .
The largest known prime number was almost always a Mersenne prime number, i.e. of the form that the Lucas-Lehmer test can be used in this special case , a very quick prime number test compared to the general situation. When searching for large prime numbers, only numbers of this or a similarly suitable type are therefore examined for primality.
List of record prime numbers by years
number | Number of decimal digits |
year | Explorer (computer used) |
---|---|---|---|
2 17 −1 | 6th | 1588 | Cataldi |
2 19 −1 | 6th | 1588 | Cataldi |
2 31 −1 | 10 | 1772 | Euler |
(2 59 −1) / 179951 | 13 | 1867 | Landry |
2 127 −1 | 39 | 1876 | Lucas |
(2 148 +1) / 17 | 44 | 1951 | Ferrier |
180 · (2 127 −1) 2 +1 | 79 | 1951 | Miller & Wheeler (EDSAC1) |
2 521 −1 | 157 | 1952 | Robinson ( SWAC ) |
2 607 −1 | 183 | 1952 | Robinson (SWAC) |
2 1,279 −1 | 386 | 1952 | Robinson (SWAC) |
2 2,203 −1 | 664 | 1952 | Robinson (SWAC) |
2 2,281 −1 | 687 | 1952 | Robinson (SWAC) |
2 3,217 −1 | 969 | 1957 | Riesel (BESK) |
2 4,423 −1 | 1,332 | 1961 | Hurwitz (IBM7090) |
2 9,689 −1 | 2,917 | 1963 | Gillies (ILLIAC 2) |
2 9,941 −1 | 2,993 | 1963 | Gillies (ILLIAC 2) |
2 11,213 −1 | 3,376 | 1963 | Gillies (ILLIAC 2) |
2 19,937 −1 | 6.002 | 1971 | Tuckerman (IBM360 / 91) |
2 21,701 −1 | 6,533 | 1978 | Noll & Nickel (CDC Cyber 174) |
2 23,209 −1 | 6,987 | 1979 | Noll (CDC Cyber 174) |
2 44,497 −1 | 13,395 | 1979 | Nelson & Slowinski (Cray 1) |
2 86,243 −1 | 25,962 | 1982 | Slowinski (Cray 1) |
2 132,049 −1 | 39,751 | 1983 | Slowinski (Cray X-MP) |
2 216.091 −1 | 65,050 | 1985 | Slowinski (Cray X-MP / 24) |
391581 · 2 216,193 −1 | 65,087 | 1989 | "Amdahler Six" (Amdahl 1200) |
2 756 839 -1 | 227.832 | 1992 | Slowinski & Gage (Cray 2) |
2 859 433 -1 | 258.716 | 1994 | Slowinski & Gage (Cray C90) |
2 1,257,787 −1 | 378.632 | 1996 | Slowinski & Gage (Cray T94) |
2 1,398,269 −1 | 420.921 | 1996 | Armengaud, Woltman ( GIMPS , Pentium 90 MHz) |
2 2,976,221 −1 | 895.932 | 1997 | Spence, Woltman (GIMPS, Pentium 100 MHz) |
2 3,021,377 −1 | 909.526 | 1998 | Clarkson, Woltman, Kurowski (GIMPS, Pentium 200 MHz) |
2 6,972,593 −1 | 2,098,960 | 1999 | Hajratwala, Woltman, Kurowski (GIMPS, Pentium 350 MHz) |
2 13,466,917 −1 | 4,053,946 | 2001 | Cameron, Woltman, Kurowski (GIMPS, Athlon 800 MHz) |
2 20.996.011 −1 | 6.320.430 | 2003 | Shafer (GIMPS, Pentium 4 2 GHz) |
2 24,036,583 −1 | 7,235,733 | 2004 | Findley (GIMPS, Pentium 4 2.4 GHz) |
2 25,964,951 −1 | 7,816,230 | 2005 | Nowak (GIMPS, Pentium 4 2.4 GHz) |
2 30,402,457 −1 | 9,152,052 | 2005 | Cooper, Boone (GIMPS, Pentium 4 3 GHz) |
2 32,582,657 −1 | 9,808,358 | 2006 | Cooper, Boone (GIMPS, Pentium 4 3 GHz) |
2 43.112.609 −1 | 12,978,189 | 2008 | Smith, Woltman, Kurowski, et al. (GIMPS, Core 2 Duo 2.4 GHz) |
2 57,885,161 −1 | 17,425,170 | 2013 | Cooper, Woltman, Kurowski, et al. (GIMPS, Core2 Duo E8400 @ 3.00 GHz) |
2 74,207,281 −1 | 22,338,618 | 2016 | Cooper, Woltman, Kurowski, et al. (GIMPS, Intel i7-4790 @ 3.60 GHz) |
2 77,232,917 −1 | 23.249.425 | 2017 | Jonathan Pace et al. (GIMPS, Intel i5-6600 @ 3.30 GHz) |
2 82,589,933 −1 | 24,862,048 | 2018 | Patrick Laroche et al. (GIMPS, Intel i5-4590T @ 2.0 GHz) |
Distribution and growth
Pi function and prime number theorem
To investigate the distribution of the prime numbers one considers the function, among other things
- ,
the number of primes indicating and Primzahlzählfunktion is called. For example is
- .
This function and its growth behavior is a popular research subject in number theory. Over time, some approximation formulas have been developed and improved.
The prime number theorem says that
holds, that is, the quotient of the left and right side tends towards 1:
- (see asymptotic analysis )
The Dirichlet prime number theorem, on the other hand, restricts the consideration to residual classes : Let it be a natural number. If there is an integer that is not relatively prime , the arithmetic sequence can be
contain at most one prime number, because all terms in the series are divisible by the greatest common divisor of and . But if coprime is to , then the Dirichlet prime number theorem says that the sequence contains infinitely many prime numbers. For example, there are an infinite number of prime numbers of the form and an infinite number of the form ( each traverses the nonnegative natural numbers).
This statement can be further specified in the following form: It applies
here is the Euler phi function . In this sense, there are prime numbers for a fixed one in the remainder classes , each with an “equal number”.
Barriers
The (proven) Bonsian inequality guarantees that the square of a prime number is smaller than the product of all smaller prime numbers (from the fifth prime onwards).
According to Andrica's (unproven) conjecture , the difference between the roots of the -th and -th prime numbers is less than 1.
Prime gaps
The difference between two neighboring prime numbers is called the prime number gap. This difference fluctuates and there are prime number gaps of arbitrary size. But there are also restrictions on the size of the gap depending on its location:
The set of Bertrand ensures the existence of a prime number between any natural number and its double .
According to the (unproven) Legendre's conjecture, there is always at least one prime number between and .
Estimates of prime numbers and conclusions from the prime number theorem
In the following, the sequence of prime numbers is denoted by.
Estimates
The following estimates apply to indices :
- (1a)
- (1b)
- For
- (1c)
- For
- (1d)
- (1e)
- For
Consequences from the prime number theorem
With the prime number theorem, the following results are obtained:
- (2a)
- (2 B)
- For
- (2c)
For every positive real number there is a sequence of prime numbers with
- .
- (2d)
The set of quotients formed from all prime numbers is a dense subset of the set of all positive real numbers. That means: For any positive real numbers with there always exist prime numbers , so that
is satisfied.
Generation of prime numbers
One of the oldest algorithms for determining prime numbers is the sieve of Eratosthenes . To date, no efficient prime number generator is known. However, there are formulas where there is a certain probability that the numbers generated are prime. Such numbers have to be tested for their primality afterwards.
Special prime numbers and prime number constellations
Other special types of prime numbers can be found in the category: prime number .
generalization
In ring theory, the concept of the prime number is generalized to the elements of any commutative unitary ring. The corresponding terms are prime element and irreducible element .
The prime numbers and their negatives are then precisely the prime elements and also precisely the irreducible elements of the ring of whole numbers . In factorial rings , that is, rings with unambiguous prime factorization, the terms prime element and irreducible element coincide; in general, however, the set of prime elements is only a subset of the set of irreducible elements.
Particularly in the case of Dedekind rings , which is significant from a number-theoretical point of view , prime ideals take on the role of prime numbers.
Prime numbers in computer science
In the information security and in particular in the encryption of messages (see cryptography ) play an important role primes. They are often used in asymmetric cryptosystems such as public key encryption methods. Important examples are the Diffie-Hellman key exchange , the RSA cryptosystem , which is used by OpenPGP , among others , the Elgamal cryptosystem and the Rabin cryptosystem . The keys are calculated from large, randomly generated prime numbers that must remain secret.
Such algorithms are based on one-way functions that can be executed quickly, but the inverse of which is practically impossible to calculate with the currently known technology. New information technologies , such as quantum computers , could change that. The unsolved P-NP problem is related to this.
Prime numbers in nature
Some animal and plant species (e.g. certain cicadas or spruce ) multiply particularly strongly in cycles of prime numbers (about every 11, 13 or 17 years) in order to make it difficult for predators to adapt to the massive occurrence.
Why 1 is not a prime number
For hundreds of years mathematicians have debated whether or not the number is prime. The great mathematician Godfrey Harold Hardy , for example, designated the number 1 as a prime number in 1908, but no longer in 1929 at the latest. In general, since the 20th century, the vast majority of mathematicians have agreed not to count the number 1 among the prime numbers.
The argument that 1 is prime is as follows:
- 1 is only divisible by itself and 1.
Arguments against that 1 is not a prime number are as follows:
- A particularly important proposition in mathematics is the uniqueness of the prime factorization . For example, if a number were prime, the composite number would have many different prime factorizations, for example .
- Suddenly every number would have an infinite number of different prime factorizations and one would have to formulate the requirements for this important theorem differently so that the uniqueness is given again.
- If you multiply two prime numbers with each other, you get a composite number according to the definition , i.e. a number that consists of at least two (prime) factors. If 1 were a prime number, it could be multiplied by a prime number, for example, and the product would again be a prime number and not a composite number. The definition of the composite number would have to be much more complicated.
- Every prime number has exactly two factors: the number 1 and itself. Has only one factor and obviously does not fulfill this property, which means that this number is different from all other prime numbers.
- The sieve of Eratosthenes would not work, since one would first have to cross out all multiples of 1, which would not leave a single number other than the 1.
- For all prime numbers is Euler's Phi function . But applies to . The sentence would have to be reformulated and make 1 an exception.
- The divisor function applies to all prime numbers . For is but . It also applies . For is but . So the number 1 would be a big exception for these function (s) as well.
- The definition of prime elements would have to be reformulated if 1 were a prime number. The new definition would be more complicated.
- For every prime power there is a finite field that has just as many elements. If 1 were a prime number, there would also have to be a finite field with a single element. But there is no such thing. One would have to change the definition of finite fields.
There are other mathematical theorems about prime numbers that would also have to be rephrased if the number were a prime number.
The examples show that the set of prime numbers without a 1 is urgently needed - more urgently than the concept of the prime numbers including the 1. Since there are always degrees of freedom in definitions, for the sake of the economy of the terms, the decision was made to exclude (in addition to the 0) the 1 (and more generally all units ) from the prime numbers (or prime elements).
See also
- Prime factorization
- Prime test
- Gilbreath's guess
- Illegal prime number
- Permutable prime number
- Relatively prim
- Near prime numbers
literature
- Peter Bundschuh : Introduction to Number Theory. 6th edition. Springer, Berlin 2008, ISBN 978-3-540-76490-8 .
- Marcus du Sautoy : The music of the prime numbers. On the trail of the greatest puzzle in mathematics. Beck, Munich 2004, ISBN 3-406-52320-X .
- Władysław Narkiewicz : The Development of Prime Number Theory. From Euclid to Hardy and Littlewood. Springer, Berlin 2000, ISBN 3-540-66289-8 .
- Paulo Ribenboim : The New Book of Prime Number Records. Springer, New York 1996, ISBN 0-387-94457-5 .
- Robert E. Dressler, Louis Pigno, Robert Young: Sums of squares of primes . In: Nordisk Mat. Tidskr . tape 24 , 1976, p. 39-40 ( MR0419352 ).
- Hans Rademacher , Otto Toeplitz : Of numbers and figures. Samples of mathematical thinking for lovers of mathematics (= Heidelberger Taschenbücher . Volume 50 ). Springer Verlag, Berlin ( inter alia) 1968 ( MR0252141 ).
- JB Rosser : The n-th prime is greater than n log n . In: Proc. London Math. Soc . tape 45 , 1939, pp. 21-44 .
- J. Barkley Rosser , L. Schoenfeld : Approximate formulas for some functions of prime numbers . In: Illinois J. Math . tape 6 , 1962, pp. 64-94 ( projecteuclid.org [PDF]). MR0137689
- Wacław Sierpiński : Elementary Theory of Numbers (= North-Holland Mathematical Library . Volume 31 ). 2nd revised and expanded edition. North-Holland (inter alia), Amsterdam (inter alia) 1988, ISBN 0-444-86662-0 .
- József Sándor , Dragoslav S. Mitrinović , Borislav Crstici : Handbook of Number Theory. 2nd Edition. tape I . Springer-Verlag, Dordrecht, NL 2006, ISBN 978-1-4020-4215-7 ( MR2186914 ).
Web links
- The Prime Pages (English)
- The prime number side
- Eric W. Weisstein : Rosser's Theorem . In: MathWorld (English).
Individual evidence
- ^ Karl Ernst Georges : Comprehensive Latin-German concise dictionary . 8th, improved and increased edition. Hahnsche Buchhandlung, Hannover 1918 ( zeno.org [accessed on March 12, 2020] dictionary entry “prior”).
- ↑ Christlieb von Clausberg : Demonstrative arithmetic art, or science to calculate thoroughly and briefly . In which both common and other types of commercial invoices, samples and arbitrage of bills of exchange are thoroughly taught in a particularly short manner, and a description of European coins, types of bills and usages, a comparison of weights and cubic measures, the true calculation of the interusurii, a new logarithmic table, too more other mathematical and curious calculations are attached. Bernhard Christoph Breitkopf and Son , Leipzig 1762, p. 86 ( limited preview in Google Book Search [accessed March 12, 2020]).
- ↑ Armin Leutbecher: Number Theory: An Introduction to Algebra. Springer, 1996, ISBN 3-540-58791-8 , p. 18, limited preview in the Google book search.
- ^ Vaughan R. Pratt: Every Prime has a Succinct Certificate. PDF.
- ^ Vašek Chvátal : Lecture notes on Pratt's Primality Proofs. PDF.
- ↑ Vaughan Pratt's Theorem as Theorem of the Day. PDF.
- ↑ For proofs of Euclid's theorem see evidence archive .
- ↑ Mersenne Prime Number discovery - 2 82589933 -1 is Prime! Retrieved December 21, 2018 .
- ↑ List of known Mersenne prime numbers - PrimeNet. Retrieved November 1, 2019 .
- ↑ https://primes.utm.edu/bios/page.php?id=5004
- ↑ Daniel AJ Sokolov: Computer in Florida finds new greatest prime. In: Heise.de. December 22, 2018, accessed December 22, 2018 .
- ↑ Rademacher-Toeplitz: p. 164.
- ↑ Sierpiński: p. 146.
- ↑ Dressler Pigno-Young: . Nordisk Mat Tidskr . tape 24 , p. 39 .
- ↑ Sándor Mitrinović-Crstici: S. 247th
- ↑ Sierpiński: p. 145.
- ↑ The estimate (1d) was first found by John Barkley Rosser (see Rosser in: Proc. London Math. Soc., Vol. 45, p. 21 ff. / Sierpiński, p. 163 / Sándor-Mitrinović-Crstici, p . 247).
- ↑ Sierpiński: p. 162.
- ↑ From (1e) is obtained as Sierpiński observes, directly, the divergence in sequence .
- ↑ Sierpiński: p. 163.
- ^ Rosser-Schoenfeld: Illinois J. Math . tape 6 , p. 64 ff .
- ↑ Sierpiński: p. 163.
- ↑ As Sierpiński notes, (2b) leads directly to the prime number theorem.
- ↑ Sierpiński: p. 165.
- ↑ According to Sierpiński, this result was first obtained by the Polish mathematician Hugo Steinhaus .
- ↑ Sierpiński: p. 165.
- ↑ Klaus Schmeh : What cicadas have to do with prime numbers. In: heise online . Retrieved March 9, 2020 .
- ↑ Numbers count in cicada life. Max Planck Society, April 29, 2002, archived from the original on October 1, 2007 ; accessed on March 9, 2020 .
- ↑ Chris K. Caldwell , Angela Reddick, Yeng Xiong: The History of the Primality of One: A Selection of Sources. Journal of Integer Sequences 15 , Article 12.9.8, 2012, pp. 1-40 , accessed on February 10, 2020 .